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 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.
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.
A modified Newton-Raphson Method to find a multiple root has linear convergence.
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)