2.4: Order of Convergence

Let $r$ be the root and $x_{n}$ be the $n$th approximation to the root. Define the error as

$$\epsilon_{n}=r-x_{n} \nonumber$$

If for large $n$ we have the approximate relationship

$$\left|\epsilon_{n+1}\right|=k\left|\epsilon_{n}\right|^{p}, \nonumber$$

with $k$ a positive constant, then we say the root-finding numerical method is of order $p$. Larger values of $p$ correspond to faster convergence to the root. The order of convergence of bisection is one: the error is reduced by approximately a factor of 2 with each iteration so that

$$\left|\epsilon_{n+1}\right|=\frac{1}{2}\left|\epsilon_{n}\right| . \nonumber$$

We now find the order of convergence for Newton’s Method and for the Secant Method.

2.4.1. Newton’s Method

We start with Newton’s Method

$$x_{n+1}=x_{n}-\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} \nonumber$$

Subtracting both sides from $r$, we have

$$r-x_{n+1}=r-x_{n}+\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} \nonumber$$

Or

$$\epsilon_{n+1}=\epsilon_{n}+\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} \nonumber$$

We use Taylor series to expand the functions $f\left(x_{n}\right)$ and $f^{\prime}\left(x_{n}\right)$ about the root $r$, using $f(r)=0$. We have

$$\begin{aligned} f\left(x_{n}\right) &=f(r)+\left(x_{n}-r\right) f^{\prime}(r)+\frac{1}{2}\left(x_{n}-r\right)^{2} f^{\prime \prime}(r)+\ldots, \\ &=-\epsilon_{n} f^{\prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)+\ldots ; \\ f^{\prime}\left(x_{n}\right) &=f^{\prime}(r)+\left(x_{n}-r\right) f^{\prime \prime}(r)+\frac{1}{2}\left(x_{n}-r\right)^{2} f^{\prime \prime \prime}(r)+\ldots, \\ &=f^{\prime}(r)-\epsilon_{n} f^{\prime \prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime \prime}(r)+\ldots \end{aligned} \nonumber$$

To make further progress, we will make use of the following standard Taylor series:

$$\frac{1}{1-\epsilon}=1+\epsilon+\epsilon^{2}+\ldots, \nonumber$$

which converges for $|\epsilon|<1 .$ Substituting $(2.2)$ into $(2.1)$, and using $(2.3)$ yields

$$\begin{aligned} \epsilon_{n+1} &=\epsilon_{n}+\frac{f\left(x_{n}\right)}{f^{\prime}\left(x_{n}\right)} \\ &=\epsilon_{n}+\frac{-\epsilon_{n} f^{\prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)+\ldots}{f^{\prime}(r)-\epsilon_{n} f^{\prime \prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime \prime}(r)+\ldots} \\ &=\epsilon_{n}+\frac{-\epsilon_{n}+\frac{1}{2} \epsilon_{n}^{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots}{1-\epsilon_{n} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots} \\ &=\epsilon_{n}+\left(-\epsilon_{n}+\frac{1}{2} \epsilon_{n}^{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots\right)\left(1+\epsilon_{n} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots\right) \\ &=\epsilon_{n}+\left(-\epsilon_{n}+\epsilon_{n}^{2}\left(\frac{1}{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}-\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right)+\ldots\right) \\ &=-\frac{1}{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)} \epsilon_{n}^{2}+\ldots \end{aligned} \nonumber$$

Therefore, we have shown that

$$\left|\epsilon_{n+1}\right|=k\left|\epsilon_{n}\right|^{2} \nonumber$$

as $n \rightarrow \infty$, with

$$k=\frac{1}{2}\left|\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right| \nonumber$$

provided $f^{\prime}(r) \neq 0 .$ Newton’s method is thus of order 2 at simple roots.

2.4.2. Secant Method

Determining the order of the Secant Method proceeds in a similar fashion. We start with

$$x_{n+1}=x_{n}-\frac{\left(x_{n}-x_{n-1}\right) f\left(x_{n}\right)}{f\left(x_{n}\right)-f\left(x_{n-1}\right)} \nonumber$$

We subtract both sides from $r$ and make use of

$$\begin{aligned} x_{n}-x_{n-1} &=\left(r-x_{n-1}\right)-\left(r-x_{n}\right) \\ &=\epsilon_{n-1}-\epsilon_{n} \end{aligned} \nonumber$$

and the Taylor series

$$\begin{aligned} f\left(x_{n}\right) &=-\epsilon_{n} f^{\prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)+\ldots, \\ f\left(x_{n-1}\right) &=-\epsilon_{n-1} f^{\prime}(r)+\frac{1}{2} \epsilon_{n-1}^{2} f^{\prime \prime}(r)+\ldots, \end{aligned} \nonumber$$

so that

$$\begin{aligned} f\left(x_{n}\right)-f\left(x_{n-1}\right) &=\left(\epsilon_{n-1}-\epsilon_{n}\right) f^{\prime}(r)+\frac{1}{2}\left(\epsilon_{n}^{2}-\epsilon_{n-1}^{2}\right) f^{\prime \prime}(r)+\ldots \\ &=\left(\epsilon_{n-1}-\epsilon_{n}\right)\left(f^{\prime}(r)-\frac{1}{2}\left(\epsilon_{n-1}+\epsilon_{n}\right) f^{\prime \prime}(r)+\ldots\right) \end{aligned} \nonumber$$

We therefore have

$$\begin{aligned} \epsilon_{n+1} &=\epsilon_{n}+\frac{-\epsilon_{n} f^{\prime}(r)+\frac{1}{2} \epsilon_{n}^{2} f^{\prime \prime}(r)+\ldots}{f^{\prime}(r)-\frac{1}{2}\left(\epsilon_{n-1}+\epsilon_{n}\right) f^{\prime \prime}(r)+\ldots} \\ &=\epsilon_{n}-\epsilon_{n} \frac{1-\frac{1}{2} \epsilon_{n} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots}{1-\frac{1}{2}\left(\epsilon_{n-1}+\epsilon_{n}\right) \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots} \\ &=\epsilon_{n}-\epsilon_{n}\left(1-\frac{1}{2} \epsilon_{n} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots\right)\left(1+\frac{1}{2}\left(\epsilon_{n-1}+\epsilon_{n}\right) \frac{f^{\prime \prime}(r)}{f^{\prime}(r)}+\ldots\right) \\ &=-\frac{1}{2} \frac{f^{\prime \prime}(r)}{f^{\prime}(r)} \epsilon_{n-1} \epsilon_{n}+\ldots, \end{aligned} \nonumber$$

or to leading order

$$\left|\epsilon_{n+1}\right|=\frac{1}{2}\left|\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right|\left|\epsilon_{n-1}\right|\left|\epsilon_{n}\right| \nonumber$$

The order of convergence is not yet obvious from this equation, and to determine the scaling law we look for a solution of the form

$$\left|\epsilon_{n+1}\right|=k\left|\epsilon_{n}\right|^{p} . \nonumber$$

From this ansatz, we also have

$$\left|\epsilon_{n}\right|=k\left|\epsilon_{n-1}\right|^{p} \nonumber$$

and therefore

$$\left|\epsilon_{n+1}\right|=k^{p+1}\left|\epsilon_{n-1}\right|^{p^{2}} \nonumber$$

Substitution into $(2.4)$ results in

$$k^{p+1}\left|\epsilon_{n-1}\right|^{p^{2}}=\frac{k}{2}\left|\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right|\left|\epsilon_{n-1}\right|^{p+1} \nonumber$$

Equating the coefficient and the power of $\epsilon_{n-1}$ results in

$$k^{p}=\frac{1}{2}\left|\frac{f^{\prime \prime}(r)}{f^{\prime}(r)}\right| \nonumber$$

and

$$p^{2}=p+1 \nonumber$$

The order of convergence of the Secant Method, given by $p$, therefore is determined to be the positive root of the quadratic equation $p^{2}-p-1=0$, or

$$p=\frac{1+\sqrt{5}}{2} \approx 1.618 \nonumber$$

which coincidentally is a famous irrational number that is called The Golden Ratio, and goes by the symbol $\Phi$. We see that the Secant Method has an order of convergence lying between the Bisection Method and Newton’s Method.