Convergence

Suppose our initial interval size, i.e., x₂-x₁, is given by I₀. Then after the 1st bisection the interval size I₁ = I₀/2, after the second bisection, I₂ = I₁/2 = I₀/4 etc. Generalizing, after the nth bisection,

I_n = I_n-1 / 2 = I₀ / (2ⁿ). (2)

So if the tolerance level is delta , then the number of bisections required to reduce the interval width to delta is given by

N_delta > log₂(I₀ / delta) (3)

Or in other words, if we think of the current interval size as the error, the error in the nth step is proportional to the error in the (n-1)th step. This is characteristic of a linearly convergent algorithm. We say that a method is linearly convergent if the error in the nth step is proportional to the error in the (n-1)th step raised to the first power, quadratically convergent if the error in the nth step is proportional to the error in the (n-1)th step raised to the second power, quartically convergent if raised to the fourth power, and so forth.