edu.northwestern.at.utils.math.rootfinders
Class Brent

java.lang.Object
  edu.northwestern.at.utils.math.rootfinders.Brent

All Implemented Interfaces:

MonadicFunctionRootFinder

public class Brent
extends java.lang.Object
implements MonadicFunctionRootFinder

Find a root of a function using Brent's method which combines quadratic interpolation with the method of bisection.

Brent's method requires as input an initial interval [x0,x1] which brackets one (or an odd number) of roots.

During each iteration Brent's method constructs an interpolation curve to approximate the function. For the initial iteration this is a simple linear interpolation using the initially supplied endpoints of the interval bracketing the root. For subsequent iterations the interpolation curve is an inverse quadratic fit to the last three points. The intercept of the interpolation curve with the x-axis provides the root approximation. If this value lies within the bounds of the current root bracketing interval the interpolation point is accepted and used to narrow the interval. If the interpolated value lies outside the bounds of the current interval the algorithm switches to bisection steps to narrow the interval. The algorithm switches between quadratic interpolation and bisection as often as necessary to ensure convergence.

The best estimate of the root is taken from the most recent interpolation or bisection after the value is found to a specified tolerance or a specified number of iterations is exhausted.

See Brent, Richard P. Algorithms for minimization without derivatives. Mineola, N.Y. : Dover Publications, 2002.

and

Brent, R. P. An algorithm with guaranteed convergence for finding the zero of a function. The Computer Journal vol. 14, no. 4, pp. 422-425.

This Java code is a fairly straightforward translation of Brent's original Algol 60 version as published in his paper in The Computer Journal.

Constructor Summary

Brent()
Constructor if RootFinder interface used.

Method Summary

static double	brent(double x0, double x1, double tol, int maxIter, MonadicFunction function) Find root of a function using Brent's method.
static double	brent(double x0, double x1, double tol, int maxIter, MonadicFunction function, RootFinderConvergenceTest convergenceTest, RootFinderIterationInformation iterationInformation) Find root of a function using Brent's method.
static double	brent(double x0, double x1, MonadicFunction function) Find root of a function using Brent's method.
double	findRoot(double x0, double x1, double tol, int maxIter, MonadicFunction function, MonadicFunction derivativeFunction, RootFinderConvergenceTest convergenceTest, RootFinderIterationInformation iterationInformation) Implementation for MonadicFunctionRootFinder interface.

Methods inherited from class java.lang.Object

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

Constructor Detail

Brent

public Brent()

Constructor if RootFinder interface used.

Method Detail

brent

public static double brent(double x0,
                           double x1,
                           double tol,
                           int maxIter,
                           MonadicFunction function,
                           RootFinderConvergenceTest convergenceTest,
                           RootFinderIterationInformation iterationInformation)
                    throws java.lang.IllegalArgumentException

Find root of a function using Brent's method.

Parameters:

x0 - Left endpoint of interval containing root.

x1 - Right endpoint of interval containing root.

tol - Convergence tolerance to which root is computed.

maxIter - Maximum number of iterations.

function - The function whose root to find.

convergenceTest - RootFinderConvergenceTest which tests for convergence of the root-finding process.

iterationInformation - Class implementing RootFinderIterationInformation for retrieving information about each iteration of root finding process. Set to null if you don't want this information.

Returns:

Root of function in interval [x0,x1] .

Throws:

InvalidArgumentException - when [x0,x1] does not contain root and the attempt to expand the interval to contain a root fails.

Function must have an odd # of roots in the interval [x0,x1] .

java.lang.IllegalArgumentException

brent

public static double brent(double x0,
                           double x1,
                           double tol,
                           int maxIter,
                           MonadicFunction function)
                    throws java.lang.IllegalArgumentException

Find root of a function using Brent's method.

Parameters:

x0 - Left endpoint of interval containing root.

x1 - Right endpoint of interval containing root.

tol - Convergence tolerance to which root is computed.

maxIter - Maximum number of iterations.

function - The function whose root to find.

Returns:

Root of function in interval [x0,x1] .

Throws:

InvalidArgumentException - when [x0,x1] does not contain root and the attempt to expand the interval to contain a root fails.

Function must have an odd # of roots in the interval [x0,x1] .

java.lang.IllegalArgumentException

brent

public static double brent(double x0,
                           double x1,
                           MonadicFunction function)
                    throws java.lang.IllegalArgumentException

Find root of a function using Brent's method.

Parameters:

x0 - Left endpoint of interval containing root.

x1 - Right endpoint of interval containing root.

function - The function whose root to find.

Returns:

Root of function in interval [x0,x1] .

Throws:

InvalidArgumentException - when [x0,x1] does not contain root and the attempt to expand the interval to contain a root fails.

Function must have an odd # of roots in the interval [x0,x1] . Up to 100 iterations are attempted with a convergence tolerance set to Constants.MACHEPS .

java.lang.IllegalArgumentException

findRoot

public double findRoot(double x0,
                       double x1,
                       double tol,
                       int maxIter,
                       MonadicFunction function,
                       MonadicFunction derivativeFunction,
                       RootFinderConvergenceTest convergenceTest,
                       RootFinderIterationInformation iterationInformation)
                throws java.lang.IllegalArgumentException

Implementation for MonadicFunctionRootFinder interface.

Specified by:

findRoot in interface MonadicFunctionRootFinder

Parameters:

x0 - Left bracket value for root.

x1 - Right bracket value for root. Not used by some root-finder (e.g., Newton/Raphson), set to same value as x0 in those cases.

tol - Convergence tolerance.

maxIter - Maximum number of iterations.

function - MonadicFunction computes value for function whose root is being sought.

derivativeFunction - MonadicFunction computes derivative value for function whose root is being sought. Currently used only by Newton/Raphson, set to null for other methods.

convergenceTest - RootFinderConvergenceTest which tests for convergence of the root-finding process.

iterationInformation - Method implementing the RootFinderIterationInformation interace. Allows retrieval of function, function derivative, and iteration number for each iteration in the root-finding process. Can be set to null if you don't want to get that information.

Throws:

java.lang.IllegalArgumentException