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

Implementation of Bisection Method in 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.

Leave a Reply

Your email address will not be published. Required fields are marked *