## You are here

Homeinterval halving converges linearly

## Primary tabs

# 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 $|x_{{i+1}}-x_{i}|<c|x_{i}-x_{{i-1}}|$ 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, $\mathit{length}_{{i+1}}=\frac{1}{2}\mathit{length}_{i}$. Thus $c=1/2$ and we have exact linear convergence. ∎

Major Section:

Reference

Type of Math Object:

Theorem

Parent:

## Mathematics Subject Classification

49M15*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Corrections

converges by alozano ✓

wrong type by Mathprof ✓

wrong type by Mathprof ✓

Typo by everweb ✓

please change this a little by Mathprof ✓

wrong type by Mathprof ✓

wrong type by Mathprof ✓

Typo by everweb ✓

please change this a little by Mathprof ✓