2.4: Order of Convergence
- Last updated
- May 31, 2022
- Save as PDF
( \newcommand{\kernel}{\mathrm{null}\,}\)
Let r be the root and xn be the nth approximation to the root. Define the error as
ϵn=r−xn
If for large n we have the approximate relationship
|ϵn+1|=k|ϵn|p,
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
|ϵn+1|=12|ϵn|.
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
xn+1=xn−f(xn)f′(xn)
Subtracting both sides from r, we have
r−xn+1=r−xn+f(xn)f′(xn)
Or
ϵn+1=ϵn+f(xn)f′(xn)
We use Taylor series to expand the functions f(xn) and f′(xn) about the root r, using f(r)=0. We have
f(xn)=f(r)+(xn−r)f′(r)+12(xn−r)2f′′(r)+…,=−ϵnf′(r)+12ϵ2nf′′(r)+…;f′(xn)=f′(r)+(xn−r)f′′(r)+12(xn−r)2f′′′(r)+…,=f′(r)−ϵnf′′(r)+12ϵ2nf′′′(r)+…
To make further progress, we will make use of the following standard Taylor series:
11−ϵ=1+ϵ+ϵ2+…,
which converges for |ϵ|<1. Substituting (2.2) into (2.1), and using (2.3) yields
ϵn+1=ϵn+f(xn)f′(xn)=ϵn+−ϵnf′(r)+12ϵ2nf′′(r)+…f′(r)−ϵnf′′(r)+12ϵ2nf′′′(r)+…=ϵn+−ϵn+12ϵ2nf′′(r)f′(r)+…1−ϵnf′′(r)f′(r)+…=ϵn+(−ϵn+12ϵ2nf′′(r)f′(r)+…)(1+ϵnf′′(r)f′(r)+…)=ϵn+(−ϵn+ϵ2n(12f′′(r)f′(r)−f′′(r)f′(r))+…)=−12f′′(r)f′(r)ϵ2n+…
Therefore, we have shown that
|ϵn+1|=k|ϵn|2
as n→∞, with
k=12|f′′(r)f′(r)|
provided f′(r)≠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
xn+1=xn−(xn−xn−1)f(xn)f(xn)−f(xn−1)
We subtract both sides from r and make use of
xn−xn−1=(r−xn−1)−(r−xn)=ϵn−1−ϵn
and the Taylor series
f(xn)=−ϵnf′(r)+12ϵ2nf′′(r)+…,f(xn−1)=−ϵn−1f′(r)+12ϵ2n−1f′′(r)+…,
so that
f(xn)−f(xn−1)=(ϵn−1−ϵn)f′(r)+12(ϵ2n−ϵ2n−1)f′′(r)+…=(ϵn−1−ϵn)(f′(r)−12(ϵn−1+ϵn)f′′(r)+…)
We therefore have
ϵn+1=ϵn+−ϵnf′(r)+12ϵ2nf′′(r)+…f′(r)−12(ϵn−1+ϵn)f′′(r)+…=ϵn−ϵn1−12ϵnf′′(r)f′(r)+…1−12(ϵn−1+ϵn)f′′(r)f′(r)+…=ϵn−ϵn(1−12ϵnf′′(r)f′(r)+…)(1+12(ϵn−1+ϵn)f′′(r)f′(r)+…)=−12f′′(r)f′(r)ϵn−1ϵn+…,
or to leading order
|ϵn+1|=12|f′′(r)f′(r)||ϵn−1||ϵn|
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
|ϵn+1|=k|ϵn|p.
From this ansatz, we also have
|ϵn|=k|ϵn−1|p
and therefore
|ϵn+1|=kp+1|ϵn−1|p2
Substitution into (2.4) results in
kp+1|ϵn−1|p2=k2|f′′(r)f′(r)||ϵn−1|p+1
Equating the coefficient and the power of ϵn−1 results in
kp=12|f′′(r)f′(r)|
and
p2=p+1
The order of convergence of the Secant Method, given by p, therefore is determined to be the positive root of the quadratic equation p2−p−1=0, or
p=1+√52≈1.618
which coincidentally is a famous irrational number that is called The Golden Ratio, and goes by the symbol Φ. We see that the Secant Method has an order of convergence lying between the Bisection Method and Newton’s Method.
