Root finding · CMNA Laboratory

The bisection method

Bracket a real root, halve the interval, keep the half that still contains the sign change, and repeat. It is difficult to make glamorous, which is precisely why it is so useful.

The idea

Suppose a continuous function changes sign between a andb. The intermediate value theorem tells us that at least one real root lies between them. Bisection evaluates the midpoint and discards the half-interval that cannot contain the sign change.

Each successful iteration cuts the width of the bracket in half. Aftern steps, the surviving interval is only(b − a) / 2^n wide. That makes the method slower than some alternatives, but unusually transparent: the computation carries its own error bound around with it.

What bisection buys you: if the starting interval really brackets a sign change and the function is continuous, the method does not need a clever initial guess or a derivative. It just keeps making the uncertainty smaller.

bisection <- function(f, a, b, tol = 1e-3, m = 100) {
    iter <- 0
    f.a <- f(a)
    f.b <- f(b)

    while (abs(b - a) > tol) {
        iter <- iter + 1
        if (iter > m) {
            warning("iterations maximum exceeded")
            break
        }
        xmid <- (a + b) / 2
        ymid <- f(xmid)
        if (f.a * ymid > 0) {
            a <- xmid
            f.a <- ymid
        } else {
            b <- xmid
            f.b <- ymid
        }
    }

    root <- (a + b) / 2
    return(root)
}

Experiment

Watch the bracket collapse.

Choose a function and tolerance, then scrub through the iterations. The Murrey endpoints mark the current bracket; the gold point is the midpoint tested at that step.

f(x)

FunctionTolerance

Iteration

n	a	b	midpoint	f(midpoint)	width

Bring your own function

Now remove the training wheels.

Define f as any valid R function, choose an interval, and let the browser run the same bisection logic against your problem. The point here is not merely to get a root: CMNA will unpack why the interval works, what the first sign test does, how the uncertainty shrinks, and exactly why the algorithm stops.

RuntimePreparing R…

RDefine a function named f

abtolerance

Iteration

n	a	b	midpoint	f(midpoint)	width

The function and trace above are evaluated by real R through webR. The teaching trace instruments the current CMNA bisection update rule; the canonical bisection() function itself remains unchanged.

Where bisection sits among root finders

Newton's method can converge much faster when a useful derivative and starting value are available. The secant method estimates that derivative from nearby function values. Bisection trades that speed for a remarkably simple guarantee: preserve the sign-changing bracket and the search region keeps shrinking.

Compare bisection, Newton, and secant on the same functions →

Book§6.1.1 · Bisection Method · p. 166Book details

CMNA packagebisection

R/bisection.R

TeachingInstructor notes and chapter contextOpen teaching material

Numerical ZooWorked problems

Wilkinson's polynomial