Convergence of iteration schemes

NUMERICAL METHODS
Of the four methods mentioned, no single one is ideal, and, in practice, some
mixture of them is usually to be preferred. The particular combination of methods
selected will depend a great deal on how easily the progress of the calculation
may be monitored, but some combination of the first three methods mentioned,
followed by the NR scheme if great accuracy were required, would be suitable
for most situations.
27.2 Convergence of iteration schemes
For iteration schemes in which xn+1 can be expressed as a differentiable function
of xn , for example the rearrangement or NR methods of the previous section, a
partial analysis of the conditions necessary for a successful scheme can be made
as follows.
Suppose the general iteration formula is expressed as
xn+1 = F(xn )
(27.13)
((27.7) and (27.12) are examples). Then the sequence of values x1 , x2 , . . . , xn , . . . is
required to converge to the value ξ that satisfies both
f(ξ) = 0
and
ξ = F(ξ).
(27.14)
If the error in the solution at the nth stage is n , i.e. xn = ξ + n , then
ξ + n+1 = xn+1 = F(xn ) = F(ξ + n ).
(27.15)
For the iteration process to converge, a decreasing error is required, i.e. |n+1 | <
|n |. To see what this implies about F, we expand the right-hand term of (27.15)
by means of a Taylor series and use (27.14) to replace (27.15) by
ξ + n+1 = ξ + n F (ξ) + 12 2n F (ξ) + · · · .
(27.16)
This shows that, for small n ,
n+1 ≈ F (ξ)n
and that a necessary (but not sufficient) condition for convergence is that
|F (ξ)| < 1.
(27.17)
It should be noted that this is a condition on F (ξ) and not on f (ξ), which
may have any finite value. Figure 27.3 illustrates in a graphical way how the
convergence proceeds for the case 0 < F (ξ) < 1.
Equation (27.16) suggests that if F(x) can be chosen so that F (ξ) = 0 then the
ratio |n+1 /n | could be made very small, of order n in fact. To go even further,
if it can be arranged that the first few derivatives of F vanish at x = ξ then the
992
27.2 CONVERGENCE OF ITERATION SCHEMES
y
y=x
y = F(x)
ξ
xn
xn+1 xn+2
x
Figure 27.3 Illustration of the convergence of the iteration scheme xn+1 =
F(xn ) when 0 < F (ξ) < 1, where ξ = F(ξ). The line y = x makes an angle
π/4 with the axes. The broken line makes an angle tan−1 F (ξ) with the x-axis.
convergence, once xn has become close to ξ, could be very rapid indeed. If the
first N − 1 derivatives of F vanish at x = ξ, i.e.
F (ξ) = F (ξ) = · · · = F (N−1) (ξ) = 0
(27.18)
n+1 = O(N
n ),
(27.19)
and consequently
then the scheme is said to have Nth-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 function F is 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, provided f (ξ) = 0, it follows that F (ξ) = 0 because f(x) = 0 at x = ξ.
993