Bisection Method – What is, Algorithm, and Example

What is Bisection Method?

Bisection Method is one of the basic numerical solutions for finding the root of a polynomial equation. It brackets the interval in which the root of the equation lies and subdivides them into halves in each iteration until it finds the root. Thus, the bisection method is also called the bracketing method.

However, as the working mechanism is similar to the binary search algorithm, the bisection method is also known as binary search method, halving method, or the dichotomy method. It is primarily based on the Intermediate value theorem.

Finding Roots of Equations

In this example, we only consider equations with one independent variable. It can be either linear or nonlinear. Linear equations are used to represent the graph of a straight line, whereas non-linear equations are used to represent curves.

The root of an equation means the value of the independent variable that satisfies the equation. For example: the root of an equation f(x)= 4-x2 = 0 is 2 because f(2) = 4-22 =0.

Let’s consider f(x) as a real continuous function. According to the intermediate value theorem, the equation f(x)=0 has at least one root between a and b if f(a)f(b) < 0. The function f(x) has a root, “c,” between a and b.

Finding Roots of Equations

Graphical Representation of Bisection Method

The following graph represents the working mechanism of the bisection method. From the graph, we can see that the root of the equation is red marked.

To begin with:

  • We first took two initial guesses, a1 and b1, for which f(a1)f(b1) < 0. According to the intermediate value theorem, the root should lie in [a1, b1].
  • We can find the midpoint of a1 and b1, which is b2. Thus, the initial interval is now reduced to [a1, b2] because f(a1)f(b2) < 0.
  • In the same manner, the interval is reduced until the approximate solution is found.

Graphical Representation of Bisection Method

Bisection Method Algorithm

The steps for applying the bisection method algorithm to find the root of equation f(x)=0 is as follows

Step 1) Choose initial guesses a, b, and tolerance rate e

Step 2) If f(a)f(b) >=0, then the root does not lie in this interval. Thus, there will be no solution.

Step 3) Find the midpoint, c = (a+b)/2

(i) If the function value of the midpoint f(c) = 0, then c is the root. Go to step 5.
(ii) If f(a)f(c) < 0 the root lies between a and c. Then set a = a, b = c.
(iii) Else set a = c, b = b.

Step 4) If the absolute error is higher than the tolerance rate or (b-a) > e, go to step 3.

Step 5) Display c as the approximate root.

Let’s see an example of the bisection method algorithm.
We have to find the root of the following continuous function using the bisection method formula.

f(x) = x3 – x2 + 2

Bisection Method Example

Step 1) Let’s assume,

         a = -10,
         b = 10, and
         e = 1% or 0.01

Step 2) Now, we will check whether f(a)f(b) >= 0 or not.

         f(a) = f(-10) = (-10)3 – (-10)2 + 2 = -1098
         f(b) = f(10) = (10)3 – (10)2 + 2 = 902
         f(a)f(b) = f(-10)f(10) = (-1098)(902) < 0

Hence, the root of the above function lies in this interval [-10, 10].

Step 3) Then the midpoint c will be calculated first.

Bisection Method Example

Now the following conditions need to be checked:

(i) whether f(c) = 0:
         f(c) = f(0) = (0)3 – (0)2 + 2 = 2 ≠ 0

(ii) if f(a)f(c) < 0:
         f(c)f(a) = 2*(-1098) < 0

The condition is fulfilled. For the next iteration, the values will be,

         a = a = -10
         b = c = 0

Step 4) As (b-a) = (0-(-10)) = 10>0.05, the process will be repeated. The next iterations are shown in the table.

Iteration a b c b-a f(c)
1 -10 0 0 10 2
2 -5 0 -5 5 -148
3 -2.5 0 -2.5 2.5 -19.875
4 -1.25 0 -1.25 1.25 -1.52562
5 -1.25 -0.625 -0.625 0.625 1.36523
6 -1.25 -0.9375 -0.9375 0.3125 0.297119
7 -1.09375 -0.9375 -1.09375 0.15625 -0.50473
8 -1.01562 -0.9375 -1.01562 0.078125 -0.0791054
9 -1.01562 -0.976562 -0.976562 0.0390625 0.115003
10 -1.01562 -0.996094 -0.996094 0.0195312 0.0194703
11 -1.00586 -0.996094 -1.00586 0.00976562 -0.0294344

Step 5) In the 11th iteration, the step 4 condition will be false. Thus, the root of this equation is -1.00586.

Bisection Method Logical Diagram

Bisection Method Logical Diagram

Pseudo-Code

Start
Set a, b, e
if f(a)*f(b) >=0 
	Output("Root does not exist in this interval")
	Stop
while (b-a)>e do   
	c ← (a + b)/2    
	if f(c) = 0
        	break    
	end if 
	if f(c)*f(a) < 0 then
      	b ← c    
	else        
		a ← c
end while
Output(c)
Stop

Bisection Method Example in C/C++

Input:

#include<bits/stdc++.h>
using namespace std;
#define Error 0.01
double value(double x)
{
	return x*x*x - x*x + 2;
}
void bisection_method(double a, double b)
{
	if (value(a) * value(b) >= 0)
	{
		cout << "The root does not lie in this interval\n";
		return;
	}
	double c = a;
	while ((b-a) >= Error)
	{
		c = (a+b)/2;
		if (value(c) == 0.0)
			break;
		else if (value(c)*value(a) < 0)
			b = c;
		else
			a = c;
	}
	cout << "The root is :" << c;
}
int main()
{
	double a =-10 , b = 10;
	bisection_method(a, b);
	return 0;
}

Output:

The root is :-1.00586

Bisection Method Example in Python

Input:

def value(x):
	return x*x*x - x*x + 2
def bisection_method(a,b):
	if (value(a) * value(b) >= 0):
		return
	c = a
	while ((b-a) >= 0.01):
		c = (a+b)/2
		if (value(c) == 0.0):
			break
		if (value(c)*value(a) < 0):
			b = c
		else:
			a = c			
	print("The root is : ","%.4f"%c)	
a =-10
b = 10
bisection_method(a, b)

Output:

The root is :  -1.0059

Advantages & Limitations of Bisection Method

Here are the Pros and Cons of Bisection Method:

Pros Cons
Easy and simple root-finding method to implement. The convergence is slow because it is simply based on halving the interval.
Since it brackets the root, it is always convergent. If one of the initial guesses is close to the root, reaching the root will take more iterations.
The error rate can be controlled by increasing or decreasing the number of iterations.