next up previous
Next: Summary Up: Other Iterative Schemes Previous: Other Iterative Schemes

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

\begin{displaymath}
x_{n} = r - \epsilon_{n}, \qquad x_{n+1} = r - \epsilon_{n+1},
\end{displaymath}

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

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

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

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

However, remembering that the root $r$ is a fixed-point and so satisfies $r = G(r)$, the leading term in the Taylor series gives
\begin{displaymath}
\epsilon_{n+1} \approx G^{\prime}(r)\epsilon_{n}.
\end{displaymath} (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

\begin{displaymath}
\epsilon_{1} \approx G^{\prime}(r)\epsilon_{0}.
\end{displaymath}

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
\begin{displaymath}
\epsilon_{n} \approx \left [G^{\prime}(r)\right ]^{n}\epsilon_{0}.
\end{displaymath} (1.16)

(1.16) shows us that When the scheme converges we can see that

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

\begin{displaymath}
x_{n+1} = e^{-x_{n}} = G(x_{n}),
\end{displaymath}

we have $r \approx 0.567$

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

Thus,

\begin{displaymath}
\left \vert G^{\prime}(r)\right \vert < 1,
\end{displaymath}

and so the scheme converges.

However, if you use the scheme

\begin{displaymath}
x_{n+1} = - \log(x_{n}) = G(x_{n}),
\end{displaymath}

we have

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

In this case we have

\begin{displaymath}
\left \vert G^{\prime}(r)\right \vert > 1,
\end{displaymath}

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

    \begin{displaymath}
x = \sqrt{2x + 3}, \qquad \Rightarrow \qquad x_{n+1} =
\sqrt{2x_{n} + 3}.
\end{displaymath}

    Hence, $G(x) = (2x + 3)^{1/2}$ and

    \begin{displaymath}
G^{\prime}(x) = {1\over 2}\left (2x + 3\right )^{-1/2}.2 = {1\over
(2x + 3)^{1/2}}.
\end{displaymath}

    Thus,

  2. Express as $x(x-2) - 3 = 0$. Thus,

    \begin{displaymath}
x = {3\over x-2}, \qquad \Rightarrow \qquad x_{n+1} = {3\over x_{n}
-2}.
\end{displaymath}

    In this example $G(x) = 3/(x-2)$ and so

    \begin{displaymath}
G^{\prime}(x) = -{3\over (x-2)^{2}}.
\end{displaymath}

    Thus,

  3. Finally, express as $x^{2} - 3 = 2x$, so that

    \begin{displaymath}
x = {x^{2}-3\over 2}, \qquad \Rightarrow \qquad x_{n+1} =
{x_{n}^{2} -3 \over 2}.
\end{displaymath}

    Here we have $G(x) = (x^{2} - 3)/2$ and so

    \begin{displaymath}
G^{\prime}(x) = x.
\end{displaymath}

    So the convergence condition gives

next up previous
Next: Summary Up: Other Iterative Schemes Previous: Other Iterative Schemes
Prof. Alan Hood
2000-02-01