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

 

x0123
f(x)1-7-91

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:

nan (f(an)<0)bn (f(bn)>0)xn+1=(an + bn)/2f(xn+1)
0010.5-3.37
100.50.25-1.23
200.250.125-0.123
300.1250.06250.437
40.06250.1250.093750.155
50.093750.1250.1093750.016933
60.1093750.1250.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:

nan (f(an)<0)bn (f(bn)>0)xn+1=(an + bn)/2f(xn+1)
0121.5-0.25
11.521.750.3125
21.51.751.6250.015625
31.51.6251.5625-0.121094
41.51.6251.59375-0.053711
51.56251.6251.60937-0.01928
61.593751.6251.61718-0.001893
71.609371.6251.621090.00684
81.617181.621091.619140.00246
91.617181.619141.618160.00028
101.617181.618161.61767-0.00081
111.617671.618161.61791

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

 

<< Previous Next>>

Leave a Reply

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