Other Iterative Schemes

The Newton-Raphson method is an iterative scheme of the general form

$$x_{n+1} = G(x_{n}),$$

where

$$G(x_{n}) = x_{n} - {F(x_{n})\over F^{\prime}(x_{n})}.$$

It is possible to construct other iterative schemes that have a similar form to this by rearranging the equation F(x) = 0 into the form

$$F(x) = 0 \qquad \Rightarrow \qquad x - G(x) = 0.$$

Then a possible iterative scheme is

$$x_{n+1} = G(x_{n}).$$ (1.14)

Will (1.14) converge to the root of the function $F$? If we can show that

$$x_{n} \rightarrow r \hbox{ as } n \rightarrow \infty,$$

then so does

$$x_{n+1} \rightarrow r.$$

Thus, $r$ is a solution to

$$r = G(r),$$

and so

$$F(r) = 0.$$

Thus, $r$ is a root of $F$. $r$ is called a fixed point of the function $G$. The advantage of this approach is that it is easy to obtain an iterative scheme of the form (1.14) but the problem is that not all schemes converge.

Example 1. .6Consider

$$F(x) = x - e^{-x}.$$

Since we are looking for the value of $x$ that makes $F(x) = 0$ we can set

$$x = e^{-x}.$$

If we can find the value of $x$ that makes the left hand side equal the right hand side, then we have found the root of the original function $F$. So we try as our iterative scheme

$$x_{n+1} = G(x_{n}) \qquad \Rightarrow \qquad x_{n+1} = e^{-x_{n}}.$$

Here we have chosen $G(x) = e^{-x}$. The iterations, assuming an initial guess of $x_{0} = 1$, are shown in Table 1.5.

Table 1.5: The iteration obtained using $x_{n+1} = e^{-x_{n}}$.

n	$x_{n}$	$\epsilon_{n}= \vert r - x_{n}\vert$	$\epsilon_{n+1}/\epsilon_{n}$
0	1	0.4329
1	0.3679	0.1993	0.4603
2	0.6922	0.1251	0.6276
3	0.5005	0.0667	0.5331
4	0.6062	0.0391	0.5865
5	0.5454	0.0217	0.5562

Looking at the first two columns we see that the method is converging but only very slowly. If fact we would need 24 iterations to get an answer as accurate as the one obtained by 4 iterations with the Newton-Raphson method. The root obtained by Newton-Raphson is approximately given by

$$r \approx 0.567143.$$

Using this value, the absolute value of the absolute error is calculated in column 3 and it is clear that the error is reducing as more and more iterations are used. The final column takes the ratio of two successive absolute errors. There is an indication that the ratio is tending towards a constant value. Thus,

$${\epsilon_{n+1}\over \epsilon_{n}} = \hbox{ constant},\qquad \Rightarrow \qquad \epsilon_{n+1} \approx C \epsilon_{n},$$

where the constant of proportionality $C$ is about 0.56.

This fixed-point iteration scheme is illustrated in Figure 1.4.

Figure 1.4: Fixed-point iteration.

Taking the initial guess $x_{0}$, we obtain the value of $e^{-x_{0}}$. This means we move from the $x$-axis at $x_{0}$ up to the curve $y = e^{-x}$. From this curve, we move horizontally until we meet the line $y = x$ and this value of $x$ is the next estimate $x_{1}$. This procedure is repeated, move up to the curve $y = e^{-x}$ and then move along to the line $y = x$ to get the next estimate.

Note that we could rearrange the function $F(x) = x - e^{-x}$ in the following manner.

$$x = e^{-x}, \qquad \Rightarrow \qquad \log x = -x,\qquad \Rightarrow \qquad x = -\log x.$$

Hence, another fixed-point iterative scheme is

$$x_{n+1} = - \log(x_{n}),$$

but this does not converge. To understand why we need to perform an error analysis for fixed-point iteration.