Bisection Method – Theory, Algorithm, and Code

Theory

The bisection method is the simplest and most reliable iterative method. Also known as binary chopping or half-interval method.

If f(x) is real and continuous, and f(x) & f(x2) are of opposite sign i.e. f(x1)*f(x2) < 0 then there is at least one root in the interval between x1 and x2 i.e. xm = (x1 + x2) / 2

Now, there exist the following three conditions.

1. if f(xm) = 0, root is at xm
2. if f(xm)*f(x1) < 0, root is betn xm & x2
3. if f(xm)*f(x2) < 0, root is betn xm & x1

Then we further bisect the new further interval and continue the process until the root of desire accuracy is determined.

Algorithm

1. Start
2. Define function f(x) and error E (stoping criteria)
3. Read initial values x1 & x2 and funcational value f(x1) & f(x2)
4. Check the bracketing condition
   • if f(x1)*f(x2) > 0; goto step 3
5. Find mid-point, xm = (x1 + x2) / 2 & find f(xm)
6. If |f(xm)| <= E goto step 8
7. If f(xm)*f(x1) < 0
   • set x2 = xm
   • else
     • x1 = xm
   • goto step 5
8. Print root xm
9. Stop

Source Code

#include<iostream>
#include<math.h>
#define f(x) (x*x - 4*x - 10)
#define E 0.0001

using namespace std;

int main() {
    float x1, x2, xm;
    
    do {
        cout<<"Enter two points\n";
        cin>>x1>>x2;
    }while(f(x1)*f(x2) > 0);

    do {
        xm = (x1 + x2) / 2;

        if(f(x1)*f(xm) < 0) {
            x2 = xm;
        }
        else {
            x1 = xm;
        }
    } while(fabs(f(xm))>E);
    
    cout<<"Root is "<<xm;

    return 0;
}

Output

Enter two points
1
-2
Root is -1.74166