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.,

$$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^*$:

$$\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

• sublinear if $p=1$ and $\mu=1$, $\lim\limits_{n\rightarrow\infty} \vert e_{n+1}\vert=\vert e_n\vert$;
• linear if $p=1$ and $0<\mu<1$, $\vert e_{n+1}\vert=\mu\vert e_n\vert<\vert e_n\vert$, $e_n=\mu^n e_0$;
• superlinear if $p=1$ and $\mu=0$, or $p>1$ (with any $\mu>0$). In particular, the convergence is quadratic if $p=2$, $\vert e_{n+1}\vert=\mu\vert e_n\vert^2$, or cubic if $p=3$, $\vert e_{n+1}\vert=\mu\vert e_n\vert^3$, etc.

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^*$:

$$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

$$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

$$\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

$$e_{n+1}=\frac{1}{2}g''(x)e_n^2+\cdots,\;\;\;\;\;\; \;\;\;\;\;\; \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

$$e_{n+1}=\frac{1}{6}g'''(x)e_n^3+\cdots,\;\;\;\;\;\; \;\;\;\;\;\; \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:

• $\vert e_n\vert=1/n$, the sequence is $1,\;1/2,\;1/3,\;1/4,\;1/5,\; \cdots$

  $$\frac{\vert e_{n+1}\vert}{\vert e_n\vert^p}=\frac{1/(n+1)}{1/n^p}... ...row} \left\{\begin{array}{cc}0 & p<1\\ 1 & p=1\\ \infty & p>1\end{array}\right.$$ (76)

  This is a sub-linear convergence as only when $p=1$ will the limit be a constant $\mu=1$.

• $\vert e_n\vert=1/2^n$, the sequence is $1/2,\; 1/4,\; 1/8,\; 1/16,\; 1/32,\; \cdots$

  $$\frac{\vert e_{n+1}\vert}{\vert e_n\vert^p}=\frac{2^{np}}{2^{n+1}... ...w} \left\{\begin{array}{cc}0 & p<1\\ 1/2 & p=1\\ \infty & p>1\end{array}\right.$$ (77)

  This is a linear convergence of order $p=1$ and rate $\mu=1/2$.
• $\vert e_n\vert=1/2^{2^n}$, the sequence is $1/4,\; 1/16,\; 1/256,\;1/65536,\; \cdots$

  $$\frac{\vert e_{n+1}\vert}{\vert e_n\vert^p}=\frac{1/2^{2^{n+1}}}{... ...row} \left\{\begin{array}{cc}0 & p<2\\ 1 & p=2\\ \infty & p>2\end{array}\right.$$ (78)

  This is quadratic (superlinear) convergence of order $p=2$ and rate $1$.

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

$$\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

$$\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)

Consider:

$$\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}$$

$$= \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$,

$$\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

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