Wednesday, 3 April 2013

C Program for Bisection Method

Basic Theory:

The bisection method is a method to find the real root of an equation in which the interval is always divided into half for every new iterative step. If a function changes sign over an interval, the functional value at the mid-point is evaluated. The location of the root is then determined to be within the sub-interval where the sign change occurs. The sub-interval thus becomes the interval for next iteration. The process is repeated until the root is known to the required precision.

Following is a numerical example of Bisection method.
Consider finding the root of f(x) = x2 - 3. Let Error = 0.01 and start with the interval [1, 2].

Table 1: Bisection method applied to f(x) = x2 - 3.
a
b
f(a)
f(b)
c = (a + b)/2
f(c)
Exchange
Error
1.0
2.0
-2.0
1.0
1.5
-0.75
a = c
0.5
1.5
2.0
-0.75
1.0
1.75
0.062
b = c
0.25
1.5
1.75
-0.75
0.0625
1.625
-0.359
a = c
0.125
1.625
1.75
-0.3594
0.0625
1.6875
-0.1523
a = c
0.0625
1.6875
1.75
-0.1523
0.0625
1.7188
-0.0457
a = c
0.0313
1.7188
1.75
-0.0457
0.0625
1.7344
0.0081
b = c
0.0156
1.7188
1.7344
-0.0457
0.0081
1.7266
-0.0189
a = c
0.0078

Thus, with the seventh iteration, we note that the final interval, [1.7266, 1.7344], has a width less than the value of Error and |f(1.7344)| < 0.01, and therefore we chose b = 1.7344 to be our approximation of the root.

Program:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#define f(x) x*x*x-2*x-5 //define the function here

void main(){
clrscr();
float x1 = 2, x2 =3, E=0.0005, x0; //define initial values and errors here
float f1 = f(x1), f2 = f(x2), f0;
float root;

                if(f1*f2>0){
                                goto last;
                }

printf("\n\t\t\tBISECTION METHOD");
printf("\n\n  FINDING ROOT OF x^3-2x-5");
printf("\n\n  X1\t  X2\t  X0\tf(X0)\t  Error");
printf("\n  -------------------------------------");
back:
x0 = (x1+x2)/2;
f0 = f(x0);
printf("\n  %.3f\t%.3f\t%.3f\t%.3f\t%.5f",x1,x2,x0,f(x0),fabs((x2-x1)/x2));
//print in tabular form
                if(f1*f0<0){
                                x2= x0;
                }
                else{
                                x1=x0;
                                f1=f0;
                }

                if(fabs((x2-x1)/x2)<E){
                                root = (x1+x2)/2; //display root if required precision is met
                                printf("\n\n  Approximate Root = %.5f", root);
                                goto last;
                }
                else{
                                goto back;
                }
last:
getch();
}

Sample Output:

     BISECTION METHOD
FINDING ROOT OF x^3-2x-5

X1          X2       X0      f(X0)      Error
------------------------------------------------
2.000   3.000   2.500   5.625    0.33333
2.000   2.500   2.250   1.891    0.20000
2.000   2.250   2.125   0.346    0.11111
2.000   2.125   2.062   -0.351   0.05882
2.062   2.125   2.094   -0.009   0.02941
2.094   2.125   2.109   0.167    0.01471
2.094   2.109   2.102   0.079    0.00741
2.094   2.102   2.098   0.035    0.00372
2.094   2.098   2.096   0.013    0.00186
2.094   2.096   2.095   0.002    0.00093
2.094   2.095   2.095   0.002    0.00047


Approximate Root = 2.09424 

©Dixit Bhatta 2013

No comments:

Post a Comment

Was this post helpful? Ask any questions you have, I will try to answer them for you.

Follow by Email