DerivationNonlinear equationsbasic

Derivation: bisection error bound

Why the bisection error halves at every iteration, and how to predict in advance how many iterations a given tolerance requires.

The error halves

  1. After kk bisections, the interval [ak,bk][a_k,b_k] still contains the root and is half the size of the previous one:

    bk−ak=b−a2kb_k-a_k=\frac{b-a}{2^k}

  2. The approximation is the midpoint mkm_k, and the root lies in one of the two halves, at distance at most half the interval:

    ∣mk−α∣≤bk−ak2=b−a2k+1|m_k-\alpha|\le\frac{b_k-a_k}{2}=\frac{b-a}{2^{k+1}}

  3. To guarantee ∣mk−α∣<ε|m_k-\alpha|<\varepsilon, solve for kk in b−a2k+1<ε\frac{b-a}{2^{k+1}}<\varepsilon: the number of iterations is known before starting, something no other method in this area offers.

    k>log⁡2 ⁣(b−aε)−1k>\log_2\!\left(\frac{b-a}{\varepsilon}\right)-1