Shampine, Allen, Pruess - Fundamentals of Numerical Computing (523185), страница 28
Текст из файла (страница 28)
It is usually said that a bisection code will produce an interval [B,C] of specifiedlength that contains a root because f(B) f(C) < 0. This is superficial. It should bequalified by saying that either this is true, or a root has been found that is as accurateas the precision allows. The qualification “as accurate as the precision allows” meanshere that either the computed f(z) vanishes, or that one of the computed values f(B),f(C) has the wrong sign.A basic assumption of the bisection method is that f(x) is continuous.
It should beno surprise that the method can fail when this is not the case. Because a bisection codepays no attention to the values of the function, it cannot tell the difference between apole of odd multiplicity and a root of odd multiplicity [unless it attempts to evaluatef(x) exactly at a pole and there is an overflow]. So, for example, if a bisection code isgiven the function tan(x) and asked to find the root in [5,7], it will have no difficulty.If asked to find the root in [4,7], it will not realize there is a root in the interval becausethe sign change due to the simple pole cancels out the sign change due to the simpleroot.
And, what is worse, if asked to find a root in [4,5], it will locate a pole or causean overflow. We see here another reason for scaling: removing odd order poles byscaling removes the sign changes that might cause bisection to locate a pole ratherthan a zero. Here this is done by F(x) = cos(x) tan(x) = sin(x). One of the examplesof scaling given earlier is a less trivial illustration of the point. Because of the very realpossibility of computing a pole of odd multiplicity, it is prudent when using a bisectioncode to inspect the residual f(z) of an alleged root z-it would be highly embarrassingto claim that z results in a very small value of f(z) when it actually results in a verylarge value!A bisection code can converge to a pole because it makes no use of the valuef(M), just its sign.
Because of this its rate of convergence is the same whether the rootis simple or not and whether the function is smooth or not. Other methods convergemuch faster when the root is simple and the function is smooth, but they do not workso well when this is not the case.Bisection has a number of virtues. Provided an initial bracket can be found, it will140CHAPTER 4ROOTS OF NONLINEAR EQUATIONSconverge no matter how large the initial interval known to contain a root. It is easyto decide reliably when the approximation is good enough. It converges reasonablyfast and the rate of convergence is independent of the multiplicity of the root and thesmoothness of the function. The method deals well with limiting precision.Bisection also has some drawbacks.
If there are an even number of zeros betweenB and C, it will not realize that there are any zeros at all because there is no signchange. In particular, it is not possible to find a zero of even multiplicity except byaccident. It can be fooled by poles. A major disadvantage is that for simple zeros,which seem to be the most common by far, there are methods that converge muchmore rapidly.
There is no way to be confident of calculating a particular root nor ofgetting all the roots. This is troublesome with all the methods, but some are (much)better at computing the root closest to a guessed value. Bisection does not generalizeto functions of a complex variable nor easily to functions of several variables.Let us now take up two methods that are superior to bisection in some, althoughnot all, of these respects.
Both approximate f(x) by a straight line L(x) and thenapproximate a root of f(x) = 0 by a root of L(x) = 0.Newton’s method (Figure 4.3) will be familiar from calculus. It takes L(x) as theline tangent to f(x) at the latest approximation xi and the next approximation (iterate)is the root xi+1 of L(x) = 0. Equivalently, approximating f(x) by the linear terms of aTaylor’s series about xi ,suggests solvingfor its root xi+1 to approximate α [assuming that f´(xi )known as0].
The resulting method isNewton's method:(4.5)When it is inconvenient or expensive to evaluate f´(x), a related procedure calledthe secant rule is preferred because it uses only values of f(x). Let L(x) be the secantline that interpolates f(x) at the two approximations xi-1,xi :The next approximation xi+1 is taken to be the root of L(x) = 0. Hence, assuming thatf(xi )f(xi-l), we have thesecant rule:(4.6)4.1 BISECTION, NEWTON’S METHOD, AND THE SECANT RULE141Figure 4.3 Newton’s method.The method is illustrated graphically in Figure 4.4.
Although a picture furnishes a natural motivation for the method, an alternative approach is to approximate the derivativein Newton’s method (4.5) by a difference quotient to get (4.6).A little analysis shows that Newton’s method and the secant rule converge muchfaster than bisection for a simple root of (4.1).
Considering first Newton’s method, wehave from (4.5)If xi is near α, thenNow f(α) = 0 and f´(α)for a simple root, soIt is seen that if xi is near a simple root, the error in xi+1 is roughly a constant multipleof the square of the error in xi . This is called quadratic convergence.A similar look at the secant rule (4.6) leads to(4.7)142CHAPTER 4ROOTS OF NONLINEAR EQUATIONSFigure 4.4 Secant rule.This method does not converge as fast as Newton’s method, but it is much faster thanbisection. For both methods it can be shown that if the starting values are sufficientlyclose to a simple root and f(x) is sufficiently smooth, the iterates will converge to thatroot. For Newton’s method,and for the secant rule,A careful treatment of the secant rule even shows thatwhere p =2Example 4.2. As in Example 4.1, let f(x) = x - 2.
An easy calculation shows thatfor the secant rule started with x1 = 3 and x2 = 2,4.1 BISECTION, NEWTON’S METHOD, AND THE SECANT RULE143and for Newton’s method started with x1 = 3,Both methods converge quite rapidly and the quadratic convergence of Newton’s methodis apparent. Comparison with the bisection method of Example 4.1 shows the superiority of the secant rule and Newton’s method (for this problem).nIf an iteration is such thatthe method is said to converge at rate r with constant γ. It has been argued that for asimple root, Newton’s method converges at the rate r = 2 and it has been stated thatthe secant rule converges at the rate r = p1.618. Bisection does not fit into thisframework; the width of the bracketing intervals are being halved at every step, butnothing can be said about(see Example 4.1).The secant rule is a principal part of the code Zero developed in this chapter, sowe now state conditions that guarantee its convergence to a simple root of (4.1) andstudy how fast it converges.
As a first step we derive an expression that relates thefunction values at three successive iterates xi-l, xi , xi+1. Let L(x) be the polynomialof degree 1 interpolating f(x) on the set {xi ,xi-1 }. The iterate xi+1 is the zero of L(x).In Chapter 3 we developed an expression for the error of interpolation [see (3.4)],144CHAPTER 4ROOTS OF NONLINEAR EQUATIONSwhich in this case isor, since L( x i+1 ) = 0,(4.8)for a suitable (unknown) pointrelationsSome manipulation of equation (4.6) gives the two(4.9)(4.10)A third relation is obtained from the mean value theorem for derivatives:(4.11)where ζ, a point between xi and xi-l, is unknown.
Combining equations (4.8)–(4.1l),we arrive atLet us assume that on an appropriate interval we have(4.12)and that we are computing a simple zero a. (Why must it be simple with these hypotheses?) Then these bounds and the expression above for f(xi+1) imply thatIf we letthis inequality leads toSupposing that4.1 BISECTION, NEWTON’S METHOD, AND THE SECANT RULE145it is easy to argue by induction thatwhereThe formal proof is left as an exercise. Sincewe see that for i large,In any event,and since 0 < ε < 1, we must havewhich iswhat we wanted to prove.
Let us now state a formal theorem and complete the detailsof its proof.Theorem 4.1.The secant rule defined by (4.6) with initial guesses x0, x1 converges to a simple zero α of f(x) if x0, x1 lie in a sufficiently small closed intervalcontaining α on which f´(x), f´´(x) exist and are continuous and f’(x) does not vanish.Proof. Without loss of generality we assume that M2 defined by (4.10) is positive. Otherwise f´´(x) = 0 near a, implying that f(x) is a linear function and the secantrule converges in one step. With the assumptions on f´ and f´´, the bounds m1, m2,and M2 are well defined. Using the mean value theorem for derivatives, we see thatThis implies that the quantity ε defined above is less than 1 if x0 and x1 are sufficientlyclose to α. The argument above shows thatBut146CHAPTER 4ROOTS OF NONLINEAR EQUATIONSHence,This says thatmeanThe argument suggests that the rate of convergence is the goldenstated earlier.nMethods that converge at a rate r > 1 are said to be superlinearly convergent.
Wehave seen that this is the case for Newton’s method and the secant rule when computinga simple root. Unfortunately it is not the case when computing a multiple root. It iseasy enough to see this for Newton’s method. If xi is near a root α of multiplicitym > 1, thenThis implies thatThis expression shows that for a root of multiplicity m, Newton’s method is only linearly convergent with constant (m - 1)/m.An example from Wilkinson [11] illustrates several difficulties that can arise inthe practical application of Newton’s method.Example 4.3.Consider the problemx20 - l = 0.In attempting to compute the simple root α = 1 using Newton’s method, suppose westart with x0 = 1/2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
