Bisection

Root Finding

Bisection is one of the simplest root-finding methods. It uses the change in sign of a function to help estimate where the root is. The foundation of this method is the area calculation of a rectangle.

Algorithm

Given a continuous function and an interval such that and have opposite signs, the bisection method:

  1. Computes the midpoint
  2. Evaluates
  3. If or the interval is sufficiently small, return
  4. Otherwise, replace the interval with or based on which subinterval contains the root

Python Implementation

The following is a Python implementation:

def bisection(f, a, b, tol=1e-6, max_iter=100):
    """
    Find root of f(x) using bisection method.
    
    Parameters
    ----------
    f : function
        Function whose root we want to find
    a : float
        Left endpoint of interval
    b : float
        Right endpoint of interval
    tol : float
        Tolerance for convergence
    max_iter : int
        Maximum number of iterations
    
    Returns
    -------
    float
        Approximate root
    """
    if f(a) * f(b) > 0:
        raise ValueError("f(a) and f(b) must have opposite signs")
    
    for i in range(max_iter):
        c = (a + b) / 2
        fc = f(c)
        
        if abs(fc) < tol or abs(b - a) < tol:
            return c
        
        if f(a) * fc < 0:
            b = c
        else:
            a = c
    
    return (a + b) / 2

# Example usage
def f(x):
    return x**3 - x - 2  # Root near x ≈ 1.521

root = bisection(f, 1.0, 2.0)
print("Root:", root)

C++ Implementation

The following is a complete C++ implementation with user input:

#include <stdio.h>
#include <math.h>

/* Define the function whose root we want */
double f(double x)
{
    /* Example: f(x) = x^3 - x - 2  (root near x ≈ 1.521) */
    return x*x*x - x - 2.0;
}

int main(void)
{
    double a, b, c;
    double fa, fb, fc;
    double tol;
    int max_iter;
    int iter = 0;

    /* Input */
    printf("Enter left endpoint a: ");
    scanf("%lf", &a);

    printf("Enter right endpoint b: ");
    scanf("%lf", &b);

    printf("Enter tolerance: ");
    scanf("%lf", &tol);

    printf("Enter maximum iterations: ");
    scanf("%d", &max_iter);

    fa = f(a);
    fb = f(b);

    /* Check bracketing condition */
    if (fa * fb > 0.0) {
        printf("Error: f(a) and f(b) must have opposite signs.\n");
        return 1;
    }

    printf("\nIter        a              b              c           f(c)\n");
    printf("----------------------------------------------------------------\n");

    /* Bisection loop */
    while (iter < max_iter) {
        c = 0.5 * (a + b);
        fc = f(c);

        printf("%4d  %14.8f  %14.8f  %14.8f  %14.8f\n",
               iter, a, b, c, fc);

        /* Convergence check */
        if (fabs(fc) < tol || fabs(b - a) < tol) {
            printf("\nConverged to root x = %.10f\n", c);
            return 0;
        }

        /* Update interval */
        if (fa * fc < 0.0) {
            b = c;
            fb = fc;
        } else {
            a = c;
            fa = fc;
        }

        iter++;
    }

    printf("\nMax iterations reached.\n");
    printf("Approximate root x = %.10f\n", c);

    return 0;
}

Convergence

The bisection method converges linearly with rate . After iterations, the error is bounded by:

where is the true root.

Trace it by hand

ProblemThree bisection steps on a cubic
Apply bisection to f(x) = x³ − x − 2 on the bracket [1, 2]. Confirm there's a sign change first, then run three iterations. Report each (lo, hi, mid, f(mid)) and the bracket size at the end.