edu.mines.jtk.opt
Class BrentZeroFinder

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

public class BrentZeroFinder
extends java.lang.Object

Brent's algorithm for finding a zero of a function of one variable. Searches an interval [a,b] for an argument x for which a function f(x) = 0.

This algorithm uses a combination of bisection and inverse linear and/or quadratic interpolation. Convergence is never much slower than that for bisection. If f(x) has a continuous second derivative near a simple zero, then the algorithm will tend towards superlinear convergence of order at least 1.618.

Let xzero be the argument x that results from a search for the zero. That search is terminated when the difference between xzero and the true zeroing argument x is less than tol+4*EPS*abs(xzero), where tol is a specified tolerance and EPS is DBL_EPSILON (approximately 1.0e-16), machine epsilon for IEEE double precision arithmetic.

This implementation is adapted from the Fortran subroutine ZEROIN, 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:

2001.07.10, 2006.07.12

Author:

Dave Hale, Colorado School of Mines

Nested Class Summary

static interface

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

Constructor Summary

BrentZeroFinder(BrentZeroFinder.Function f)
Constructs a zero finder for the specified function.

Method Summary

double	f(double x) Returns the function value f(x) for the specified argument x.
double	findZero(double a, double b, double tol) Finds a zero within the specified search interval [a,b].
double	findZero(double a, double fa, double b, double fb, double tol) Finds a zero within the specified search interval [a,b], beginning with specified function values f(a) and f(b), which must not have the same sign.

Methods inherited from class java.lang.Object

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

Constructor Detail

BrentZeroFinder

public BrentZeroFinder(BrentZeroFinder.Function f)

Constructs a zero finder for the specified function.

Parameters:

f - the function.

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).

findZero

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

Finds a zero within the specified search interval [a,b]. The function values f(a) and f(b) must not have the same sign.

Parameters:

a - the lower limit of the search interval.

b - the upper limit of the search interval.

tol - the accuracy with which to find the zero.

Returns:

the abscissa x for which f(x) is approximately zero.

findZero

public double findZero(double a,
                       double fa,
                       double b,
                       double fb,
                       double tol)

Finds a zero within the specified search interval [a,b], beginning with specified function values f(a) and f(b), which must not have the same sign.

Parameters:

a - the lower limit of the search interval.

fa - the function f(x) evaluated at x = a.

b - the upper limit of the search interval.

fb - the function f(x) evaluated at x = b.

tol - the accuracy with which to find the zero.

Returns:

the abscissa x for which f(x) is approximately zero.