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 proceeds by evaluating the function in question at the midpoint of the original interval and testing to see in which of the subintervals or 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 and be the endpoints at the th iteration (with and ) and let be the th approximate solution. Then the number of iterations required to obtain an error smaller than is found by noting that

(1)

and that is defined by

(2)

In order for the error to be smaller than ,

(3)

Taking the natural logarithm of both sides then gives

(4)

so

(5)