Order and rate of convergence

Iteration is a common approach widely used in various numerical methods. It is the hope that an iteration in the general form of $x_{n+1}=g(x_n)$ will eventually converge to the true solution $x^*$ of the problem at the limit when $n\rightarrow\infty$. The concern is whether this iteration will converge, and, if so, the rate of convergence. Specifically we use the following to represent how quickly the error $e_n=x_n-x^*$ converges to zero:

$$\lim\limits_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\v... ...\infty}\frac{\vert x_{n+1}-x^*\vert}{\vert x_n-x^*\vert^p}=\mu$$

Here $p\ge 1$ is called the order of convergence, the constant $\mu$ is the rate of convergence or asymptotic error constant.

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 more quickly the sequence converges. Specially, we consider the following cases:

• If $p=1$ and $0<\mu<1$, $\vert e_{n+1}\vert=\mu\vert e_n\vert<\vert e_n\vert$, then
  • if $\mu=1$, the convergence is sublinear
  • if $0<\mu<1$, the convergence is linear with the rate of convergence of $\mu$.
  • if $\mu=0$, the convergence is superlinear
• If $p=2$, $\vert e_{n+1}\vert=\mu\vert e_n\vert^2,\;\;(\mu>0)$, the convergence is quadratic.
• If $p=3$, $\vert e_{n+1}\vert=\mu\vert e_n\vert^3,\;\;(\mu>0)$, the convergence is cubic.

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:

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

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

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

At the limit $n\rightarrow\infty$, all higher order error terms become zero, we have

$$\lim\limits_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\vert e_n\vert}\e\vert g'(x)\vert$$

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

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

and we have

$$\lim\limits_{n\rightarrow\infty}\frac{\vert e_{n+1}\vert}{\vert e_n\vert^2}\le\frac{1}{2}\vert g''(x)\vert$$

the convergence is quadratic. We see that if the iteration function has zero derivative at the fixed point, the iteration may be accelerated.

Examples:

• $\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)}{... ...{array}{cc}0 & p<1 1 & p=1 \infty & p>1\end{array}\right.$$
  
  
  This is a sublinear 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... ...rray}{cc}0 & p<1 1/2 & p=1 \infty & p>1\end{array}\right.$$
  
  
  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... ...{array}{cc}0 & p<2 1 & p=2 \infty & p>2\end{array}\right.$$
  
  
  This is superlinear, specifically quadratic, 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}{\v... ...array}{cc}0 & q<p \mu & q=p \infty & q>p\end{array}\right.$$

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

$$\lim\limits_{n\rightarrow\infty}\frac{\vert x_{n+1}-x^*\vert}{\vert x_n-x^*\vert}=0$$

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

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

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

The order and rate of convergence can be estimated by

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