1. Home
  2. Docs
  3. Numerical Methods
  4. Solution of Nonlinear Equations
  5. Bisection Method

Bisection Method

Introduction

  • Simplest method
  • Convergent
  • Requires initial guesses
  • Closed bracket method
  • Also known as binary chopping or half interval method

This method is based on the immediate value theorem which states that if f(x) is continuous in the interval [x_1,x_2] and f(x_1) and f(x_2) has different signs then the equation f(x)=0 has atleast one root between x_1 and x_2.

Here mid-point x_0 = {{x_1+x_2} \over 2}

This gives us two new intervals [x_1,x_0] & [x_0, x_2].

if f(x_0) = 0 then x_0 is the root of f(x). Otherwise, if f(x_0) \times f(x_1) < 0 then the root lies between x_0 & x_2. Then we bisect the interval as before and continue the process until we meet the accuracy as defined.

Bisection
Bisection

Algorithm

1. Define function f(x) and error
2. Guess two initial values x_1 and x_2
3. Compute f(x_1) and f(x_2)
4. If f(x_1) \times f(x_2) > 0
    goto step 8, otherwise
5. Calculate x_0 = {{x_1 + x_2} \over {2}}
6. Check if | f(x_0)| > error
    if f(x_0) \times f(x_1) > 0
        x_1 = x_0
    else
        x_2 = x_0
    goto step 5
7. Print root = x_0
8. End

Psuedocode

FUNCTION Bisect(xl, xu, es, imax, xr, iter, ea)
   iter = 0
   DO
      xrold = xr
      xr = (xl 1 xu) / 2
      iter = iter 1 1
      IF xr ? 0 THEN
         ea = ABS((xr 2 xrold) / xr) * 100
      END IF
      test = f(xl) * f(xr)
      IF test , 0 THEN
         xu = xr
      ELSE IF test . 0 THEN
         xl = xr
      ELSE
         ea = 0
      END IF
      IF ea < es OR iter >= imax EXIT
   END DO
   Bisect = xr
END Bisect

Code

C Program

float bisection(float x1, float x2, int n){
    float x, fx1, fx2;
    int i;
    for(i = 0; i < n; i++){
        x = (x1 + x2)/2;
        fx1 = fn(x1);
        fx2 = fn(x2);
        if(fx1*fx2 < 0){
            x1 = x;
        }
        else{
            x2 = x;
        }
    }
    return x;
}
 float fn(float x){
    return x*x*x - 2*x - 5;
 }

Javascript

Function for bisection

function bisection(a,b,n,f)
{
    var x = (a+b)/2;
    var e = Math.pow(10, -n);
    var i = 0;
    while(Math.abs(f(x))>e)
    {
        if(f(a)*f(x)<0)
        {
            b = x;
        }
        else
        {
            a = x;
        }
        x = (a+b)/2;
        i++;
        console.log(x)
    }
    return x;
}

The function representing x^3 - 2x - 5 = 0

function f(x)
{
    return x*x*x -2*x - 5;
}
console.log(bisection(2,3,3,f));
Output : 

2.25
2.125
2.0625
2.09375
2.109375
2.1015625
2.09765625
2.095703125
2.0947265625
2.09423828125
2.094482421875
2.094482421875

Convergence

In Bisection method interval is halved in every iteration. After n^{th} iteration size of interval is reduced to

    \[ {{x_2-x_1} \over {2^n}} = { \Delta x \over 2^n }  \]

Now we can say that maximum error after n^{th} iteration is E_n = \pm {\Delta x \over 2^n }

    \[ | E_n | = \Delta x \over 2^n \]

Similarly, after (n+1)^{th} iteration maximum error is given by

    \[ E_{n+1} = |{ \Delta x \over 2^{n+1} } | = {E_n \over 2} \]

This equation shows that error is halved after each iteration of bisection method. Therefore, we can say tat the bisection method converges linearly.

Advantages

  1. The bisection method is always convergent. Since, the method brackets the roots, the method guaranteed to converge.
  2. Assiteration are conducted, the interval gets halved. So one can guarantee the decrease in the error in the solution of the equation.

Disadvantages

  1. The convergence of bisection method is slow as it is simply based on halving the interval.
  2. If one of the initial guesses is closer to the root, it will take larger number of iterations to reach the root.
Was this article helpful to you? Yes No

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *