5.3. Order of Convergence

We previously used the hypothesis that \(g\) (in the fixed point iteration \(x_{k+1}=g(x_k)\)) is a contraction to show that \(|x_k-a|\xrightarrow{k\rightarrow\infty}0\). Remember that the quantity

\[e=x_\texttt{approximate}-x_\texttt{exact}\]

was previously defined as the (absolute) error. In this case, let us define \(e_k=x_k-a\) (\(a\) is the solution, i.e., \(f(a)=0\)) as the error after the \(k\)-th iteration. If \(g\) is a contraction, we have

\[|e_{k+1}|=|x_{k+1}-a|=|g(x_k)-g(a)|\leq L|x_k-a|=L|e_k|\]

Since \(L<1\), the error shrinks at least by a constant factor at each iteration. In some cases, we can do even better. Remember the following theorem:

Theorem

If a function \(g\) is \(k\)-times differentiable, then:

\[g(y)=g(x) + g'(x)(y-x)+\frac{g''(x)}{2!}(y-x)^2+\frac{g'''(x)}{3!}(y-x)^3 + \ldots + \frac{g^{(k-1)}(x)}{(k-1)!}(y-x)^{k-1}+\frac{g^{(k)}(c)}{k!}(y-x)^k\]

for some number \(c\) between \(x\) and \(y\).

For \(k=1\), we simply obtain the mean value theorem:

\[g(y)=g(x)+g'(c)(y-x)\Leftrightarrow \frac{g(y)-g(x)}{y-x}=g'(c)\]

(for some \(c\) between \(x\) and \(y\)), which we used before to show that \(|g'(x)|\leq L<1\) implies that \(g\) is a contraction. We will now use the theorem in the case \(k=2\):

(1)\[g(y)=g(x)+g'(x)(y-x)+\frac{g''(c)}{2}(y-x)^2 \enspace\enspace \mbox{for some $c$ between $x$ and $y$}\]

Let \(g(x)=x-f(x)/f'(x)\) (as in Newton’s method). Now, let us make the following substitutions in the equation above:

\[x\leftarrow a \enspace \mbox{(the solution), and} \enspace y\leftarrow x_k\]

If \(f'(a)\neq 0\) and \(f''(a)\) is defined, then

\[g'(a)=\frac{\overbrace{f(a)}^{=0}f''(a)}{[f'(a)]^2}=0\]

Thus, equation (1) becomes

\[\begin{split}&g(x_k)& = g(a)+\frac{g''(c)}{2}(x_k-a)^2 \\ &\Rightarrow& x_{k+1}=a+\frac{g''(c)}{2}(x_k-a)^2 \\ &\Rightarrow& |x_{k+1}-a|=\left|\frac{g''(c)}{2}\right||x_k-a|^2\end{split}\]

(2)\[\Rightarrow |e_{k+1}|\leq C|e_k|^2 \enspace\enspace \mbox{note the exponent!}\]

where

\[C\equiv \max\left|\frac{g''(x)}{2}\right|_{\mbox{$x$ between $a$ and $x_k$}}\]

Compare equation (2) with the general guarantee

(3)\[|e_{k+1}|\leq L|e_k|\]

for contractions:

• Equation (3) depends on \(L<1\) to reduce the error. In equation (2), even if \(C\) is larger than one, if \(e_k\) is small enough then \(e_{k+1}\) will be reduced. Consider for example, the case \(C=10\), \(|e_k|=10^{-3}\) which will guarantee \(|e_{k+1}|\leq 10^{-5}\), and \(|e_{k+2}|\leq 10^{-9}\) in the next iteration.

• Equation (3) implies that every iteration adds a fixed number (or, a fixed fraction) of correct significant digits. For example, if \(L=0.3\):

  \[|e_{k+2}|\leq 0.3|e_{k+1}|\leq 0.09|e_k|\]

  Thus, we gain \(1\) significant digit every \(2\) iterations.

More generally, if an iterative scheme for solving \(f(x)=0\) can guarantee that

\[|e_{k+1}|\leq L|e_k|^d\]

then the exponent \(d\) (which can be a fractional number too) is called the order of convergence. Specifically:

• If \(d=1\), we shall also require that \(L<1\) in order to guarantee that the error \(e_k\) is being reduced. In this case, we say that the method exhibits linear convergence.
• If \(d>1\), we no longer need \(L<1\) as a strict condition for convergence (although we need to be “close enough” to the solution to guarantee progress). This case is described as superlinear convergence. The case \(d=2\) is referred to as quadratic convergence, the case \(d=3\) is referred to as cubic convergence, and so on.

We previously saw that Newton’s method converges quadratically. More generally, for the fixed point iteration \(x_{k+1}=g(x_k)\), if we can show that \(g'(a)=0\) (where \(a\) is the solution), then Taylor’s second order formula yields the same result as in equation (2), and the fixed point iteration converges quadratically.