## 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.**

- 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)

Last edited