Bisection Method

A deterministic root-finding method grounded in the Intermediate Value Theorem. By repeatedly halving an interval where a sign change is detected, the algorithm traps the root in a window that shrinks by exactly half at each step — guaranteeing linear convergence at a predictable rate of log₂(|b−a|/ε) iterations.

Historical Context

Iterative interval halving was practiced long before it was understood. Mathematicians such as Lagrange and Fourier used halving heuristics in the 18th century to locate roots of polynomials — effective in practice, yet entirely without proof. The idea that a continuous function must cross zero somewhere between a positive and a negative value was accepted as geometrically self-evident, not as a theorem requiring demonstration.

That changed in 1817, when the Bohemian mathematician Bernard Bolzano published his landmark paper Rein analytischer Beweis — a “purely analytical proof” of what we now call the Intermediate Value Theorem. Bolzano was motivated by a philosophical conviction: geometry should play no role in the foundations of analysis. His proof, built entirely from the definition of continuity, was a watershed in mathematical rigor.

Bolzano's work was largely ignored during his lifetime. Augustin-Louis Cauchy independently re-proved the IVT in 1821, and it is his formulation that most textbooks carry today. Yet the bisection algorithm stands as the direct computational artifact of that theoretical revolution: the first root-finding procedure with a guaranteed convergence bound. For any continuous function on a valid interval, it will always converge — halving the error with every step.

Geometric Foundation: The IVT Trap

Bound (a)0.50

Bound (b)2.00

Intermediate Value Theorem

For a continuous curve, if

f(a)

and

f(b)

have opposite signs, the curve must cross the x-axis at least once between them.

f(a) \times f(b) = -3.50

< 0 (Valid)

f(x) = x^3 - x - 2

Geometric View

c_n = \frac{1}{2}(a_n + b_n)

Invalid Interval

Same sign detected. No root guaranteed.

Convergence Plot

Each step reduces the error. On a logarithmic scale, convergence patterns form straight lines.

Interval [a, b]

Stop Criterion

Tolerance (ε)

Speed

Invalid input.

Error Bound |b - a|

Current State

Not initialized.

Algorithm

c = (a + b) / 2if f(c) == 0 or (b-a)/2 < ε:return cif sign(f(c)) == sign(f(a)):a = celse:b = c

Why it works

The Bisection method relies on the Intermediate Value Theorem (IVT). If a continuous function $f(x)$ has opposite signs at the endpoints of an interval $[a, b]$ , i.e.,

f(a) \cdot f(b) < 0

then the function must cross zero at least once within that interval.

We simply halve the interval repeatedly at midpoint $c = \frac{a+b}{2}$ . By evaluating $f(c)$ , we determine which sub-interval $[a, c]$ or $[c, b]$ contains the root and discard the other, shrinking the error bound exponentially:

|x_n - x^*| \leq \frac{b - a}{2^n}

A Priori Error Bound

A unique property of Bisection is that we can determine exactly how many iterations are needed to achieve a desired tolerance $\epsilon$ before we even start, using the formula:

n \ge \log_2\left(\frac{b - a}{\epsilon}\right)

The Failure Mode

Bisection requires the function to have opposite signs at the interval endpoints (a strict sign change). If we provide an interval where $f(a)$ and $f(b)$ have the same sign, the algorithm cannot guarantee a root exists, and mathematically cannot determine which sub-interval to search.

Output

Output will appear here after running the code

Bisection is guaranteed but slow. What if we just turn it into a fixed-point problem?Fixed Point Iteration →