Convergence of Fixed-Point Iteration, Error Analysis

As in section 1.3.2, we use a Taylor series expansion to see how the error behaves from one step to another. Again we take

$$x_{n} = r - \epsilon_{n}, \qquad x_{n+1} = r - \epsilon_{n+1},$$

where $r$ is the exact value of the root, $x_{n}$ is the value of the $n^{th}$ iterate and $\epsilon_{n}$ is the error after $n$ iterations. Hence, fixed-point iteration can be written as

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

If $\epsilon_{n}$ is small we may expand the function $G$ in a Taylor series about $r$. Hence,

$$r - \epsilon_{n+1} = G(r) - \epsilon_{n}G^{\prime}(r) + \epsilon_{n}^{2}{G^{\prime\prime}(r)\over 2} + \cdots$$

However, remembering that the root $r$ is a fixed-point and so satisfies $r = G(r)$, the leading term in the Taylor series gives

$$\epsilon_{n+1} \approx G^{\prime}(r)\epsilon_{n}.$$ (1.15)

(1.15) shows us that fixed-point iteration is a first-order scheme provided $G^{\prime}(r) \ne 0$. We can use (1.15) to see if the scheme converges or not.

Assume that the initial error is $\epsilon_{0}$. Then (1.15) gives

$$\epsilon_{1} \approx G^{\prime}(r)\epsilon_{0}.$$

Repeated use of (1.15) gives

$$\begin{eqnarray*} \epsilon_{2} & \approx &G^{\prime}(r)\epsilon_{1} \approx \le... ...silon_{3} \approx \left [G^{\prime}(r)\right ]^{4}\epsilon_{0} \end{eqnarray*}$$

From these first few terms it is clear that in general

$$\epsilon_{n} \approx \left [G^{\prime}(r)\right ]^{n}\epsilon_{0}.$$ (1.16)

(1.16) shows us that

• the error reduces if $\vert G^{\prime}(r)\vert < 1$, the scheme converges,

• the error increases if $\vert G^{\prime}(r)\vert > 1$, the scheme diverges.

When the scheme converges we can see that

• the error decreases monotonically if $0\le G^{\prime}(r) < 1$,

• the error decreases in an oscillatory manner if $-1 < G^{\prime}(r) < 0$.

Example 1. .7Consider the previous example with $F(x) = x - e^{-x}$. Using the scheme

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

we have $r \approx 0.567$

$$G^{\prime}(x) = - e^{-x}, \qquad \Rightarrow \qquad G^{\prime}(r) = - e^{-0.567} = -0.567.$$

Thus,

$$\left \vert G^{\prime}(r)\right \vert < 1,$$

and so the scheme converges.

However, if you use the scheme

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

we have

$$G^{\prime}(x) = -{1\over x}, \qquad \Rightarrow \qquad G^{\prime}(r) = -{1\over 0.567} = - 1.7637.$$

In this case we have

$$\left \vert G^{\prime}(r)\right \vert > 1,$$

and the scheme does not converge.

Example 1. .8Consider $F(x) = x^{2} - 2x -3$. The roots are $x=-1$ and $x=3$. We will express $F(x) = 0$ in three different forms and test the convergence criterion for each form.

1. Express as $x^{2} = 2x + 3$. Hence, we have
   
   $$x = \sqrt{2x + 3}, \qquad \Rightarrow \qquad x_{n+1} = \sqrt{2x_{n} + 3}.$$
   
   
   Hence, $G(x) = (2x + 3)^{1/2}$ and
   
   $$G^{\prime}(x) = {1\over 2}\left (2x + 3\right )^{-1/2}.2 = {1\over (2x + 3)^{1/2}}.$$
   
   
   Thus,
   • $G^{\prime}(-1) = 1$, the scheme will NOT converge.

   • $G^{\prime}(3) = {1\over 3} < 1$, the scheme will converge to the root at $x=3$.

2. Express as $x(x-2) - 3 = 0$. Thus,
   
   $$x = {3\over x-2}, \qquad \Rightarrow \qquad x_{n+1} = {3\over x_{n} -2}.$$
   
   
   In this example $G(x) = 3/(x-2)$ and so
   
   $$G^{\prime}(x) = -{3\over (x-2)^{2}}.$$
   
   
   Thus,
   • $G^{\prime}(-1) = -{1\over 3}$, the scheme converges to $x=-1$.

   • $G^{\prime}(3) = -3$, this scheme does not converge to $x=3$.

3. Finally, express as $x^{2} - 3 = 2x$, so that
   
   $$x = {x^{2}-3\over 2}, \qquad \Rightarrow \qquad x_{n+1} = {x_{n}^{2} -3 \over 2}.$$
   
   
   Here we have $G(x) = (x^{2} - 3)/2$ and so
   
   $$G^{\prime}(x) = x.$$
   
   
   So the convergence condition gives
   • $G^{\prime}(-1) = -1$ so does not converge to $x=-1$.

   • $G^{\prime}(3) = 3$ and again the iterative scheme does not converge.