interval halving converges linearly

Theorem 1.

The interval halving algorithm converges linearly.

Proof.

To see that interval halving (or bisection) converges linearly we use the alternative definition of linear convergence that says that for some constant $1>c>0$.

In the case of interval halving, $|x_{i+1}-x_i|$ is the length of the interval we should search for the solution in and has $x_{i+2}$ as its midpoint. We have then that this interval has half the length of the previous interval which means, ${\mathrm{𝑙𝑒𝑛𝑔𝑡ℎ}}_{i+1}=\frac{1}{2}{\mathrm{𝑙𝑒𝑛𝑔𝑡ℎ}}_i$. Thus $c=1/2$ and we have exact linear convergence. ∎

Title	interval halving converges linearly
Canonical name	IntervalHalvingConvergesLinearly
Date of creation	2013-03-22 14:21:02
Last modified on	2013-03-22 14:21:02
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	14
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 49M15