2.1 Error analysis for iterative methods#

Assume we have an iterative method \(\{p_{n}\}\) that converges to the root \(p\) of some function. How can we assess the rate of convergence?

Definition 5

Suppose \(\{p_{n}\}\) converges to \(p\). If there are constants \(C>0\) and \(\alpha >1\) such that

(3)#\[|p_{n+1}-p| \leq C |p_{n}-p|^{\alpha},\]

for \(n\geq 1\), then we say \(\{p_{n}\}\) converges to \(p\) with order \(\alpha\).

Special cases:

  • If \(\alpha=1\) and \(C<1\), we say the convergence is linear, and the rate of convergence is \(C\). In this case, using induction, we can show

(4)#\[|p_{n+1}-p| \leq C^n |p_{1}-p|.\]

There are some methods for which Equation (4) holds, but Equation (3) does not hold for any \(C<1\). We still call these methods to be of linear convergence. An example is the bisection method.

  • If \(\alpha>1\), we say the convergence is superlinear. In particular, the case \(\alpha=2\) is called quadratic convergence.

Example 12

Consider the sequences defined by

\[\begin{align*} p_{n+1}&=0.7 p_n \text{ and } p_1=1\\ p_{n+1}&=0.7 p^2_n \text{ and } p_1=1. \end{align*}\]

The first sequence converges to 0 linearly, and the second quadratically. Here are a few iterations of the sequences:

\[\begin{equation*} \begin{array}{ccc} n & \text{Linear} & \text{Quadratic} \\ \hline 1 & 0.7 & 0.7\\ 4 & 0.24 & 4.75\times10^{-3}\\ 8 & 5.76\times10^{-2} & 3.16\times10^{-40}\\ \end{array} \end{equation*}\]

Observe how fast quadratic convergence is compared to linear convergence.