interval halving converges linearly

Theorem 1.

The interval halving algorithm converges linearly.


To see that interval halving (or bisection) converges linearly we use the alternative definition of linear convergence that says that |xi+1-xi|<cโข|xi-xi-1| for some constant 1>c>0.

In the case of interval halving, |xi+1-xi| is the length of the intervalMathworldPlanetmath we should search for the solution in and has xi+2 as its midpointMathworldPlanetmathPlanetmathPlanetmath. We have then that this interval has half the length of the previous interval which means, ๐‘™๐‘’๐‘›๐‘”๐‘กโ„Ži+1=12โข๐‘™๐‘’๐‘›๐‘”๐‘กโ„Ž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