Order and rate of convergence

Iteration is a common approach used in a wide variety of numerical methods. It is the hope that from some initial guess $x_0$ of the solution of a given problem, an iteration in the general form of $x_{n+1}=g(x_n)$ will eventually converge to the true solution $x^*$ at the limit $n\rightarrow\infty$, i.e.,

$\displaystyle g(x^*)=x^*$ (69)

This point $x^*$ is also called a fixed point. The concern is whether this iteration will converge, and, if so, how quickly or slowly, measured by the rate of convergence in terms of the error $e_n=x_n-x^*$:

$\displaystyle \lim_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\vert e_n\vert...
...m_{n\rightarrow\infty}\frac{\vert x_{n+1}-x^*\vert}{\vert x_n-x^*\vert^p}=\mu>0$ (70)

where $p\ge 1$ is the order of convergence. We assume when $n$ is large enough, the error is much smaller than 1, i.e., $e_n \ll 1$.

This expression may be better understood when it is interpreted as $\vert e_{n+1}\vert=\mu \vert e_n\vert^p$ when $n\rightarrow\infty$. Obviously, the larger $p$ and the smaller $\mu$, the smaller $e_{n+1}$ and the more quickly the sequence converges. Specifically, the convergence is

The iteration $x_{n+1}=g(x_n)$ can be written in terms of the errors $e_{n+1}$ and $e_n$. Consider the Taylor expansion around the true solution now denoted by $x=x^*$:

$\displaystyle x_{n+1}=x+e_{n+1}=g(x_n)=g(x+e_n)=g(x)+g'(x)e_n+\frac{1}{2}g''(x)e_n^2+
\cdots$ (71)

Subtracting $g(x)=x$ from both sides, we get

$\displaystyle e_{n+1}=x_{n+1}-x=g'(x)e_n+\frac{1}{2!}g''(x)e_n^2+\frac{1}{3!}g'''(x)e_n^3+\cdots$ (72)

At the limit $n\rightarrow\infty$, $e_n \ll 1$ and all non-linear terms approach zero, we have

$\displaystyle \lim_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\vert e_n\vert}\le\vert g'(x)\vert$ (73)

If $0<\vert g'(x)\vert<1$, then the convergence is linear. However, if $g'(x)=0$, then

$\displaystyle e_{n+1}=\frac{1}{2}g''(x)e_n^2+\cdots,\;\;\;\;\;\;$and$\displaystyle \;\;\;\;\;\;
\lim_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\vert e_n\vert^2}\le\frac{1}{2}\vert g''(x)\vert$ (74)

the convergence is quadratic. Moreover, if $g''(x)=0$, then

$\displaystyle e_{n+1}=\frac{1}{6}g'''(x)e_n^3+\cdots,\;\;\;\;\;\;$and$\displaystyle \;\;\;\;\;\;
\lim\limits_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\vert e_n\vert^3}\le\frac{1}{6}\vert g'''(x)\vert$ (75)

the convergence is cubic. We see that more lower order terms of the iteration function vanish at the fixed point, the more quickly the iteration converges.

Examples: All iterations below converge to zero, but their order and rate of convergence are different:

From these examples we see that there is a unique exponent $p\ge 0$, the order of convergence, so that

$\displaystyle \lim\limits_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\vert e...
=\left\{\begin{array}{cc}0 & q<p\\ \mu & q=p\\ \infty & q>p\end{array}\right.$ (79)

In practice, the true solution $x^*$ is unknown and so is the error $e_n=x_n-x^*$. However, the convergence can still be estimated, if the convergence is superlinear, i.e., it satisfies

$\displaystyle \lim\limits_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\vert e...
...\limits_{n\rightarrow\infty}\frac{\vert x_{n+1}-x^*\vert}{\vert x_n-x^*\vert}=0$ (80)

    $\displaystyle \lim\limits_{n\rightarrow\infty}\frac{\vert x_{n+1}-x_n\vert}{\ve...
...s_{n\rightarrow\infty}\frac{\vert x_{n+1}-x^*+x^*-x_n\vert}{\vert x_n-x^*\vert}$  
  $\displaystyle =$ $\displaystyle \lim\limits_{n\rightarrow\infty}\frac{\vert x_{n+1}-x^*\vert}{\ve...
...limits_{n\rightarrow\infty}\frac{\vert x^*-x_n\vert}{\vert x_n-x^*\vert}
=0+1=1$ (81)

i.e., when $n\rightarrow\infty$,

$\displaystyle \vert e_n\vert=\vert x_n-x^*\vert \approx \vert x_{n+1}-x_n\vert$ (82)

The order $p$ and rate $\mu$ of convergence can be estimated by

$\displaystyle \vert e_{n+1}\vert\le \mu \;\vert e_n\vert^p$ (83)