Bisection Procedure

Given an interval $[a,b]$, let $a_n$ and $b_n$ be the endpoints at the $n$th iteration and $r_n$ be the $n$th approximate solution. Then, the number of iterations required to obtain an error smaller than $\epsilon$ is found as follows.

$$b_n-a_n = {1\over 2^{n-1}} (b-a)$$ (1)

$$r_n\equiv {\textstyle{1\over 2}}(a_n+b_n)$$ (2)

$$\vert r_n-r\vert \leq {\textstyle{1\over 2}}(b_n-a_n)=2^{-n}(b-a) < \epsilon$$ (3)

$$-n\ln 2<\ln\epsilon-\ln(b-a),$$ (4)

so

$$n > {\ln(b-a)-\ln\epsilon\over\ln 2}.$$ (5)

See also Root

References

Arfken, G. Mathematical Methods for Physicists, 3rd ed. Orlando, FL: Academic Press, pp. 964-965, 1985.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. ``Bracketing and Bisection.'' §9.1 in Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 343-347, 1992.