.PNG)
Program Statement :
Write a C program to implement Bisection method to solve an Algebraic or Transcendal equation.
Theory :
The method of bisection is a root-finding algorithm which repeatedly bisects an interval then selects a subinterval in which a root must lie for further processing. It is the most simplest iterative and robust method, but it is also relatively slow. It is also known as half-interval or Bolzano method. This method is based on the following theorem on the change of sign.
Theorem : If f(a) and f(b) are of the same sign, then there are an odd number (at least one) of real roots of the equation f(x) = 0 between a and b.
In this method, we first find out a sufficiently small interval [a0, b0] containing the required root by graphical or tabulation method. Then f(a0)f(b0) < 0 and f'(x) has the same sign in [a0, b0] and so f(x) is strictly monotonic in [a0, b0]. To generate the sequence {xn} of iterates, we put x0 = a0 or b0 and x1 = ½ (a0 + b0) and find f(x1). If f(a0) and f(x1) are of opposite signs, then set a1 = a0, b1 = x1 so that [a1, b1] = [a0, x1]. On the other hand, if f(x1) and f(b0) are of opposite signs then put a1 = x1, b1 = b0, i.e. [a1, b1] = [x1, b0]. Thus we see that [a1, b1] contains the root ∝ in either case. Next set x2 = ½ (a1 + b1) and repeat the above process till we obtain xn+1 = ½ (an + bn) with desired accuracy with xn → ∝ as n → ∞.
A few steps of the bisection method applied over the starting range [a1, b1]. The bigger dot is the root of the function.
Algorithm :
Step1 : Start the program.
Step2 : Define the function f(x).
Step3 : Select he interval (a, b) in which the root lies.
Step4 : Calculate y1 = f(a), y2 = f(b).
Step5 : If y1y2 < 0, then goto step 6 else step 10. Step6 : Calculate x = (a+b)/2, y = f(x). Step7 : If y1y2 < 0, set b = x, otherwise set a = x. Step8 : If |a-b| < ℇ, ℇ being the prescribed accuracy, then go to step 9 else step 6. Step9 : Print the value of x. Step10 : Stop the program.
Program listing :
/* C program to find a real root of a given equation using Bisection method */
#include<stdio.h>
#include<math.h>
#define e 0.000001/*e is the prescribed accuracy*/
main()
{
double g1,g2,g,v,v1,v2,prev;
int found=0,converged=0,i=0;
double f(double);
printf("We apply Bisection method to find a real root of the non-linear equation f(x) = 0, where f(x) = x^(2.7182818)-3cosx+1n");
while(found==0)/*This loop will continue until a range is found in between which a real root lies*/
{
printf("nEnter the first guess : ");
scanf("%lf",&g1);
v1=f(g1);
printf("nEnter the second guess : ");
scanf("%lf",&g2);
v2=f(g2);
if(v1*v2>0)
{
found=0;
g1++;
printf("nRoot does not lie in [%lf,%lf].n",g1-1,g2);
printf("nn..Enter two new guesses..nn");/*Previous two guesses are inappropriate*/
}
else
found=1;
}
printf("nThere is a real root which lies in [%lf,%lf].n",g1,g2);
while(converged==0)/*This loop will continue until a real root is found*/
{
printf("nnIteration = %dnn",i);
printf("a[%d](-ve)tb[%d](+ve)tbbx[%d]=(a[%d]+b[%d])/2tf(x[%d])n",i,i,i+1,i,i,i+1);
printf("%lft",g1);
printf("%lft",g2);
g=(g1+g2)/2;
v=f(g);
printf("%lft",g);
printf("t%lf",v);
if(v<0)
g1=g;
else
g2=g;
if(fabs(prev-v)<e)
converged=1;
else
prev=v;
i=i+1;
}
printf("nnThe approximate value of the root is : %lfn",g);
}
/*This function returns values of f(x)*/
double f(double x)
{
return pow(2.7182818,x)-3*cos(x)+1;
}
Output :
We apply Bisection method to find a real root of the non-linear equation f(x) = 0, where f(x) = x^(2.7182818)-3cosx+1
Enter the first guess : 1
Enter the second guess : 2
Root does not lie in [1.000000,2.000000].
..Enter two new guesses..
Enter the first guess : 0
Enter the second guess : 1
There is a real root which lies in [0.000000,1.000000].
Iteration = 0
a[0](-ve) b[0](+ve) x[1]=(a[0]+b[0])/2 f(x[1])
0.000000 1.000000 0.500000 0.015974
Iteration = 1
a[1](-ve) b[1](+ve) x[2]=(a[1]+b[1])/2 f(x[2])
0.000000 0.500000 0.250000 -0.622712
Iteration = 2
a[2](-ve) b[2](+ve) x[3]=(a[2]+b[2])/2 f(x[3])
0.250000 0.500000 0.375000 -0.336531
Iteration = 3
a[3](-ve) b[3](+ve) x[4]=(a[3]+b[3])/2 f(x[4])
0.375000 0.500000 0.437500 -0.168611
Iteration = 4
a[4](-ve) b[4](+ve) x[5]=(a[4]+b[4])/2 f(x[5])
0.437500 0.500000 0.468750 -0.078406
Iteration = 5
a[5](-ve) b[5](+ve) x[6]=(a[5]+b[5])/2 f(x[6])
0.468750 0.500000 0.484375 -0.031738
Iteration = 6
a[6](-ve) b[6](+ve) x[7]=(a[6]+b[6])/2 f(x[7])
0.484375 0.500000 0.492188 -0.008013
Iteration = 7
a[7](-ve) b[7](+ve) x[8]=(a[7]+b[7])/2 f(x[8])
0.492188 0.500000 0.496094 0.003948
Iteration = 8
a[8](-ve) b[8](+ve) x[9]=(a[8]+b[8])/2 f(x[9])
0.492188 0.496094 0.494141 -0.002041
Iteration = 9
a[9](-ve) b[9](+ve) x[10]=(a[9]+b[9])/2 f(x[10])
0.494141 0.496094 0.495117 0.000951
Iteration = 10
a[10](-ve) b[10](+ve) x[11]=(a[10]+b[10])/2 f(x[11])
0.494141 0.495117 0.494629 -0.000545
Iteration = 11
a[11](-ve) b[11](+ve) x[12]=(a[11]+b[11])/2 f(x[12])
0.494629 0.495117 0.494873 0.000203
Iteration = 12
a[12](-ve) b[12](+ve) x[13]=(a[12]+b[12])/2 f(x[13])
0.494629 0.494873 0.494751 -0.000171
Iteration = 13
a[13](-ve) b[13](+ve) x[14]=(a[13]+b[13])/2 f(x[14])
0.494751 0.494873 0.494812 0.000016
Iteration = 14
a[14](-ve) b[14](+ve) x[15]=(a[14]+b[14])/2 f(x[15])
0.494751 0.494812 0.494781 -0.000078
Iteration = 15
a[15](-ve) b[15](+ve) x[16]=(a[15]+b[15])/2 f(x[16])
0.494781 0.494812 0.494797 -0.000031
Iteration = 16
a[16](-ve) b[16](+ve) x[17]=(a[16]+b[16])/2 f(x[17])
0.494797 0.494812 0.494804 -0.000008
Iteration = 17
a[17](-ve) b[17](+ve) x[18]=(a[17]+b[17])/2 f(x[18])
0.494804 0.494812 0.494808 0.000004
Iteration = 18
a[18](-ve) b[18](+ve) x[19]=(a[18]+b[18])/2 f(x[19])
0.494804 0.494808 0.494806 -0.000002
Iteration = 19
a[19](-ve) b[19](+ve) x[20]=(a[19]+b[19])/2 f(x[20])
0.494806 0.494808 0.494807 0.000001
Iteration = 20
a[20](-ve) b[20](+ve) x[21]=(a[20]+b[20])/2 f(x[21])
0.494806 0.494807 0.494807 -0.000000
Iteration = 21
a[21](-ve) b[21](+ve) x[22]=(a[21]+b[21])/2 f(x[22])
0.494807 0.494807 0.494807 0.000001
The approximate value of the root is : 0.494807
Discussions :
If f has several simple roots in the interval [a, b], then the bisection method will find one of them.
The expression f(left) * f(midpoint) is very likely to underflow to 0 since both arguments are approaching a zero of f. To avoid this possibility, the two function values should be tested separately rather than multiplied.
If ℇ is too small, the value of |(right – left)| might never become as small as 2*ℇ, as left and right can get stuck at adjacent non-equal floating-point values.
The order of convergence of bisection method is 1, i.e., the convergence is linear.
Advantage of bisection method is that it is very simple, as at any stage of iteration the approximate value of the desired root of the equation f(x) = 0 does not depend on the values f(xn) but on their signs only.
Also this method is unconditionally and surely convergent if f(a) and f(b) have different signs.
Disadvantage of this method is that it is very slow and requires large number of iteration to obtain moderately accurate results and hence it is laborious.
Write a C program to implement Bisection method to solve an Algebraic or Transcendal equation.
Theory :
The method of bisection is a root-finding algorithm which repeatedly bisects an interval then selects a subinterval in which a root must lie for further processing. It is the most simplest iterative and robust method, but it is also relatively slow. It is also known as half-interval or Bolzano method. This method is based on the following theorem on the change of sign.
Theorem : If f(a) and f(b) are of the same sign, then there are an odd number (at least one) of real roots of the equation f(x) = 0 between a and b.
In this method, we first find out a sufficiently small interval [a0, b0] containing the required root by graphical or tabulation method. Then f(a0)f(b0) < 0 and f'(x) has the same sign in [a0, b0] and so f(x) is strictly monotonic in [a0, b0]. To generate the sequence {xn} of iterates, we put x0 = a0 or b0 and x1 = ½ (a0 + b0) and find f(x1). If f(a0) and f(x1) are of opposite signs, then set a1 = a0, b1 = x1 so that [a1, b1] = [a0, x1]. On the other hand, if f(x1) and f(b0) are of opposite signs then put a1 = x1, b1 = b0, i.e. [a1, b1] = [x1, b0]. Thus we see that [a1, b1] contains the root ∝ in either case. Next set x2 = ½ (a1 + b1) and repeat the above process till we obtain xn+1 = ½ (an + bn) with desired accuracy with xn → ∝ as n → ∞.
Algorithm :
Step1 : Start the program.
Step2 : Define the function f(x).
Step3 : Select he interval (a, b) in which the root lies.
Step4 : Calculate y1 = f(a), y2 = f(b).
Step5 : If y1y2 < 0, then goto step 6 else step 10. Step6 : Calculate x = (a+b)/2, y = f(x). Step7 : If y1y2 < 0, set b = x, otherwise set a = x. Step8 : If |a-b| < ℇ, ℇ being the prescribed accuracy, then go to step 9 else step 6. Step9 : Print the value of x. Step10 : Stop the program.
Program listing :
/* C program to find a real root of a given equation using Bisection method */
#include<stdio.h>
#include<math.h>
#define e 0.000001/*e is the prescribed accuracy*/
main()
{
double g1,g2,g,v,v1,v2,prev;
int found=0,converged=0,i=0;
double f(double);
printf("We apply Bisection method to find a real root of the non-linear equation f(x) = 0, where f(x) = x^(2.7182818)-3cosx+1n");
while(found==0)/*This loop will continue until a range is found in between which a real root lies*/
{
printf("nEnter the first guess : ");
scanf("%lf",&g1);
v1=f(g1);
printf("nEnter the second guess : ");
scanf("%lf",&g2);
v2=f(g2);
if(v1*v2>0)
{
found=0;
g1++;
printf("nRoot does not lie in [%lf,%lf].n",g1-1,g2);
printf("nn..Enter two new guesses..nn");/*Previous two guesses are inappropriate*/
}
else
found=1;
}
printf("nThere is a real root which lies in [%lf,%lf].n",g1,g2);
while(converged==0)/*This loop will continue until a real root is found*/
{
printf("nnIteration = %dnn",i);
printf("a[%d](-ve)tb[%d](+ve)tbbx[%d]=(a[%d]+b[%d])/2tf(x[%d])n",i,i,i+1,i,i,i+1);
printf("%lft",g1);
printf("%lft",g2);
g=(g1+g2)/2;
v=f(g);
printf("%lft",g);
printf("t%lf",v);
if(v<0)
g1=g;
else
g2=g;
if(fabs(prev-v)<e)
converged=1;
else
prev=v;
i=i+1;
}
printf("nnThe approximate value of the root is : %lfn",g);
}
/*This function returns values of f(x)*/
double f(double x)
{
return pow(2.7182818,x)-3*cos(x)+1;
}
Output :
We apply Bisection method to find a real root of the non-linear equation f(x) = 0, where f(x) = x^(2.7182818)-3cosx+1
Enter the first guess : 1
Enter the second guess : 2
Root does not lie in [1.000000,2.000000].
..Enter two new guesses..
Enter the first guess : 0
Enter the second guess : 1
There is a real root which lies in [0.000000,1.000000].
Iteration = 0
a[0](-ve) b[0](+ve) x[1]=(a[0]+b[0])/2 f(x[1])
0.000000 1.000000 0.500000 0.015974
Iteration = 1
a[1](-ve) b[1](+ve) x[2]=(a[1]+b[1])/2 f(x[2])
0.000000 0.500000 0.250000 -0.622712
Iteration = 2
a[2](-ve) b[2](+ve) x[3]=(a[2]+b[2])/2 f(x[3])
0.250000 0.500000 0.375000 -0.336531
Iteration = 3
a[3](-ve) b[3](+ve) x[4]=(a[3]+b[3])/2 f(x[4])
0.375000 0.500000 0.437500 -0.168611
Iteration = 4
a[4](-ve) b[4](+ve) x[5]=(a[4]+b[4])/2 f(x[5])
0.437500 0.500000 0.468750 -0.078406
Iteration = 5
a[5](-ve) b[5](+ve) x[6]=(a[5]+b[5])/2 f(x[6])
0.468750 0.500000 0.484375 -0.031738
Iteration = 6
a[6](-ve) b[6](+ve) x[7]=(a[6]+b[6])/2 f(x[7])
0.484375 0.500000 0.492188 -0.008013
Iteration = 7
a[7](-ve) b[7](+ve) x[8]=(a[7]+b[7])/2 f(x[8])
0.492188 0.500000 0.496094 0.003948
Iteration = 8
a[8](-ve) b[8](+ve) x[9]=(a[8]+b[8])/2 f(x[9])
0.492188 0.496094 0.494141 -0.002041
Iteration = 9
a[9](-ve) b[9](+ve) x[10]=(a[9]+b[9])/2 f(x[10])
0.494141 0.496094 0.495117 0.000951
Iteration = 10
a[10](-ve) b[10](+ve) x[11]=(a[10]+b[10])/2 f(x[11])
0.494141 0.495117 0.494629 -0.000545
Iteration = 11
a[11](-ve) b[11](+ve) x[12]=(a[11]+b[11])/2 f(x[12])
0.494629 0.495117 0.494873 0.000203
Iteration = 12
a[12](-ve) b[12](+ve) x[13]=(a[12]+b[12])/2 f(x[13])
0.494629 0.494873 0.494751 -0.000171
Iteration = 13
a[13](-ve) b[13](+ve) x[14]=(a[13]+b[13])/2 f(x[14])
0.494751 0.494873 0.494812 0.000016
Iteration = 14
a[14](-ve) b[14](+ve) x[15]=(a[14]+b[14])/2 f(x[15])
0.494751 0.494812 0.494781 -0.000078
Iteration = 15
a[15](-ve) b[15](+ve) x[16]=(a[15]+b[15])/2 f(x[16])
0.494781 0.494812 0.494797 -0.000031
Iteration = 16
a[16](-ve) b[16](+ve) x[17]=(a[16]+b[16])/2 f(x[17])
0.494797 0.494812 0.494804 -0.000008
Iteration = 17
a[17](-ve) b[17](+ve) x[18]=(a[17]+b[17])/2 f(x[18])
0.494804 0.494812 0.494808 0.000004
Iteration = 18
a[18](-ve) b[18](+ve) x[19]=(a[18]+b[18])/2 f(x[19])
0.494804 0.494808 0.494806 -0.000002
Iteration = 19
a[19](-ve) b[19](+ve) x[20]=(a[19]+b[19])/2 f(x[20])
0.494806 0.494808 0.494807 0.000001
Iteration = 20
a[20](-ve) b[20](+ve) x[21]=(a[20]+b[20])/2 f(x[21])
0.494806 0.494807 0.494807 -0.000000
Iteration = 21
a[21](-ve) b[21](+ve) x[22]=(a[21]+b[21])/2 f(x[22])
0.494807 0.494807 0.494807 0.000001
The approximate value of the root is : 0.494807
Discussions :
If f has several simple roots in the interval [a, b], then the bisection method will find one of them.
The expression f(left) * f(midpoint) is very likely to underflow to 0 since both arguments are approaching a zero of f. To avoid this possibility, the two function values should be tested separately rather than multiplied.
If ℇ is too small, the value of |(right – left)| might never become as small as 2*ℇ, as left and right can get stuck at adjacent non-equal floating-point values.
The order of convergence of bisection method is 1, i.e., the convergence is linear.
Advantage of bisection method is that it is very simple, as at any stage of iteration the approximate value of the desired root of the equation f(x) = 0 does not depend on the values f(xn) but on their signs only.
Also this method is unconditionally and surely convergent if f(a) and f(b) have different signs.
Disadvantage of this method is that it is very slow and requires large number of iteration to obtain moderately accurate results and hence it is laborious.
