Numerical Analysis Home

Order of Convergence

    


In the preceding three sections we learned techniques to construct a sequence \(\{x_n\}\) that converges to the root \(x^*\) of a function. But the speed of their convergence are different. In this section we will compare them by their order of convergence.

Definition. The convergence of a sequence \(\{x_n\}\) to \(x^*\) is of order \(p\) if \[\lim_{n\to \infty}\frac{|x_{n+1}-x^*|}{|x_n-x^*|^p}= \lim_{n\to \infty}\frac{\varepsilon_{n+1}}{\varepsilon_n^p}=c,\] for some constant \(c>0\).

For higher order convergence (i.e., larger \(p\)), the sequence converges more rapidly. The rate of convergence is called linear, quadratic, and superlinear if \(p=1\), \(p=2\), and \(1< p< 2\) respectively. We say \(\{x_n\}\) converges linearly, quadratically, or superlinearly to \(x^*\). In quadratic convergence, we have \(\varepsilon_{n+1}\approx c\varepsilon_n^2\) and then accuracy of \(x_n\) to \(x^*\) gets roughly double at each iteration.

Example. The sequence \(\{\frac{1}{2^n}\}\) converges linearly to \(0\). \[\lim_{n\to \infty}\frac{|2^{-(n+1)}-0|}{|2^{-n}-0|^p} =\lim_{n\to \infty}2^{pn-n-1} =\begin{cases} 0 &\text{if } p<1\\ 1/2 &\text{if } p=1\\ \infty &\text{if } p>1. \end{cases}\]

Example. The order of convergence of the Bisection Method is linear.

Recall that \[\varepsilon_n=|x^*-x_n|\leq \frac{b-a}{2^n}.\] So the rate of convergence of the sequence \(\{x_n\}\) is similar to (at least) that of \(\{\frac{1}{2^n}\}\). We denote this by \(x_n=x^*+O(\frac{1}{2^n})\). Since \(\{\frac{1}{2^n}\}\) converges linearly, \(\{x_n\}\) also converges linearly.

Example. The order of convergence of the Fixed Point Iteration is linear when \(g'(x^*)\neq 0\).

Consider the sequence \(\{x_n\}\), where \(x_{n+1}=g(x_n)\), that converges to \(x^*\) where \(g'(x^*)\neq 0\). We have shown before by applying the MVT on \(g\) on \([x^*,x_n]\), that we find \(\xi_n\in (x^*,x_n)\) such that \[x^*-x_{n+1}=g(x^*)-g(x_n)=g'(\xi_n)(x^*-x_n).\] Since \(\{x_n\}\) converges to \(x^*\) and \(\xi_n\in (x^*,x_n)\), \(\{\xi_n\}\) also converges to \(x^*\). Then \[\lim_{n\to \infty}\frac{|x^*-x_{n+1}|}{|x^*-x_n|} =\lim_{n\to \infty}|g'(\xi_n)| =|g'(\lim_{n\to \infty}\xi_n)| =|g'(x^*)|>0 \;\; (\text{Assuming continuity of } g').\; ◼\]

Example. The order of convergence of the Newton-Raphson Method to find a simple root is quadratic.

Recall that to find a simple root \(x^*\) of \(f\) (i.e., \(f'(x^*)\neq 0\)), we used the Fixed Point Iteration on \[g(x)=x-\frac{f(x)}{f'(x)}\] for any choice of the initial approximation \(x_0\in (x^*-\delta,x^*+\delta)\) for small \(\delta>0\). Also recall that since \(f(x^*)=0\) and \(f'(x^*)\neq 0\), \(g'(x^*)=0\). By Taylor's Theorem on \(g\) about \(x^*\), we get \[g(x)=g(x^*)+\frac{g'(x^*)}{1!}(x-x^*) +\frac{g''(\xi)}{2!}(x-x^*)^2,\] for some \(\xi\) between \(x\) and \(x^*\). For \(x=x_n\), we get \(\xi_n\) between \(x_n\) and \(x^*\) such that \[\begin{align*} & g(x_n)=g(x^*)+\frac{g'(x^*)}{1!}(x_n-x^*) +\frac{g''(\xi_n)}{2!}(x_n-x^*)^2\\ \implies &x_{n+1}= x^*+\frac{g'(x^*)}{1!}(x_n-x^*) +\frac{g''(\xi_n)}{2!}(x_n-x^*)^2\\ \implies &x_{n+1}-x^*=\frac{g''(\xi_n)}{2!}(x_n-x^*)^2\;\; (\text{since }g'(x^*)=0)\\ \implies & \lim_{n\to \infty}\frac{|x_{n+1}-x^*|}{|x_n-x^*|^2}=\lim_{n\to \infty}\frac{|g''(\xi_n)|}{2!} =\frac{|g''\left(\displaystyle\lim_{n\to \infty}\xi_n\right)|}{2!}\;\; (\text{Assuming continuity of } g'') \end{align*}\] Since \(\{x_n\}\) converges to \(x^*\) and \(\xi_n\) lies between \(x_n\) and \(x^*\), \(\{\xi_n\}\) also converges to \(x^*\). Thus \[\lim_{n\to \infty}\frac{|x_{n+1}-x^*|}{|x_n-x^*|^2} =\frac{|g''(x^*)|}{2} =\frac{|f''(x^*)|}{2|f'(x^*)|}. \; ◼\]

Remark.

  1. If the root is not simple, the Newton-Raphson Method still may converge but the order of convergence is not quadratic but linear. For example, to approximate the double root zero of \(f(x)=x^2\) using \(x_0=1\) by the Newton-Raphson Method, it constructs the sequence \(\{\frac{1}{2^n}\}\) which converges to \(0\) linearly.

  2. A modified Newton-Raphson Method to find a multiple root has linear convergence.

  3. The order of convergence of the Secant Method is superlinear (\(p=(1+\sqrt{5})/2\approx 1.6\)) which is in between that of the Bisection Method and the Newton-Raphson Method. (Proof skipped)


Last edited