Conte, de Boor - Elementary Numerical Analysis. An Algorithmic Approach (523140), страница 16
Текст из файла (страница 16)
Repair this flaw in the subroutine, usingthe FORTRAN function SIGN. Also, is it necessary to update the value of FA each time A ischanged?3.2-3 Prove that the function f(x) = ex - 1 - x - x2 /2 has exactly one zero, namely,(Hint: Use the remainder in a Taylor expansion for e x around 0.) Then evaluate theFORTRAN functionfor various values of the argument X "near” zero to show that this function has many signchanges, hence many zeros, “near” X = 0.
What can you conclude from these facts,specifically, as regards the bisection method, and more generally, as regards the (theoretical)concept of a “zero of a function”?3.2-4 Suppose you are to find that root of the equation tan x - x which is closest to 50, usingthe secant method and nine-decimal-digit floating-point arithmetic. Would it be “reasonable’*to use the termination criterion |f((xn)| < 10-8?3.2-5 Binary search The problem of table lookup consists in finding, for given X, an integer Isuch that X lies between TABLE (I) and TABLE (I + I), where TABLE is a givenone-dimensional array containing an increasing (or a decreasing) sequence.
Write a FORTRAN subprogram which utilizes the bisection method to carry out this search efficiently.How many times does your routine compare X with an entry of TABLE if TABLE has nentries?88THE SOLUTION OF NONLINEAR EQUATIONS3.2-6 Write a subroutine for the secant method based on the form (3.7). Allow for termination using either of the relative error criteria (3.14). Also in computing the relative error|x n - x n - 1 | < XTOL*|xn| do not recompute the difference xn - xn-1 but rather use thecorrection from the previous iteration.3.2-7 Write a subroutine for Newton’s method. Be sure to provide an exit in the event thatf’(xn) = 0. In addition to the termination criteria (3.13) or (3.14), provision for terminationshould also be made in the event of nonconvergence after a given number NTOL ofiterations.3.2-8 Find the smallest positive root of each of the following equations to maximum precisionon your computer using Algorithms 3.1, 3.3, 3.4 and 3.5.
Compare your results, the number ofiterations required and the accuracy attained.3.2-9 Solve the equation in Example 3.26 by Newton’s method using the parameter values(I,q) = (10-7, 30). Try to solve this equation using various starting values between 0 and 4and note the effect on convergence or divergence.3.3 FIXED-POINT ITERATIONIn Sec. 3.1, we mentioned fixed-point iteration as a possible method forobtaining a root of the equation(3.15)In this method, one derives from (3.15) an equation of the form(3.16)so that any solution of (3.16), i.e., any fixed point of g(x), is a solution of(3.15). This may be accomplished in many ways. If, for example,(3.17)then among possible choices for g(x) are the following:(3.18)for some nonzero constant mEach such g(x) is called an iteration function for solving (3.15) [with f(x)given by (3.17)].
Once an iteration function g(x) for solving (3.15) ischosen, one carries out the following algorithm.3.3FIXED-POINT ITERATION89Algorithm 3.6: Fixed-point iteration Given an iteration function g(x)and a starting point x0For this algorithm to be useful, we must prove:(i) For the given starting point x 0 , we can calculate successivelyx1, x2, . . . .(ii) The sequence x1, x2, . . .
converges to some point(iii) The limitis a fixed point of g(x), that is,The example of the real-valued functionshows that (i) is not a trivial requirement. For in this case, g(x) is definedonly for x > 0. Starting with any x0 > 0, we get x1 = g(x0) < 0; hence wecannot calculate x2. To settle (i), we make the following assumption.Assumption 3.1 There is an interval I = [a, b] such that, for allg(x) is defined andthat is, the function g(x) maps I intoitself.It follows from this assumption, by induction on n, that ifthenfor allhence xn+1 = g(xn) is defined and is in I.We discussed (iii) already, in Sec.
3.1. For we proved there that (iii)holds if g(x) is continuous. Hence, to settle (iii), we make Assumption 3.2.Assumption 3.2 The iteration function g(x) is continuous on I = [a, b].We note that Assumptions 3.1 and 3.2 together imply that g(x) has afixed point in I = [a, b]. For if either g(a) = a or g(b) = b, this is obviously so. Otherwise, we haveandBut by Assumption3.1, both g(a) and g(b) are in I = [a, b]; hence g(a) > a and g(b) < b. Thisimplies that the function h(x) = g(x) - x satisfies h(a) > 0, h(b) < 0.Since h(x) is continuous on I, by Assumption 3.2, h(x) must thereforevanish somewhere in I, by the intermediate-value theorem for continuousfunctions (see Sec. 1.7).
But this says that g(x) has a fixed point in I, andproves the assertion.For the discussion of (ii) concerning convergence, it is instructive tocarry out the iteration graphically. This can be done as follows. Sincexn = g(xn-1), the point {xn-1, xn} lies on the graph of g(x). To locate90THE SOLUTION OF NONLINEAR EQUATIONS{xn, xn+1} from {xn-1, xn}, draw the straight line through {xn-1, xn}parallel to the x axis. This line intersects the line y = x at the point{xn, xn}. Through this point, draw the straight line parallel to the y axis.This line intersects the graph y = g(x) of g(x) at the point {xn, g(xn)}.
Butsince g(xn) = xn+1, this is the desired point {xn, xn+1}. In Fig. 3.4, we havecarried out the first few steps of fixed-point iteration for four typical cases.Note thatis a fixed point of g(x) if and only if y = g(x) and y = xintersect atAs Fig. 3.4 shows, fixed-point iteration may well fail to converge, as itdoes in Fig. 3.4a and d. Whether or not the iteration converges [given thatg(x) has a fixed point] seems to depend on the slope of g(x). If the slope ofg(x) is too large in absolute value, near a fixed pointof g(x), then wecannot hope for convergence to that fixed point.
We therefore makeAssumption 3.3.Assumption 3.3 The iteration function is differentiable on I = [a,b].Further, there exists a nonnegative constant K < 1 such thatNote that Assumption 3.3 implies Assumption 3.2, since a differentiafunctionis, in particular, continuous.bleTheorem 3.1 Let g(x) be an iteration function satisfying Assumptions3.1 and 3.3. Then g(x) has exactly one fixed pointin I, and startingwith any point x0 in I, the sequence x1 , x2 , .
. . generated by fixedpoint iteration of Algorithm 3.6 converges toTo prove this theorem, recall that we haveistence of a fixed point for g(x) in I. Now let x0as we remarked earlier, fixed-point iterationx1, x2, . . . of points all lying in I, by Assumptionthe nth iterate byThen sincealready proved the exbe any point in I. Then,generates a sequence3.1. Denote the error inand xn = g(xn-1 ), we have(3.19)for somebetweenand xn-1 by the mean-value theorem for derivatives(see Sec.
1.7). Hence by Assumption 3.3,It follows by induction on n that3.3FIXED-POINT ITERATION91IFigure 3.4 Fixed-point iteration.regardless of the initial error e0. But this says that x1, x2, . . . converges toIt also proves that is the only fixed point of g(x) in I.
For if, also, is afixed point of g(x) in I, then withwe should havehence |eo| = |el| < K|e0|. Since K < 1, this then impliesThis completes the proof.It is often quite difficult to verify Assumption 3.1. In such a situation,the following weaker statement may at least assure success if the iterationis started “sufficiently close” to the fixed point.Corollary If g(x) is continuously differentiable in some open intervalcontaining the fixed point and ifthen there exists an92THE SOLUTION OF NONLINEAR EQUATIONSso that fixed-point iteration with g(x) converges wheneverIndeed, since g’(x) is continuous nearthere exists,for any K withfor every xwithFix one such K with its correspondingThen, forAssumption 3.3 is satisfied. As to Assumption 3.1, let xbe any point in I, thusThen, as in the proof of Theorem 3.1,for some pointbetween x andhence in I. But thenshowing that g(x) is in I if x is in I.
This verifies Assumption 3.1, and theconclusion now follows from Theorem 3.1.Because of this corollary, a fixed point for g(x), for whichis often called a point of attraction [for the iteration with g(x)] .We consider again the quadratic function f(x) = x2 - x - 2 of (3.17).The zeros of this function are 2 and -1. Suppose we wish to calculate theby fixed-point iteration. If we use the iteration function givenrootby (3.18a),then for x >g’(x) > 1.
It follows that Assumption 3.3 is not satisfied forany interval containingthat is,is not a point of attraction. Infact, one can prove for this example that, starting at any point x0 , thesequence x1, x2, , . . generated by this fixed-point iteration will convergeonly if, for some n0, xn = 2 for all n > n0; that is, iftois hit“accidentally” (see Exercise 3.3-1).On the other hand, if we choose (3.18b ), thenwhile, for exNow x > 0 implies g(x) > 0 andample, x < 7 impliesHence, with I =[0, 7], both Assumptions 3.1 and 3.3 are satisfied, and anyleads,therefore, to a convergent sequence.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
