# 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_{1}, b_{1}] and use the same process to select the next new interval. In the next step, let the new interval be [a_{2}, b_{2}]. 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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/* 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

Example 01 |

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

**Solution:**

We tabulate f(x) = x^{3} – 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 |
a_{n} (f(a_{n})<0) |
b_{n} (f(b_{n})>0) |
x_{n+1}=(a_{n} + b_{n})/2 |
f(x_{n+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 x ^{2} –x -1 = 0 by the method of bisection.**

**Solution:**

Let f(x) = x^{2} –x -1

Then f(0) = -1, f(1) = -1, f(2) = 1

So a root lies between 1 and 2.

Take a_{0 }= 1, b_{0 }= 2 so that x_{1} = (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_{2} = (1.5 + 2)/2 = 1.75. Proceeding in this way, we obtain the following table:

n |
a_{n} (f(a_{n})<0) |
b_{n} (f(b_{n})>0) |
x_{n+1}=(a_{n} + b_{n})/2 |
f(x_{n+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.