Section 2.1 of Burden and Faires: Bisection

Convergence of Bisection

Theorem 2.1 Suppose that $f\in C[a,b]$ and $\left.f(a)*f(b)<0\right.$. The bisection method generates a sequence $\{r_{n}\}_{n=1}^{\infty }$ approximating a root $\left.r\right.$ of $\left.f\right.$ with

$|r_{n}-r|\leq {\frac {b-a}{2^{n}}}$,

when $n\geq 1$.

So, using the terminology of section 1.3, we'd say that the sequence $\{r_{n}\}_{n=1}^{\infty }$ converges to $\left.r\right.$ as $O\left({\frac {1}{2^{n}}}\right)$ with constant $\left.\kappa =b-a\right.$.

In the big picture, this means that we get one additional digit of binary accuracy with each iteration of bisection.