edu.mines.jtk.opt
Class BrentMinFinder

java.lang.Object
  edu.mines.jtk.opt.BrentMinFinder

public class BrentMinFinder
extends java.lang.Object

Brent's algorithm for finding the minimum of a function of one variable. Searches an interval [a,b] for an argument x that minimizes a function f(x).

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.

Version:

2005.09.15

Author:

Dave Hale, Colorado School of Mines

Nested Class Summary

static interface

BrentMinFinder.Function A function f(x) of one variable x.

Constructor Summary

BrentMinFinder(BrentMinFinder.Function f)
Constructs a min finder for the specified function.

Method Summary

double	f(double x) Returns the function value f(x) for the specified argument x.
double	findMin(double a, double b, double tol) Returns an x in the specified interval for which f(x) is a minimum.

Methods inherited from class java.lang.Object

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

Constructor Detail

BrentMinFinder

public BrentMinFinder(BrentMinFinder.Function f)

Constructs a min finder for the specified function.

Parameters:

f - the function to be minimized.

Method Detail

f

public double f(double x)

Returns the function value f(x) for the specified argument x.

Parameters:

x - the argument at which to evaluate f(x).

Returns:

the function value f(x).

findMin

public double findMin(double a,
                      double b,
                      double tol)

Returns an x in the specified interval for which f(x) is a minimum.

Parameters:

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.

Returns:

x for which f(x) is a minimum.