Bisection method

The bisection method (or dichotomy) is the most robust algorithm for finding roots of continuous equations f(x) = 0. Based on Bolzano theorem: if f is continuous on [a,b] and f(a) f(b) < 0, there exists at least one root in (a,b). Each iteration halves the interval, guaranteeing convergence.

Geometric idea

Given interval [a,b] with f(a), f(b) opposite signs, compute midpoint c = (a+b)/2 and evaluate f(c). Choose subinterval [a,c] or [c,b] that maintains sign change. Repeat until interval smaller than desired tolerance.

Bolzano theorem

If f: [a,b] -> R is continuous and f(a) f(b) < 0, then there exists at least one c in (a,b) with f(c) = 0. This theorem (Bernhard Bolzano 1817) is the basis of the method. Essential hypotheses: continuity of f and sign change at endpoints.

Algorithm

1. Check f(a) f(b) < 0. If not, error: no sign change.
2. Compute c = (a + b) / 2.
3. Evaluate f(c). If |f(c)| < tolerance or |b-a| < tolerance: STOP, root = c.
4. If f(a) f(c) < 0: new interval [a, c]. Else: [c, b].
5. Return to step 2.

Linear convergence

Each iteration halves interval: |I_n| = (b-a) / 2^n. To get precision eps, need n >= log_2((b-a)/eps) iterations. Example: initial interval [1,2] (width 1), precision 1e-10: n = log_2(10^10) ~ 33 iterations. Machine precision (1e-16): ~ 53 iterations.

Comparison with other methods

• Bisection: order 1 (linear), ALWAYS guaranteed if f changes sign.
• Newton: order 2 (quadratic), fast but may diverge.
• Secant: order phi ~ 1.618, fast but not always convergent.
• Regula falsi: hybrid, robust as bisection but faster.
• Brent: combines bisection + inverse quadratic interpolation, default in scipy.

Advantages

• GUARANTEED convergence by Bolzano hypothesis.
• A priori iteration count: log_2((b-a)/eps).
• Insensitive to derivatives, cusps, oscillations.
• Very simple implementation.
• Robust for black-box functions where f' unavailable.

Disadvantages

• SLOW convergence: 1 binary digit per iter (~ 0.30 decimal digits).
• Needs initial interval with sign change: fails for tangent roots.
• Finds ONE root in interval, not all if multiple exist.
• Doesn't exploit local info (derivative, secant).

Example: sqrt(2) in [1,2]

f(x) = x^2 - 2. f(1) = -1, f(2) = 2 (sign change). Iterations:

• iter 1: c = 1.5, f(c) = 0.25 -> [1, 1.5]
• iter 2: c = 1.25, f(c) = -0.4375 -> [1.25, 1.5]
• iter 3: c = 1.375, f(c) = -0.109 -> [1.375, 1.5]
• iter 4: c = 1.4375, f(c) = 0.066 -> [1.375, 1.4375]
• iter 30: c ~ 1.41421356 (10 digits)
• iter 50: c ~ machine precision

Hybrid strategy

Combining bisection with superlinear methods (secant, Newton) is the best strategy. Algorithms like Brent (1973) or Dekker (1969) use safety bisection when interpolation fails, guaranteeing convergence with practical superlinear speed. Default in scipy.optimize.brentq, MATLAB fzero, R uniroot.

History

Method known to ancients (Babylonians, Heron). Bolzano formalized it in 1817 with intermediate value theorem. Cauchy included it in "Cours d Analyse" (1821) as standard algorithm. Its simplicity and robustness make it still one of the most used as fallback in professional numerical software.

Bisection beyond roots: binary search and optimization

The idea of repeatedly halving an interval goes far beyond root-finding. Binary search, one of the most fundamental algorithms in computer science, is conceptually identical: to find an element in a sorted array one compares the middle value and discards half the candidates at each step, exactly as bisection discards half the interval. Both reach the answer in a number of steps proportional to the logarithm of the problem size.

The same strategy applies to any monotone predicate: the "binary search on the answer" technique solves optimization problems by finding the threshold value beyond which a condition becomes true. For unimodal functions (with a single maximum or minimum) the variant called ternary search divides the interval into three parts and locates the extremum in the same spirit. Bisection is thus the prototype of an entire family of divide-and-conquer algorithms based on halving.

Robustness and limits: when bisection is the right choice

The great merit of bisection is its absolute guarantee: if the function is continuous and changes sign at the endpoints, the method always converges, without exception, and provides a certain error bound, exactly (b-a)/2^n after n steps. This reliability makes it valuable in contexts where failure is not admissible, and as a safety component in hybrid methods that combine it with Newton or the secant to unite guarantee and speed.

Its limits are equally clear. Bisection cannot find roots of even multiplicity, where the function touches the axis without changing sign, nor complex roots, nor several roots contained in the same interval (it isolates only one). Its linear convergence, gaining about one decimal digit every 3-4 iterations, is slow compared to superlinear methods. It is the ideal tool when safety matters more than speed, or as a safety net for more aggressive methods.

Updated July 2026