public class BrentMinFinder
extends java.lang.Object
Brent's algorithm uses a combination of golden section search and successive parabolic interpolation. Convergence is never much slower than that for a Fibonacci search. If the function f(x) has a continuous second derivative that is positive at the minimum (which is not at the endpoints a or b, then convergence is superlinear, and usually of the order of about 1.324.
Let xmin be the argument x that results from a search for the minimum. That search is terminated when the difference between xmin and the true minimizing argument x is less than a specified tolerance. The function f(x) is never evaluated at two points closer together than EPS*abs(xmin)+tol/3, where EPS is approximately 1.0e-8, the square root of machine epsilon for IEEE double precision arithmetic, and tol is a specified tolerance.
If f(x) is a unimodal function and if the computed values of f(x) are always unimodal for arguments x separated by at least EPS*abs(x)+tol/3, then xmin approximates the global minimum of f(x) on the interval [a,b] with an error less than 3*EPS*abs(xmin)+tol. If f(x) is not unimodal, then xmin may approximate a local, but perhaps not global, minimum to the same accuracy.
This implementation is adapted from the Fortran function FMIN, by Forsythe, G.E., Malcolm, M.A., and Moler, C.B. 1977, Computer Methods for Mathematical Computations, Prentice Hall. That Fortran function is, in turn, a translation of the Algol 60 program by Brent, R., 1973, Algorithms for Minimization Without Derivatives, Prentice Hall.
Modifier and Type | Class and Description |
---|---|
static interface |
BrentMinFinder.Function
A function f(x) of one variable x.
|
Constructor and Description |
---|
BrentMinFinder(BrentMinFinder.Function f)
Constructs a min finder for the specified function.
|
public BrentMinFinder(BrentMinFinder.Function f)
f
- the function to be minimized.public double f(double x)
x
- the argument at which to evaluate f(x).public double findMin(double a, double b, double tol)
a
- the smallest value of x in the interval.b
- the largest value of x in the interval.tol
- the search tolerance; see notes above.