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.
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.
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.
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
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. |