Bisection Method

 

The bisection method is one of the first numerical methods developed to find the root of a nonlinear equation f(x)=0, also called the binary-search method. 

In the Bisection method, we start with two initial approximations ‘a’ and ‘b’, and we suppose that f is a continuous function defined on the interval [a, b], with f(a) and f(b) of opposite sign. Furthermore if f(a)*f(b)<0, has at least one root between a and b, and if f(a)*f(b)>0, there may or may not be any root between a and b.  If f(a)*f(b)>0, then there may be more than one root between a and b.  So the method only guarantees one root between a and b.

Since the method is based on finding the root between two points, the method falls under the category of bracketing methods.

Since the root is bracketed between two points, a and b, one can find the mid-point, 

1. Choose a and b as two guesses for the root such that f(a)*f(b)<0, or in other words, f(x) changes the sign between a and b.
2. Estimate the root, C, of the equation f(x)=0 as the mid-point between a and b as

            C(n)=(a+b)/2

3. Now check the following

a)      If f(a)*f(c)<0, then the root lies between a and c; then a=a1 and b=c.  

b)      If f(a)*f(b)>0, then the root lies between c and b; then a=c and b=b1.

c)      If f(a)*f(b)=0; then the root is c.  Stop the algorithm if this is true.

4. Find the new estimate of the root

            C(n)=(a+b)/2

            Find the absolute relative approximate error as

            

5. Compare the absolute relative approximate error  with the pre-specified relative error tolerance. 

Maple Program Bisection Method

restart;

 with(Student[NumericalAnalysis]):

f := x^3 + 4*x^2 - 10;

Bisection(f, x = [1, 2], tolerance = 10^(-4));

1.365112304

Bisection(f, x = [1, 2], tolerance = 10^(-4), output = sequence);

[1., 2.], [1., 1.500000000], [1.250000000, 1.500000000], [1.250000000, 1.375000000], [1.312500000, 1.375000000], [1.343750000, 1.375000000], [1.359375000, 1.375000000], [1.359375000, 1.367187500], [1.363281250, 1.367187500], [1.363281250, 1.365234375], [1.364257812, 1.365234375]

Bisection(f, x = [1, 2], tolerance = 10^(-2), stoppingcriterion = absolute);

1.367187500

Bisection(f, x = [1, 2], output = animation, tolerance = 10^(-3), stoppingcriterion = function_value);

Bisection(f, x = [1, 2], output = plot, tolerance = 10^(-3), maxiterations = 15, stoppingcriterion = relative);

Bisection(f, x = [1, 2], output = animation, tolerance = 10^(-3), maxiterations = 15, stoppingcriterion = relative);

Bisection(f, x = [1, 2], output = information, tolerance = 10^(-9), maxiterations = 15, stoppingcriterion = function_value);