Bisection Method

This is also an iterative method. To find root, repeatedly bisect an interval (containing the root) and then selects a subinterval in which a root must lie for further processing. Algorithm is quite simple and robust, only requirement is that initial search interval must encapsulates the actual root.

Given a function f (x) continuous on an interval [a,b] and f (a) * f (b) < 0
Do
     c = (a+b)/2
     if f (a) * f (c) < 0 then  b = c
                          else  a = c
while (none of the convergence criteria C1, C2 or C3 is satisfied)

where the criteria for convergence are :-

• C1. Fixing a priori the total number of bisection iterations N i.e., the length of the interval or the maximum error after N iterations in this case is less than \(| b-a | / 2N\).
• C2. By testing the condition \(|c_i - c_{i-1}|\) (where i are the iteration number) less than some tolerance limit, say epsilon, fixed threshold.
• C3. By testing the condition \(|f(c_i)|\) less than some tolerance limit alpha again fixed threshold.

C Implementation

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define f(x) ((x*x*x)-18)
int main(){
float a=0,b=0,error=0,m,mold;
int i=0;
printf("Input Interval: ");
scanf("%f %f",&a,&b);
if((f(a)*f(b))>0){
        printf("Invalid Interval Exit!");       //to test whether search interval
        exit(1);                                                        //is okay or not
}
else if(f(a)==0 || f(b)==0){
        printf("Root is one of interval bounds. Root is %f\n",f(a)==0?a:b);
        exit(0);
}
printf("Ite\ta\t\tb\t\tm\t\tf(m)\t\terror\n");
do{
        mold=m;
        m=(a+b)/2;
        printf("%2d\t%4.6f\t%4.6f\t%4.6f\t%4.6f\t",i++,a,b,m,f(m));
        if(f(m)==0){
                printf("Root is %4.6f\n",m);
        }else if ((f(a)*f(m))<0){
                b=m;
        }else a=m;
        error=fabs(m-mold);
        if(i==1){
                printf("----\n");
        }else printf("%4.6f\n",error);
}while(error>0.00005);
printf("Approximate Root is %4.6f",m);
return 0;
}

Output

 Input Interval: 1 3
Ite    a               b               m               f(m)            error
0      1.000000        3.000000        2.000000        -10.000000      ----
1      2.000000        3.000000        2.500000        -2.375000       0.500000
2      2.500000        3.000000        2.750000        2.796875        0.250000
3      2.500000        2.750000        2.625000        0.087891        0.125000
4      2.500000        2.625000        2.562500        -1.173584       0.062500
5      2.562500        2.625000        2.593750        -0.550446       0.031250
6      2.593750        2.625000        2.609375        -0.233189       0.015625
7      2.609375        2.625000        2.617188        -0.073128       0.007812
8      2.617188        2.625000        2.621094        0.007261        0.003906
9      2.617188        2.621094        2.619141        -0.032963       0.001953
10     2.619141        2.621094        2.620117        -0.012859       0.000977
11     2.620117        2.621094        2.620605        -0.002802       0.000488
12     2.620605        2.621094        2.620850        0.002230        0.000244
13     2.620605        2.620850        2.620728        -0.000286       0.000122
14     2.620728        2.620850        2.620789        0.000973        0.000061
15     2.620728        2.620789        2.620758        0.000343        0.000031
Approximate Root is 2.620758