Bisection Methods:

We can pursuse the above idea a little further by narrowing the interval until the interval within which the root lies is small enough. For the function in Example 1, we can bisect the interval [0,2/3] to two subintervals, [0,1/3] and [1/3,2/3]. Now, it is easily verified that f(x) does not change sign in the subinterval [0,1/3] and that it changes sign in the subinterval [1/3,2/3]. Hence we choose the subinterval [1/3,2/3] and bisect it further. This will result in the choice of the new subinterval [1/2,2/3]. We approximate the root at this stage as the arithmetic average of the end-point coordinates of this interval, this gives for the root x_r = 0.58333... Now f(0.5833)=5.4E-3; if the root is desired only to this accuracy, we can stop here or if further accuracy is desired, we can proceed further with the bisection method. The above method can be generalized as a bisection algorithm as follows:

1.

Given f(x), choose the initial interval [x₁,x₂] such that x₁<x₂ and f(x₁)*f(x₂)<0. Choose epsilon, the tolerance level. Choose N, maximum number of bisections. Define a counter, say ib, to keep track of the number of bisections performed.

2.

for ib < N+1
Compute x₃ = (x₁ + x₂)/2.
if { |f(x₃)| < epsilon then print results and exit the program}
if { f(x₁)*f(x₃)<0 then set x₂ = x₃}
else { f(x₃)*f(x₂)<0 then set x₁ = x₃}.

3.

If convergence was not obtained in N bisections, print current values for x₁, x₂ and f(x₃) and inform the user that the tolerance criterion was not satisfied in N bisections and exit the program.

Notice that this algorithm locates only one root of the equation at a time. This is generally true of numerical methods for solving nonlinear equations. When an equation has multiple roots, it is the choice of the initial interval provided by the user which determines which root is located. The choice of an interval [a,b] such that f(a)*f(b)<0 only ensures that there is at least one real root between a and b, and therefore that the method can converge to a root. The contrary condition, f(a)*f(b)>0 does not imply that there are no real roots in the interval [a,b], however. Consider the example given above, with a starting interval of [0,1]. What one can say, is that there is no guarantee of there being a root in the interval [a,b] when f(a)*f(b)>0, and the bisection algorithm will fail in this case. Thus the choice of starting interval is important to the success of the bisection method.