Ridder’s Method

This documentation was generated with the assistance of AI. Please report any inaccuracies.

Ridder’s method is a variant of false position that, instead of assuming the function is locally linear, factors out the unique exponential function that turns the residual into a straight line — giving quadratic convergence while guaranteeing the root never leaves the bracket. It is described in Press et al., 2007, Section 9.2.1 (page 452), and implemented as RidderSingleRootEstimator in the com.irurueta.numerical.roots package.

Factoring out the exponential bend

Given a bracket , evaluate the function at the midpoint as well. Ridder’s method then solves for the factor that makes:

a quadratic equation in , whose solution is:

Applying false position not to directly, but to the values instead, yields a new root estimate . Substituting the solution for gives the closed-form updating formula actually used:

This single formula has three attractive properties: is guaranteed to fall within , so the method can never jump out of its bracket; its convergence is quadratic ( ); and — since each application costs two function evaluations rather than one — its actual order per evaluation is , still comfortably superlinear. Removing the function’s "bend" via an exponential (ratio) factor, rather than a polynomial fit, turns out to give an unusually robust algorithm in practice.

flowchart TD A["Bracket (x1, x2) with f(x1), f(x2) of opposite sign"] --> B["Evaluate f at midpoint x3"] B --> C["Solve for e^Q; compute x4 via the closed-form update"] C --> D{"x4 within tolerance of\nthe previous estimate?"} D -->|"yes"| E["Return x4 as the root"] D -->|"no"| F["Re-bracket: pick whichever of x1, x3, x2\nstill brackets the root with x4"] F --> B

Library implementation

RidderSingleRootEstimator extends BracketedSingleRootEstimator, sharing the automatic bracket search described in Bisection Method, and adds:

  • getTolerance() / setTolerance(double) — the accuracy to converge to; default 1e-6.

Up to MAXIT = 60 iterations are attempted (two function evaluations each). After estimate() completes, getRoot() returns the estimated root.

Press et al., 2007 considers Ridder’s method a close competitor to Brent’s method as the default choice for general one-dimensional root finding without derivatives — concise, and generally competitive in both speed and reliability.

Example

final var listener = new SingleDimensionFunctionEvaluatorListener() {
    @Override
    public double evaluate(final double point) {
        return point * point - 4.0;
    }
};

final var estimator = new RidderSingleRootEstimator(listener, 0.0, 10.0, 1e-9);
estimator.estimate();

final var root = estimator.getRoot(); // approximately 2.0