info prev up next book cdrom email home

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.

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


\begin{displaymath}
r_n\equiv {\textstyle{1\over 2}}(a_n+b_n)
\end{displaymath} (2)


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


\begin{displaymath}
-n\ln 2<\ln\epsilon-\ln(b-a),
\end{displaymath} (4)

so
\begin{displaymath}
n > {\ln(b-a)-\ln\epsilon\over\ln 2}.
\end{displaymath} (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.




© 1996-9 Eric W. Weisstein
1999-05-26