Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 17
Текст из файла (страница 17)
Indeed, if we take x0 = 0, thenwhich clearly converges to the root3.3FIXED-POINT ITERATION93As a more realistic example, we consider the transcendental equation(3.20)The most natural rearrangement here isso that g(x) = 2 sin x. An examination of the curves y = g(x) and y = xshows that there is a root betweenandFurther,3Hence ifandthen Assumption 3.1 issatisfied. Finally, g’(x) = 2 cos x strictly decreases from 1 to -1 as xincreases fromIt follows that Assumption 3.3 is satisfiedwheneverIn conclusion, fixed-point iteration with g(x) = 2 sin x converges to the unique solution of (3.20) inExample 33 Write a program which uses fixed-point iteration to find the smallestpositive zero of the function f(x) = e -x - sin x.The first step is to select an iteration function and an initial value which will leadto a convergent iteration. We rewrite f(x) = 0 in the formNow since f(0.5) = 0.127 · · · and f(0.7) = -0.147 · · · the smallest positive zero liesin the interval I = [0.5, 0.7].
To verify that g(x) is a convergent iteration function wenote that withg’(0.5) = -0.48 · · · , g’(0.7) = -0.26 · · · and since g’(x) is a monotone function onI, we haveIt can similarly be verified that 0.5 < g(x) < 0.7 for allHence fixed-point iteration will converge if x0 is chosen in I.The program below was run on a CDC 6500. Note that successful termination ofthis program requires that both of the following error tests be satisfiedThe program also terminates if the convergence tests are not satisfied within 20iterations.C PROGRAM FOR EXAMPLE 3.3INTEGER JREALERROR,FTOL,XNEW,XOLD,XTOL,YCC THIS PROGRAM SOLVES THE EQUATIONEXP(-X) = SIN(X)C BY FIXED POINT ITERATION, USING THE ITERATION FUNCTIONG(X) = EXP(-X) - SIN(X) + XCDATA XTOL, FTOL / 1.E-8, 1.E-8 /PRINT 600600 FORMAT(9X,'XNEW',l2X,'F(XNEW)',10X,'ERROR')XOLD = .6Y = G(XOLD) - XOLDPRINT 601, XOLD,Y94THE SOLUTION OF NONLINEAR EQUATIONS601FORMAT(3X,3E16.8)DO 10 J=1,20XNEW = G(XOLD)Y = G(XNEW) - XNEWERROR = ABS(XNEW - XOLD)/ABS(XNEW)PRINT 601, XNEW,Y,ERRORIF (ERROR .LT.
XTOL .OR. ABS(Y) .LT. FTOL) STOPXOLD = XNEW10 CONTINUEPRINT 610610 FORMAT(' FAILED TO CONVERGE IN 20 ITERATIONS ’ )STOPENDOUTPUT FOR EXAMPLE 3.3EXERCISES3.3-1 Verify that the iterationwill converge to the solutionof the equationonly if, for some n0, all iterates xn with n > n0 are equal to 2, i.e., only “accidentally.”3.3-2 For each of the following equations determine an iteration function (and an interval I)so that the conditions of Theorem 3.1 are satisfied (assume that it is desired to find thesmallest positive root):3.3-3 Write a program based on Algorithm 3.6 and use this program to calculate the smallestroots of the equations given in Exercise 3.3-2.3.4CONVERGENCE ACCELERATION FOR FIXED-POINT ITERATlON3.3-4 Determine the largest interval I with the following property: For alliteration with the iteration function95fixed-pointconverges, when started with x0.
Are Assumptions 3.1 and 3.3 satisfied for your choice of I ?What numbers are possible limits of this iteration? Can you think of a good reason for usingthis particular iteration? Note that the interval depends on the constant a.3.3-5 Same as Exercise 3.3-4, but with g(x) = (x + a/x) /2.3.3-6 The functionsatisfies Assumption 3.1 forandAssumption 3.3 on any finite interval, yet fixed-point iteration with this iteration functiondoes not converge.
Why?3.3-7 The equation ex - 4x2 = 0 has a root between x = 4 and x = 5. Show that we cannotfind this root using fixed point iteration with the “natural” iteration functionCan you find an iteration function which will correctly locate this root?3.3-8 The equation e x - 4x2 = 0 also has a root between x = 0 and x = l. Show that thewill converge to this root if x0 is chosen in the interval [0, 1].iteration function23.4 CONVERGENCE ACCELERATION FOR FIXED-POINTITERATIONIn this section, we investigate the rate of convergence of fixed-pointiteration and show how information about the rate of convergence can beused at times to accelerate convergence.We assume that the iteration function g(x) is continuously differentiable and that, starting with some point x0, the sequence x1, x2, .
. . generated by fixed-point iteration converges to some point This point is thena fixed point of g(x), and we have, by (3.19), that(3.21)for somebetweenfollows thatand xn, n = 1, 2, . . . . Sincehenceit theng’(x) being continuous, by assumption. Consequently,(3.22)whereHence, ifthen for large enough n,(3.23)i.e., the error en+1 in the (n + 1)st iterate depends (more or less) linearly onthe error en in the nth iterate. We therefore say that x0, x1, x2, .
. .converges linearly toNow note that we can solve (3.21) forFor(3.24)96THE SOLUTION OF NONLINEAR EQUATIONSgivesTherefore(3.25)Of course, we do not know the numberBut we know that the ratio(3.26)for somebetween xn and xn-1, by the mean-value theorem for derivatives.
For large enough n, therefore, we haveand then the point(3.27)should be a very much better approximation toThis can also be seen graphically. In effectsolving (3.24) forafter replacingby thecalling the solutionThus= g(xn), this shows thatis a fixed point of thethan is xn or xn+1.we obtained (3.27) bynumber g[xn-1 , xn ] andSince xn+1straight lineThis we recognize as the linear interpolant to g(x) at xn-1, xn.
If now theslope of g(x) varies little between xn-1 andthat is, if g(x) is approximately a straight line between xn-1 andthen the secant s(x) should be avery good approximation to g(x) in that interval; hence the fixed pointof the secant should be a very good approximation to the fixed point ofg(x); see Fig. 3.5.In practice, we will not be able to prove that any particular xn is “closeenough” toto makea better approximation to than is xn or xn+1. Butwe can test the hypothesis that xn is “close enough” by checking the ratiosrn-1, rn. If the ratios are approximately constant, we accept the hypothesisthat the slope of g(x) varies little in the interval of interest; hence webelieve that the secant s(x) is a good enough approximation to g(x) tomakea very much better approximation to than is xn.
In particular, wethen acceptas a good estimate for the error |en|.3.4CONVERGENCE ACCELERATlON FOR FIXED-POINT ITERATION97Figure 3.5 Convergence acceleration for fixed-point iteration.Example 3.4 The equation(3.28)has a rootWe choose the iteration functionand starting with x 0 = 0, generate the sequence x 1 , x 2 , . . . by fixed-point iteration.Some of the xn are listed in the table below. The sequence seems to converge, slowly butsurely, toWe also calculate the sequence of ratios rn.
These too are listed in the table.Specifically, we findwhich we think is “sufficiently” constant to conclude that, for allis a betterapproximation to than is xn. This is confirmed in the table, where we have also listedtheWhether or not any particularxn, one can prove that the sequenceis a better approximation to than isconverges faster tothan98THE SOLUTION OF NONLINEAR EQUATIONSdoes the original sequence x0, x1, . . .
; that is,(3.29)[See Sec. 1.6 for the definition of o( ).]This process of deriving from a linearly converging sequenceby (3.27) is usuallyx0, x1, x2, . . . a faster converging sequencecalled Aitken’s process. Using the abbreviationsfrom Sec. 2.6, (3.27) can be expressed in the form(3.30)therefore the nameprocess.” This process is applicable to any linearlyconvergent sequence, whether generated by fixed-point iteration or not.Algorithm 3.7: Aitken’sprocess Given a sequence x0, x1, x2, .
. .converging tocalculate the sequenceby (3.30).If the sequence x0, x1, x2, . . . converges linearly to that is, ifif starting from a certain k on, the sequenceof difference ratios is approximatelyconstant, thencan be assumed to be a better approximation tothan is xk. In particular,is then a good estimate for the errorFurthermore,If, in the case of fixed-point iteration, we decide that a certainis avery much better approximation to than is xk, then it is certainly wastefulto continue generating xk+1, xk+2, etc. It seems more reasonable to startfixed-point iteration afresh withas the initial guess. This leads to thefollowing algorithm.Algorithm 3.8: Steffensen iteration Given the iteration function g(x)and a point y0.3.4CONVERGENCE ACCELERATION FOR FIXED-POINT ITERATION99One step of this algorithm consists of two steps of fixed-point iterationfollowed by one application of (3.27), using the three iterates available toget the starting value for the next step.We have listed in the table above the yn, generated by this algorithmapplied to Example 3.4.
Already y3 is accurate to all places shown.EXERCISES3.4-1 Assume that the error of a fixed-point iteration satisfies the recurrence relationfor some constant k, |k| < 1. Find an expression for the number of iterations N required toreduce the initial error e0 by a factor 10- m (m > 0).3.4-2 Fixed-point iteration applied to the equationproduced the successive approximations given in the following table:Use the Aitken Algorithm 3.7 to compute an accelerated sequenceFrom the ratios rk calculate the approximate value ofand the ratios rk.3.4-3 Write a program to carry out Steffensen accelerated iteration (Algorithm 3.8).
Use thisprogram to compute the smallest positive zero of the function in Exercise 3.4-2 using theiteration function g(x) = 0.5 + 0.2 sin x and x0 = 0.5.3.4-4 In Sec. 3.3 we showed that the fixed-point iterationproduced the following sequence of approximations to the positive root of f(x) = x 2 - x- 2:Use Aitken’s Algorithm 3.7 to accelerate this sequence and note the improvement in the rateof convergence to the root3.4-5 Consider the iteration function g(x) = x - x 3 .
Find the unique fixed point of g(x).Prove that fixed-point iteration with this iteration function converges to the unique fixed100THE SOLUTION OF NONLINEAR EQUATIONSpoint(Hint: Use the fact that if x n < x n+1 < x n+2 < · · · c forsome constant c, then the sequence converges.) Is it true that, for some k < 1 and all n,|e n | < k|e n-1 |?*3.5 CONVERGENCE OF THE NEWTON AND SECANTMETHODSIn the preceding section, we proved that the error en, in the nth iterate xn offixed-point iteration satisfies(3.3 1)for large enough n, provided g(x) is continuously differentiable.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
