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.

But all functions don’t converge. If for given function

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 |ci−ci−1| (where i are the iteration number) less than some tolerance limit, say epsilon, fixed threshold.
• C3. By testing the condition |f(ci)| 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