V-Lab @ ANDC

Bisection-Method for finding roots of polynomials

Aim

For finding the roots of linear, quadratic and third degree polynomial from Bisection-Method

Theory

What is Bisection Method?

The method is also called the interval halving method, the binary search method or the dichotomy method. This method is used to find root of an equation in a given interval that is value of 'x' for which f(x) = 0. The method is based on The Intermediate Value Theorem which states that if f(x) is a continuous function and there are two real numbers a and b such that f(a)*f(b) 0 and f(b) < 0), then it is guaranteed that it has at least one root between them.

Assumptions:

1. f(x) is a continuous function in interval [a, b].
2. f(a) * f(b) < 0

Procedure

  1. Enter the coefficients of the polynomial.
  2. Enter the iterations you want.
  3. Enter the values of interval
  4. If f(a) * f(b) >0 then enter different intervals.
  5. Else root(c)= (a + b)/2
  6. If f(a) * f(b) < 0 then b=c
  7. Else a = c
  8. Process will run until the desired iteration is reached.
  9. Terminate.

C++ Code

                        
                            // C++ program for implementation of Bisection Method for transcendental equations 
#include<iostream>
#include<iomanip>
#include<math.h> 
using namespace std; 
#define EPSILON 0.000001 
  
// An example function whose solution is determined using 
// Bisection Method. The function is x^3 - x^2  + 2 
double func(double x) 
{ 
    return x*x*x+4*x*x+8.0; 
} 
  
// Prints root of func(x) with error of EPSILON 
void bisection(double a, double b) 
{ 
    if (func(a) * func(b) >= 0) 
    { 
        cout << "You have not assumed right a and b\n"; 
        return; 
    } 
  
    double c = a;
    int step=1; 
    while ((b-a) >= EPSILON) 
    { 
        cout.setf(ios::fixed);
        // Find middle point 
        c = (a+b)/2; 

        if (func(c)*func(a) < 0){ 
            cout<<step<<setw(20)<<a<<setw(20)<<b<<setw(20)<<c<<setw(20)<<func(c)<<endl; 
            b = c;
        }
        else if (func(c)*func(a) > 0){
            cout<<step<<setw(20)<<a<<setw(20)<<b<<setw(20)<<c<<setw(20)<<func(c)<<endl;
            a = c;
        } 
        step+=1;
    } 
    cout << "The value of root is : " << c; 
} 
  
// Driver program to tes above function 
int main() 
{ 
    double x,y,r;
    cout.setf(ios::fixed);
    cout<<setw(35)<<"Bisection Method"<<endl;
    cout<<"********************"<<endl;
    cout<<"The equation is x^3+4x^2+8=0"<<endl;
    cout<<"Enter the intervals...."<<endl;
    cin>>x>>y;
    r=(x+y)/2;
    cout<<"---------------------------------------------------------------------------------"<<endl;
    cout<<"Iteration"<<setw(8)<<"a"<<setw(20)<<"b"<<setw(20)<<"c"<<setw(23)<<"fun(c)"<<endl;
    cout<<"---------------------------------------------------------------------------------"<<endl;
    cout<<0<<setw(20)<<x<<setw(20)<<y<<setw(20)<<r<<setw(20)<<func(r)<<endl;
    bisection(x,y);
}

Observations

Take Observations from the method and tabulate it for the given intervals.

Plot a graph also. (function vs root).

Result

Hence we findout the roots for the given polynomial.

Advantage of the bisection method is that it is guaranteed to be converged. Disadvantage of bisection method is that it cannot detect multiple roots. In general, Bisection method is used to get an initial rough approximation of solution. Then faster converging methods are used to find the solution. We will soon be discussing other methods to solve algebraic and transcendental equations

References

Bisection-Method Wikipedia

Bisection method-on geeksforgeeks