# Bisection Method – Algorithm, Implementation in C with Solved Examples

Numerical Methods & Algorithms / Wednesday, October 10th, 2018

# Bisection Method

The Bisection method is the most simplest iterative method and also known as half-interval or Bolzano method.

This method is based on the theorem which states that “If a function f(x) is continuous in the closed interval [a, b] and f(a) and f(b) are of opposite signs then there exists at least one real root of f(x) = 0, between a and b.

Let ξ be root of the equation f(x) = 0 lies in the interval [a, b], i.e., f(a).f(b) < 0, and (b – a) is not sufficiently small. The interval [a, b] is divided into two equal [a, c] and [c, b], each of length (b – a)/2 and c = (a + b)/2. If f(c) = 0, then c is an exact root.

Now, if f(c) ≠ 0, then the root lies either in the interval [a, c] or in the interval [c, b]. If f(a).f(c) < 0 then the interval [a, c] is taken as new interval, otherwise [c, b] is taken as the next interval. Let the new interval be [a1, b1] and use the same process to select the next new interval. In the next step, let the new interval be [a2, b2]. The process of bisection is continued until either the midpoint of the interval is a root, or the length (bn – an) of the interval [an, bn] (at nth step) is sufficiently small. The number an and bn are the approximate roots of the equation f(x) = 0. Finally, xn = (an + bn) /2 is taken as the approximate value of the root ξ.

## An algorithm of bisection method

Bisection Algorithm
Input function f(x);
// Assume that f(x) is continuous within [a, b]
// and a root lies on [a, b]
Read a, b; //input of the interval
Read ξ; //tolerance for width of the interval
Compute fa = f(a); fb = f(b); //compute the function values
if sign(fa) = sign(fb) then
//sign(fa) gives the sign of the value of fa
Print 'f(a).f(b) > 0, so there is no guarantee for a root within [a, b]';
Stop;
endif;
do
Compute c = (a+b)/2;
compute fc = f(c);
if fc = 0 or |fc| < ξ then
a = c and b = c;
else if sign(fb) = sign(fc) then
b = c; fb = fc;
else
a = c; fa = fc;
endif;
while (|b - a| > ξ );
Print 'the desired root is ' c;
end Bisection



## Implementation of Bisection Method in C

/* Program Bisection Method
Program to find a root of the equation x*x*x - 2x -1 = 0
by Bisection Method.
Assume that a root lies between a and b. */

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define f(x) x*x*x-2*x-1 //definition of the function f(x)
void main()
{
float a,b,fa,fb,c,fc;
float eps=1e-5; //error tolerance
printf("\nEnter the value of a and b :");
scanf("%f%f",&a,&b);
fa=f(a);
fb=f(b);
if(fa*fb>0)
{
printf("There is no guarantee for a root within [a, b]");
exit(0);
}
do
{
c=(a+b)/2;
fc=f(c);
if((fc==0) || (fabs(fc)<eps))
{
a=c;
b=c;
}
else if(fb*fc>0)
{
b=c;
fb=fc;
}
else
{
a=c;
fa=fc;
}
}while(fabs(b-a)>eps);
printf("\nThe desired root is %8.5f",c);
}



Output:

Enter the value of a and b: 0 2
The desired root is 1.61803

 Example 01

Find the location of the positive roots of x3 – 9x + 1 = 0 and evaluate the smallest one by bisection method correct to two decimal places.

Solution:

We tabulate f(x) = x3 – 9x + 1

 x 0 1 2 3 f(x) 1 -7 -9 1

Thus we find the positive roots lie in the intervals [0, 1] and [2, 3].
To find the smallest roots, the successive approximation by bisection method are tabulated below:

 n an (f(an)<0) bn (f(bn)>0) xn+1=(an + bn)/2 f(xn+1) 0 0 1 0.5 -3.37 1 0 0.5 0.25 -1.23 2 0 0.25 0.125 -0.123 3 0 0.125 0.0625 0.437 4 0.0625 0.125 0.09375 0.155 5 0.09375 0.125 0.109375 0.016933 6 0.109375 0.125 0.11718 -0.053

Hence, the required root correct to two decimal places is 0.11.

 Example 02

Find a real root of the equation x2 –x -1 = 0 by the method of bisection.

Solution:

Let f(x) = x2 –x -1
Then f(0) = -1, f(1) = -1, f(2) = 1
So a root lies between 1 and 2.
Take a0 = 1, b0 = 2 so that x1 = (0 + 1)/2 = 1.5
Since f(1.5) = -0.25 and f(2) = 1, so the root lies between 1.5 and 2. Thus we have x2 = (1.5 + 2)/2 = 1.75. Proceeding in this way, we obtain the following table:

 n an (f(an)<0) bn (f(bn)>0) xn+1=(an + bn)/2 f(xn+1) 0 1 2 1.5 -0.25 1 1.5 2 1.75 0.3125 2 1.5 1.75 1.625 0.015625 3 1.5 1.625 1.5625 -0.121094 4 1.5 1.625 1.59375 -0.053711 5 1.5625 1.625 1.60937 -0.01928 6 1.59375 1.625 1.61718 -0.001893 7 1.60937 1.625 1.62109 0.00684 8 1.61718 1.62109 1.61914 0.00246 9 1.61718 1.61914 1.61816 0.00028 10 1.61718 1.61816 1.61767 -0.00081 11 1.61767 1.61816 1.61791

Thus real root of the given equation is 1.618 correct to three decimal places.

<< Previous     Next>>

;