Heath - Scientific Computing (523150), страница 44

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 44)

.........................................................2.............................. ........ ... ........ . .... ... ......................................... ....... ...... . ..... ... .......... ... ........... ........ ........... .........................................................................................................................y =x −23y=xy=x21003122103........................................................................................................................................................... ..... ....... ........

....... .......................................................................................................................................................................... ........................................ ....................................................... ...................................................................................................................................

......................... ......... ...................... ....... ............................................................3001231√x+223........................................................................................................................................................ ..... ....... ...x2 +2... .......

................ ...2x−1.......... ............. ..................................................................................................... ............................................. .......... ............................................ .......................................................... ......... ...................... ....... ............................................................y=2y=xy=x1y=0y = 1 + 2/x2.............................................................................................................................................................................................................................................................................

.................................. ......... ..... .................. ........ .........................................................10012Figure 5.4: Fixed-point iterations for some nonlinear functions.3158CHAPTER 5. NONLINEAR EQUATIONSthen the iterative scheme is locally convergent, i.e., there is an interval containing x∗ suchthat the corresponding iterative scheme is convergent if started within that interval.

If, onthe other hand, |g 0 (x∗ )| > 1, then the corresponding iterative scheme diverges.The proof of this result is simple and instructive, so we sketch it here. If x∗ is a fixedpoint, then for the error at the kth iteration we haveek+1 = xk+1 − x∗ = g(xk ) − g(x∗ ).By the Mean Value Theorem, there is a point θk between xk and x∗ such thatg(xk ) − g(x∗ ) = g 0 (θk )(xk − x∗ ),so thatek+1 = g 0 (θk )ek .We do not know the value of θk , but if |g 0 (x∗ )| < 1, then by starting the iterations closeenough to x∗ , we can be assured that there is a constant C such that |g 0 (θk )| ≤ C < 1, fork = 0, 1, .

. . . Thus, we have|ek+1 | ≤ C|ek | ≤ · · · ≤ C k |e0 |,and since C k → 0, then |ek | → 0 and the sequence converges.As we can see from the proof, the asymptotic convergence rate of a fixed-point iterationscheme is usually linear, with constant C = |g 0 (x∗ )|. The smaller the constant, the fasterthe convergence, so ideally we would like to have g 0 (x∗ ) = 0, in which case a similar proofshows that the convergence rate is at least quadratic. We will next see a systematic way ofchoosing g so that this occurs.5.2.3Newton’s MethodThe bisection technique makes no use of the function values other than their signs, whichresults in sure but slow convergence. More rapidly convergent methods can be derived byusing the function values to obtain a more accurate approximation to the solution at eachiteration.

In particular, the truncated Taylor seriesf (x + h) ≈ f (x) + f 0 (x)his a linear function of h that approximates f near a given x. We can therefore replacethe nonlinear function f with this linear function, whose zero is easily determined to beh = −f (x)/f 0 (x), assuming that f 0 (x) 6= 0. Of course, the zeros of the two functions arenot identical in general, so we repeat the process. This motivates the following iterationscheme, known as Newton’s method :xk+1 = xk − f (xk )/f 0 (xk ).Newton’s method can be interpreted as approximating the function f near xk by the tangentline at f (xk ).

We can then take the next approximate solution to be the zero of this linearfunction, and repeat the process. Newton’s method is illustrated in Fig. 5.5.5.2. NONLINEAR EQUATIONS IN ONE DIMENSION159.............................................. ...... ........ ......... ........................... ..... .......... ............ .......................................................................... ............................................................................................k.................................................x↑xk+1Figure 5.5: Newton’s method for solving a nonlinear equation.Example 5.6 Newton’s Method. We illustrate Newton’s method by again finding aroot of the equationf (x) = x2 − 4 sin(x) = 0.The derivative of this function is given byf 0 (x) = 2x − 4 cos(x),so that the iteration scheme is given byxk+1 = xk −x2k − 4 sin(xk ).2xk − 4 cos(xk )Taking x0 = 3 as starting value, we get the sequence of iterations shown next, whereh = −f (x)/f 0 (x) denotes the change in x at each iteration.

The iteration is terminatedwhen |h| is as small as desired relative to |x|.x3.0000002.1530581.9540391.9339721.933754f (x)8.4355201.2947720.1084380.0011520.000000f 0 (x)9.9599706.5057715.4037955.2889195.287670h−0.846942−0.199019−0.020067−0.0002180.000000We can view Newton’s method as a systematic way of transforming a nonlinear equationf (x) = 0 into a fixed-point problem x = g(x), whereg(x) = x − f (x)/f 0 (x).To study the convergence of this scheme, we therefore determine the derivativeg 0 (x) = f (x)f 00 (x)/(f 0 (x))2 .If x∗ is a simple root (i.e., f (x∗ ) = 0 and f 0 (x∗ ) 6= 0), then g 0 (x∗ ) = 0.

Thus, the asymptoticconvergence rate of Newton’s method for a simple root is quadratic, i.e., r = 2. We have160CHAPTER 5. NONLINEAR EQUATIONSalready seen an illustration of this: the fourth fixed-point iteration scheme in Example 5.5 isNewton’s method for solving that example equation (note that the fourth iteration functionin Fig. 5.4 has a horizontal tangent at the fixed point).The quadratic convergence rate of Newton’s method for a simple root means that asymptotically the error is squared at each iteration. Another way of stating this is that thenumber of digits of accuracy in the approximate solution is doubled at each iteration ofNewton’s method.

For a multiple root, on the other hand, Newton’s method is only linearlyconvergent [with constant C = 1 − (1/m), where m is the multiplicity]. It is important toremember, however, that these convergence results are only local, and Newton’s methodmay not converge at all unless started close enough to the solution. For example, a relativelysmall value for f 0 (xk ) (i.e., a nearly horizontal tangent) tends to cause the next iterate tolie far away from the current approximation.Example 5.7 Newton’s Method for Multiple Root.

Both types of behavior areshown in the following examples, where the first shows quadratic convergence to a simpleroot and the second shows linear convergence to a multiple root. The multiplicity for thesecond problem is 2, so C = 0.5.k0123455.2.4f (x) = x2 − 1xk2.01.251.0251.00031.000000051.0f (x) = x2 − 2x + 1xk2.01.51.251.1251.06251.03125Secant MethodOne drawback of Newton’s method is that both the function and its derivative must beevaluated at each iteration. The derivative may be inconvenient or expensive to evaluate,so we might consider approximating it by a finite difference quotient over some small stepsizeh, as in Example 1.11; but this would require a second evaluation of the function at eachiteration purely for the purpose of obtaining derivative information.

Характеристики

Список файлов книги