Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 18
Текст из файла (страница 18)
Apparently, the smallerthe more rapidly en goes to zero asTheconvergence of fixed-point iteration should therefore be most rapid whenIf g(x) is twice-differentiable, we get from Taylor’s formula thatfor somebetweenand xn, that is, that(3.32)Hence, ifand g”(x) is continuous atthenfor large enough n(3.33)In this case, en+1 is (more or less) a quadratic function of en. We thereforesay that, in this case, x1, x2, . . .
converges quadratically toSuch an iteration function is obviously very desirable. The popularityof Newton’s method can be traced to the fact that its iteration function(3.34)is of this kind.Before proving that Newton’s method converges quadratically (when itconverges), we consider a simple example.Example Finding the positive square root of a positive number A is equivalent tofinding the positive solution of the equation f(x) = x2 - A = 0. Then f’(x) = 2x, andsubstituting into (3.34), we obtain the iteration function(3.35)for finding the square root of A, leading to the iteration(3.36)*3.5CONVERGENCE OF THE NEWTON AND SECANT METHODS101In particular, if A = 2 and x0, = 2, the result of fixed-point iteration with (3.36) isas follows:The sequence of iterates is evidently converging quite rapidly. The correspondingconverges toSince, for convergentsequence r1, r2, . .
. of ratiosfixed-point iteration,the example illustrates our assertion and showsthe very desirable rapid convergence of Newton’s method.We could show the quadratic convergence of Newton’s method byshowing that ifthen the iteration functionof Newton’s method is continuously differentiable in an open neighborhood ofConsequently, by the corollary to Theorem 3.1,there existssuch that fixed-point iteration with g(x) converges tofor any choice of x0 such thatBut it seems more efficient toprove the quadratic convergence directly and at the same time establish aconvergence proof of the secant method.The error in Newton’s method and in the secant method can bederived at the same time.
Both methods interpolate the function f(x) at twopoints, sayby a straight line,whose zerois then taken as the next approximation to the actual zero of f(x). In thesecant method we takeand then producewhilein Newton’s method we takeIn either case we know from (2.37) thatThis equation holds for all x.
If we now set x =and thereforethe desired zero, then102THE SOLUTION OF NONLINEAR EQUATIONSSolving now for theon the left side we obtainor(3.37)Equation (3.37) can now be used to obtain the error equations for theNewton and secant methods. For Newton’s method we setand recalling thatwe obtain from (3.37)(3.38)Recalling also that f[x n , x n ] = f'(x n ) and thatsomebetween xn and we can rewrite (3.38) asfor(3.38 a)This equation shows that Newton’s method converges quadratically sinceen+1 is approximately proportional to the square of en.To establish the error equation for the secant method we setin (3.37) and thus obtain(3.39)This equation shows that the error in the (n + 1)st iterate is approximatelyproportional to the product of the nth and (n - 1)st errors. Also sinceandsome points between xn-1 xn andthen for n large enough (3.39) becomes(3.39a)To be more precise about the concept of order of convergence, we makethe following definition:Definition 3.1: Order of convergence Let x0, x1, x2, .
. . be a sequencewhich converges to a number and setIf there exists anumber p and a constantsuch thatthen p is called the order of convergence of the sequence and C iscalled the asymptotic error constant.*3.5CONVERGENCE OF THE NEWTON AND SECANT METHODS103For fixed-point iteration in general based on x = g(x) we haveso that the order of convergence is one and the asymptotic error constantisFor Newton’s method we see from (3.38a) thatprovided thatso that by the definition its order of convergence is2 and the asymptotic error constant isTo determine the order of convergence of the secant method we firstnote that from (3.39a)(3.40)We seek a number p such thatfor some nonzero constant C.Now from (3.40)(3.41)provided thatand alsoi.e., provided thatThe equation p2 - p - 1 = 0 has the simple positive root p =With this choice of p and ofwesee that (3.41) defines a “fixed-point-like iteration”whereIt follows that yn converges to the fixed point of the equationwhose solution ismethodsince 1 + l/p = p.
This shows that for the secantfor large n(3.42)with p = 1.618 · · · ; i.e., the order of convergence of the secant method isp = 1.618 · · · and the asymptotic error constant is104THE SOLUTION OF NONLINEAR EQUATIONSThis says that the secant method converges more rapidly than the usualfixed-point iteration but less rapidly than the Newton method.Example 3.5 using data from Example 3.2, verify the error formulas (3.39a) and (3.42)for the secant method.In Example 3.2a we give the secant iterates for the positive root of x3 - x - 1 =0. In the table below we calculate |en| and |en+1|/|enen-1| for n - 2, 3, 4, assuming thatthe value of correct to eight decimal digits isIf we compute directly the constantwe obtain 0.93188 · · · , which agreesvery closely with the ratio |en+1/enen-1| for n = 4.It can be shown directly that, ifcontinuously differentiable, thenand f”(x) is twicewhereis the Newton iteration function.
It then follows by the corollary toTheorem 3.1 that if x0 is chosen “close enough” tothe Newton iterationwill converge. The phrase “close enough” is not very precisely defined, andindeed Newton’s method will frequently diverge or, when it does converge,converge to another zero than the one being sought. It would be desirableto establish conditions which guarantee convergence for any choice of theinitial iterate in a given interval. One such set of conditions is contained inthe following theorem.Theorem 3.2 Let f(x) be twice continuously differentiable on theclosed finite interval [a,b] and let the following conditions be satisfied:*3.5.CONVERGENCE OF THE NEWTON AND SECANT METHODS105Then Newton’s method converges to the unique solutionin [a,b] for any choice ofSome comments about these conditions may be appropriate.Conditions (i) and (ii) guarantee that there is one and only onesolution in [a,b].
Condition (iii) states that the graph of f(x) is eitherconcave from above or concave from below, and furthermore togetherwith condition (ii) implies that f’(x) is monotone on [a,b]. Added to these,condition (iv) states that the tangent to the curve at either endpointintersects the x axis within the interval [a,b]. A proof of this theorem willnot be given here (see Exercise 3.5-7), but we do indicate why the theoremmight be true.
We assume without loss of generality that f(a) < 0. We canthen distinguish two cases:Case (b) reduces to case (a) if we replace f by -f. It therefore suffices toconsider case (a). Here the graph of f(x) has the appearance given in Fig.3.6. From the graph it is evident that, forthe resulting iteratesdecrease monotonely towhile, forfalls between and band then the subsequent iterates converge monotonely toExample 3.6 Find an interval containing the smallest positive zero of f(x) = e -x sin x and which satisfies the conditions of Theorem 3.2 for convergence of Newton’smethod.With f(x) = e -x - sin x, we have f’(x) = - e -x - cos x, f”(x) = e -x + sin x.We choose [a,b] = [0, 1].
Then since f(0) = 1, f(1) = - 0.47, we have f(a)f(b) < 0 soFigure 3.6 Newton convergence.106THE SOLUTION OF NONLINEAR EQUATIONSthat condition (i) is satisfied. Sincecondition (ii) is satisfied,and sincecondition (iii) is satisfied. Finally since f(0) = 1,f‘(0) = - 2, we haveand since f(1) = - 0.47 · · · , f’(1)= 0.90 · · · , we have |f(1)|/|f’(1)| = 0.52 · · · < 1, verifying condition (iv). Newton’siteration will therefore converge for any choice of x0 in [0, 1].The conditions of Theorem 3.2 are also sufficient to establish convergence of the secant method although the modes of convergence may bequite different from those of Newton’s method.
If we assume again thatf’(x) > 0 and f”(x) > 0 on the interval [a,b] as shown in Fig. 3.6a, thenthere are essentially two different modes of convergence, depending uponwhere the initial points x0 and x1 are selected. In the first and simplermode, if x0 and x1 are selected in the intervalthen convergence willbe monotone from the right as in Newton’s method. The student can verifythis geometrically by drawing some typical curves meeting the conditionsof Theorem 3.2.If, however, we select one point, say x0, in the intervaland thepoint x1 in the intervalthen the next iterate x2 will lie also in theintervalwhile the iterate x3 will fall to the right ofAt this point wewill again have two successive iterates, x3 and x2, which straddle the rootand the entire sequence will be repeated.
Convergence thus occurs in awaltz with an iterate on one side followed by two iterates on the other. SeeFig. 3.6a for an illustration of this type of convergence.Example 3.7 Examine the mode of convergence of the secant method as applied to thefunction f(x) = ex - 3.Obviously f’(x) > 0, f”(x) > 0 for all x. Furthermore, the endpoint conditions ofTheorem 3.2 are satisfied, for example, in the interval [0,5].
Hence, f(x) has a zero inthat interval, namelyand we expect convergence if we selectThen we get the iterates below, thus verifying the waltzingmode of convergence:*3.5CONVERGENCE OF THE NEWTON AND SECANT METHODS107Figure 3.6a Secant convergence.If we chooseinstead, then we get the iteratesthus illustrating the monotone mode of convergence.From a computational point of view, the accuracy attainable withNewton’s method depends upon the accuracy to which f(x)/f’(x) can becomputed.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
