Bisection Method

Suppose is a continuous function on the interval such that .

A root exists on the interval chosen above by Intermediate Value Theorem. The bisection method is an iterative algorithm that approximates the root of .

Let the midpoint .

• If , then is the root
• If , then the root lies in , so the interval is updated to
• If , then the root lies in , so the interval is updated to .

Implementation

def bisection(f, a, b, tolerance=1e-6):
    if f(a) * f(b) >= 0:
        raise ValueError("f(a) and f(b) must have opposite signs")
    while (b - a) / 2 > tolerance:
        m = (a + b) / 2
        if f(m) == 0:
            return m
        elif f(a) * f(m) < 0:
            b = m
        else:
            a = m
    return (a + b) / 2

Bisection theorem

Suppose is continuous in and . The bisection generates a sequence such that where is a root of .

Properties

• Always convergent
• Linear convergence rate
• Error can be controlled
• Error is bounded
• Error decreases with each iteration
• Simpler calculations

Limitations

• Slow convergence
• Cannot approximate solutions for even functions and more
• Cannot determine complex roots
• Cannot be applied if there are discontinuities
• Cannot be applied if its sign doesn’t change in the interval