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