Bisection Method — Guaranteed Numerical Root Finding

Bisection is the simplest application of the Intermediate Value Theorem: if f is continuous and f(a) < 0 and f(b) > 0, then somewhere in [a,b] the function crosses zero. The algorithm just applies this fact repeatedly, halving the interval each time.

The guaranteed convergence of bisection makes it invaluable as a safety net. Bisection cannot diverge, cannot oscillate, cannot fail as long as the initial bracket is valid. This is why Brent's method — the gold standard for numerical root finding, used in scipy.optimize.brentq — combines bisection as a fallback with Newton-Raphson's quadratic convergence: the speed of Newton when near the root, the reliability of bisection everywhere else.

Algorithm and Implementation

Invariant: f(a) and f(b) have opposite signs → root in [a,b]. Each step halves the interval.

def bisection(f, a: float, b: float, tol: float = 1e-10, max_iter: int = 100) -> float:
    """
    Find root of f in [a,b] where f(a)*f(b) < 0.
    Guaranteed to converge for continuous functions.
    """
    if f(a) * f(b) > 0:
        raise ValueError('f(a) and f(b) must have opposite signs')
    for i in range(max_iter):
        mid = (a + b) / 2
        if abs(b - a) / 2 < tol or f(mid) == 0:
            print(f'Converged in {i+1} iterations, root ≈ {mid}')
            return mid
        if f(a) * f(mid) < 0:
            b = mid  # root in [a, mid]
        else:
            a = mid  # root in [mid, b]
    return (a + b) / 2

import math
# Find sqrt(2): f(x) = x^2 - 2
root = bisection(lambda x: x**2 - 2, 1, 2)
print(f'sqrt(2) = {root}')

# Find x where cos(x) = x (Dottie number)
root2 = bisection(lambda x: math.cos(x) - x, 0, 1)
print(f'cos(x)=x: x = {root2:.10f}')

Error Analysis and Convergence

After n iterations, the interval width is (b-a)/2^n. The error is bounded by this width.

To achieve precision ε: n ≥ log2((b-a)/ε) iterations.

For [1,2] with ε=10^-10: n ≥ log2(1/10^-10) = 10×log2(10) ≈ 33.2 → 34 iterations.

import math

def bisection_with_trace(f, a, b, n_steps=10):
    fa = f(a)
    print(f'Step  a              b              mid            f(mid)')
    for i in range(n_steps):
        mid = (a + b) / 2
        fmid = f(mid)
        print(f'{i+1:4}  {a:.10f}  {b:.10f}  {mid:.10f}  {fmid:+.2e}')
        if fa * fmid < 0:
            b, _ = mid, fmid
        else:
            a, fa = mid, fmid

bisection_with_trace(lambda x: x**2 - 2, 1.0, 2.0, 8)

Bisection vs Newton-Raphson

| Property | Bisection | Newton-Raphson | |---|---|---| | Convergence | Linear (1 bit/step) | Quadratic (doubles digits) | | Iterations for 10^-10 | ~34 | ~5 | | Requires derivative | No | Yes | | Guaranteed convergence | Yes (given bracket) | No | | Initial requirement | Bracket [a,b] | Single guess x0 |

Best practice: Use bisection to get close (10^-3 precision), then switch to Newton-Raphson for fast final convergence. This is essentially Brent's method.

Frequently Asked Questions