Mathematical Methods for Physics and Engineering : A Comprehensive Guide

27.2 CONVERGENCE OF ITERATION SCHEMES

xn xn+1xn+2

y=x

y=F(x)

ξ

x

y

Figure 27.3 Illustration of the convergence of the iteration schemexn+1=

F(xn)when0<F′(ξ)<1, whereξ=F(ξ). The liney=xmakes an angle

π/4 with the axes. The broken line makes an angle tan−^1 F′(ξ)withthex-axis.

convergence, oncexnhas become close toξ, could be very rapid indeed. If the

firstN−1 derivatives ofFvanish atx=ξ,i.e.

F′(ξ)=F′′(ξ)=···=F(N−1)(ξ) = 0 (27.18)

and consequently

n+1=O(Nn), (27.19)

then the scheme is said to haveNth-order convergence.

This is the explanation of the significant difference in convergence between the

NR scheme and the others discussed (judged by reference to (27.19), so that the

differentiability of the functionFis not a prerequisite). The NR procedure has

second-order convergence, as is shown by the following analysis. Since

F(x)=x−

f(x)

f′(x)

,

F′(x)=1−

f′(x)

f′(x)

+

f(x)f′′(x)

[f′(x)]^2

=

f(x)f′′(x)

[f′(x)]^2

.

Now, providedf′(ξ)= 0, it follows thatF′(ξ) = 0 becausef(x)=0atx=ξ.