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 [a₁, b₁] and use the same process to select the next new interval. In the next step, let the new interval be [a₂, b₂]. The process of bisection is continued until either the midpoint of the interval is a root, or the length (b_n – a_n) of the interval [a_n, b_n] (at nth step) is sufficiently small. The number a_n and b_n are the approximate roots of the equation f(x) = 0. Finally, x_n = (a_n + b_n) /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

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

Solution:

We tabulate f(x) = x³ – 9x + 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:

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

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

Solution:

Let f(x) = x² –x -1
Then f(0) = -1, f(1) = -1, f(2) = 1
So a root lies between 1 and 2.
Take a₀ = 1, b₀ = 2 so that x₁ = (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 x₂ = (1.5 + 2)/2 = 1.75. Proceeding in this way, we obtain the following table:

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

<< Previous     Next>>

;