Completely Solved C, C++ Programs Assignment.




C program to implement Bisection method to solve an Algebraic or Transcendal equation.

Filed Under:

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.


Back to main directory:  C++ Assignment    Software Practical


Get Free Programming Tutorials and Solved assignments