1D Root Finding: Bracketing Methods

Overview

Bracketing algorithms solve $f(x) = 0$ given two points $[a, b]$ with $f(a) \cdot f(b) < 0$, shrinking the interval at every step. By the intermediate value theorem, a continuous function with sign change must have a root in $[a, b]$, and these methods guarantee convergence.

Related API: bisection, false_position, ridders_method, brent_method, toms748.

Bisection

Halve the interval at the midpoint and keep the half with a sign change. Simplest and most reliable.

while (b - a > tol) {
    T c = (a + b) / 2;
    if (sign(f(c)) == sign(f(a))) a = c;
    else                          b = c;
}

Each iteration halves the interval, so the iteration count for tolerance $\epsilon$ is exactly $\lceil \log_2((b - a)/\epsilon) \rceil$.

Convergence order: linear (contraction ratio $1/2$).

Pros: guaranteed convergence for continuous functions; exact worst-case iteration count.

Cons: ignores function values entirely, so slow in practice.

False Position (Regula Falsi)

Instead of the midpoint, use the weighted internal point determined by function values:

$$c = a - f(a) \cdot \frac{b - a}{f(b) - f(a)} = \frac{a f(b) - b f(a)}{f(b) - f(a)}.$$

This is the zero of the line through $(a, f(a))$ and $(b, f(b))$. Unlike the secant method, false position always retains the bracket by keeping the sign-changing endpoint.

Convergence order: superlinear in general, but degrades to linear when $f$ is strongly convex/concave on one side and one endpoint refuses to move.

Illinois and Anderson-Björck

When false position gets "stuck" with one endpoint frozen, these variants shrink the frozen-side function value to force movement.

• Illinois: if the same endpoint is kept twice in a row, multiply its $f$-value by $1/2$.
• Anderson-Björck: choose the shrink factor dynamically as $f(c)/(f(c) + f_{\text{stuck}})$. More robust than Illinois.

These classical fixes restore superlinear convergence and were standard prior to Brent's method. Today they are mostly subsumed by Brent / TOMS 748, but they remain useful as low-dependency alternatives.

Ridders' Method

Ridders (1979) evaluates $f$ at the midpoint $m = (a+b)/2$ and applies an exponential correction to effectively linearize $f$:

$$c = m + (m - a) \cdot \frac{\mathrm{sign}(f(a)) \cdot f(m)}{\sqrt{f(m)^2 - f(a) f(b)}}.$$

$c$ is guaranteed to lie inside $[a, b]$, and the bracket is updated by sign. Two function evaluations per iteration, but the average iteration count is much smaller than bisection.

Convergence order: $\sqrt{2} \approx 1.41$ per iteration (i.e. $2^{1/2} \approx 1.19$ per function evaluation).

Brent's Method

Brent (1973) combines fast candidates from inverse quadratic interpolation (IQI) or the secant method with bisection fallback:

1. From three points $(a, f(a))$, $(b, f(b))$, $(c, f(c))$, compute the next candidate $s$ by IQI.
2. Accept $s$ only if it lies in the interval and several safety conditions ("the step is short enough", "the previous step was also short", etc.) hold.
3. Otherwise fall back to a bisection step.

This delivers superlinear convergence with the safety of bisection. Brent's original paper defines four switching conditions (Brent's conditions) that rigorously bound the worst case.

Convergence order: superlinear (typically 1.6–1.8 in practice).

Pros: Newton-level speed without a derivative.

Cons: can be slower than bisection on Dekker-style adversarial inputs.

sangi's brent_method is the recommended general-purpose bracketing path.

TOMS 748 (Alefeld-Potra-Shi)

Alefeld, Potra, and Shi (1995) improved on Brent and shipped the result as ACM TOMS Algorithm 748. It replaces IQI with cubic rational interpolation and double cubic interpolation, sharpening the worst-case iteration count.

Convergence order: asymptotically about $1.84$ per function evaluation.

More robust than Brent on outliers and pathological curves. sangi's toms748 implements it.

The ITP Method (Interpolation-Truncation-Projection)

A recent bracketing scheme by Oliveira and Takahashi (2020). The next point is determined in three steps:

1. Interpolation: compute the secant candidate $x_f$ (Regula Falsi).
2. Truncation: truncate $x_f$ toward the midpoint to obtain $x_t$.
3. Projection: project so the bisection contraction is never exceeded, giving $x_{\text{ITP}}$.

The parameters $\kappa_1 \in [0, \infty)$, $\kappa_2 \in [1, (3+\sqrt 5)/2)$, $n_0 \in \mathbb{N}$ are chosen so that the method matches Brent's superlinear convergence while provably guaranteeing the worst-case iteration count never exceeds bisection. Neither Brent nor TOMS 748 can offer this guarantee in principle.

Convergence order: superlinear (Brent-level); worst case $\leq$ bisection.

The ITP method is on sangi's roadmap as an additional bracketing path. Today the default is Brent; bisection is used when worst-case guarantees are required.

Convergence Order and Worst-Case Comparison

Selection in sangi

Default: Brent

For smooth, "not particularly pathological" functions, brent_method is the best general-purpose choice. It does not need a derivative and achieves a practical convergence ratio of 1.6–1.8.

Hard inputs: TOMS 748

For curves with outliers, steps, or close-together roots, toms748 is more robust. Its cubic rational interpolation handles a broader function class than Brent.

Worst-case guarantee: bisection (or future ITP)

If a deterministic upper bound on iterations is required (embedded systems, real-time control), use bisection. The cost is predictable but the convergence rate is the slowest of all methods. The ITP method offers both speed and a worst-case guarantee but is not yet shipped in sangi.

When to avoid the Brent family

For minimal-dependency teaching code, or when function evaluations are extremely expensive (seconds each), Ridders' method becomes attractive. It uses two evaluations per iteration but typically converges in very few iterations overall.

References

• Brent, R. P. (1973). Algorithms for Minimization without Derivatives. Prentice-Hall.
• Alefeld, G. E., Potra, F. A., and Shi, Y. (1995). "Algorithm 748: enclosing zeros of continuous functions". ACM Transactions on Mathematical Software, 21(3), 327–344.
• Ridders, C. (1979). "A new algorithm for computing a single root of a real continuous function". IEEE Transactions on Circuits and Systems, 26(11), 979–980.
• Oliveira, I. F. D. and Takahashi, R. H. C. (2020). "An enhancement of the bisection method average performance preserving minmax optimality". ACM Transactions on Mathematical Software, 47(1), 1–24.