dev.nm.analysis.root.univariate

Class BrentRoot

java.lang.Object

dev.nm.analysis.root.univariate.BrentRoot

All Implemented Interfaces:

Uniroot

public class BrentRoot
extends Object
implements Uniroot

Brent's root-finding algorithm combines super-linear convergence with reliability of bisection. It uses the secant method or inverse quadratic interpolation whenever possible because they converge faster, but falls back to the more robust bisection method if necessary. Unlike NewtonRoot and HalleyRoot, it does not need the derivatives of the function. Brent's algorithm is the preferred method of choice for root-finding.

Finding a root

Supply a continuous function and a finite interval bracketing a root (opposite signs at the endpoints, or an endpoint equal to zero). The three-argument solve overload does not need an initial guess. The tolerance is used in a function-residual stopping test. The algorithm also stops for a sufficiently small bracket or the iteration limit; verify the returned residual when accuracy matters.

Example

 import dev.nm.analysis.function.rn2r1.univariate.AbstractUnivariateRealFunction;
 import dev.nm.analysis.root.univariate.BrentRoot;

 AbstractUnivariateRealFunction f = new AbstractUnivariateRealFunction() {
     public double evaluate(double x) { return x * x - 2.0; }
 };
 double root = new BrentRoot(1e-12, 100).solve(f, 0.0, 2.0);
 assert Math.abs(root - Math.sqrt(2.0)) < 1e-10;
 assert Math.abs(f.evaluate(root)) < 1e-10;
 

See Also:

Wikipedia: Brent's method

Constructor Summary

Constructors

Constructor and Description
BrentRoot(double tol, int maxIterations) Construct an instance of Brent's root finding algorithm.

Method Summary

Modifier and Type	Method and Description
double	solve(UnivariateRealFunction f, double lower, double upper) Finds a root in a bracketing interval.
double	solve(UnivariateRealFunction f, double lower, double upper, double... guess) Search for a root, x, in the interval [lower, upper] such that f(x) = 0.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BrentRoot

public BrentRoot(double tol,
                 int maxIterations)

Construct an instance of Brent's root finding algorithm.

Parameters:

tol - the convergence tolerance

maxIterations - the maximum number of iterations

Method Detail

solve

public double solve(UnivariateRealFunction f,
                    double lower,
                    double upper,
                    double... guess)

Description copied from interface: Uniroot

Search for a root, x, in the interval [lower, upper] such that f(x) = 0.

Specified by:

solve in interface Uniroot

Parameters:

f - a univariate function

lower - the lower bound of the bracketing interval

upper - the upper bound of the bracketing interval

guess - an initial guess of the root within [lower, upper]. Note that guess is a double[]. This signature allows multiple initial guesses for certain types of uniroot algorithms, e.g., Brent's algorithm.

Returns:

an approximate root

solve

public double solve(UnivariateRealFunction f,
                    double lower,
                    double upper)

Finds a root in a bracketing interval.

Parameters:

f - continuous function to evaluate

lower - lower endpoint of the bracket

upper - upper endpoint of the bracket

Returns:

the last root approximation, also when the iteration limit is reached

Throws:

RuntimeException - if both endpoint values have the same strict sign