Root Finding Using Bisection Method

Bisection Method:

Many problems require to find the roots/zeros of the function:

                                                                  f(x) = 0          --------(i)

If the function f(x) is continuous between two limits, x = a and b, and f(a) and f(b) are of opposite signs,

means f(a)*f(b) < 0, then there exists a root between a and b.

Let us think the root is δ, then   f(δ) = 0

From the above figure, we can see that if f(a)*f(b) < 0 means f(a) and f(b) are of opposite signs, then we

can approximated the root by midpoint, xm = (a + b)/2. Then if f(xm) = 0, the root is xm .If not, we

have to search the root in either of interval [xm, a] or [xm, b] if f(xm)*f(a) < 0 then we will take b = xm

and if f(xm)*f(b) < 0, then a = xm, and the guessed root as, xm = (a +b)/2, we have to repeat this

 process untill the desired accuracy.

Algorithms:

1. We have to guess two initial points, a and b. If f(a)*f(b) > 0, then there is no root in the [a, b] interval.

2.  If f(a)*f(b) < 0, we will take, xm = (a + b)/2.

3.  If f(xm) = 0, then root is xm.

4. If not, then for f(a)*f(xm), we will make b = xm and for f(b)*f(xm), we will make a = xm.

5. We will repeat this process untill, |b - a| > tolerance, we have to set the tolerance.

Python code:

Input:

import numpy as np  #necessary package

def Bisect(f, a, b, tol):

    if f(a) * f(b) < 0:

        print('No root in this interval')

    else:

        while abs(b - a) > tol:

            xm = (a + b)/2

            if f(xm) == 0: return xm

            

            if f(xm) * f(a) < 0:

                b = xm

            else:

                a = xm

        return (a + b)/2

def f(x): return 2*np.cos(x) - 1

a = 0                 #Lower limit

b = 7                 #Upper Limit

tol = 1e-8          #tolerance

root = Bisect(f, a, b, tol)

print('Root of this equation : ',root)

Output:

Root of this equation :  1.0471975528635085

References:

1.   www.python.org

2.   Computational Problems for Physics With Guided Solutions Using Python - Rubin H. Landau, Manuel José Páez (CRC Press)

3.  Scientific Computing in Python (3rd edition) - Abhijit Kar Gupta (Techno World, Kolkata)