TOPICS
Search

Bisection


Bisection is the division of a given curve, figure, or interval into two equal parts (halves).

A simple bisection procedure for iteratively converging on a solution which is known to lie inside some interval [a,b] proceeds by evaluating the function in question at the midpoint of the original interval x=(a+b)/2 and testing to see in which of the subintervals [a,(a+b)/2] or [(a+b)/2,b] the solution lies. The procedure is then repeated with the new interval as often as needed to locate the solution to the desired accuracy.

Let a_n and b_n be the endpoints at the nth iteration (with a_1=a and b_1=b) and let r_n be the nth approximate solution. Then the number of iterations required to obtain an error smaller than epsilon is found by noting that

 b_n-a_n=(b-a)/(2^(n-1))
(1)

and that r_n is defined by

 r_n=1/2(a_n+b_n).
(2)

In order for the error to be smaller than epsilon,

 |r_n-r|<=1/2(b_n-a_n)=2^(-n)(b-a)<epsilon.
(3)

Taking the natural logarithm of both sides then gives

 -nln2<lnepsilon-ln(b-a),
(4)

so

 n>(ln(b-a)-lnepsilon)/(ln2).
(5)

See also

Angle Bisector, Brent's Method, Midpoint, Root, Root Bracketing, Root-Finding Algorithm

Explore with Wolfram|Alpha

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.

Referenced on Wolfram|Alpha

Bisection

Cite this as:

Weisstein, Eric W. "Bisection." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Bisection.html

Subject classifications