org.apache.commons.math3.analysis.solvers
Class BracketingNthOrderBrentSolver

java.lang.Object
  org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver<UnivariateFunction>
      org.apache.commons.math3.analysis.solvers.AbstractUnivariateSolver
          org.apache.commons.math3.analysis.solvers.BracketingNthOrderBrentSolver

All Implemented Interfaces:

BaseUnivariateSolver<UnivariateFunction>, BracketedUnivariateSolver<UnivariateFunction>, UnivariateSolver

public class BracketingNthOrderBrentSolver
extends AbstractUnivariateSolver
implements BracketedUnivariateSolver<UnivariateFunction>

This class implements a modification of the Brent algorithm.

The changes with respect to the original Brent algorithm are:

• the returned value is chosen in the current interval according to user specified AllowedSolution,
• the maximal order for the invert polynomial root search is user-specified instead of being invert quadratic only

The given interval must bracket the root.

Version:

$Id: BracketingNthOrderBrentSolver.java 1379560 2012-08-31 19:40:30Z erans $

Field Summary

private AllowedSolution	allowed The kinds of solutions that the algorithm may accept.
private static double	DEFAULT_ABSOLUTE_ACCURACY Default absolute accuracy.
private static int	DEFAULT_MAXIMAL_ORDER Default maximal order.
private static int	MAXIMAL_AGING Maximal aging triggering an attempt to balance the bracketing interval.
private int	maximalOrder Maximal order.
private static double	REDUCTION_FACTOR Reduction factor for attempts to balance the bracketing interval.

Constructor Summary

BracketingNthOrderBrentSolver()
Construct a solver with default accuracy and maximal order (1e-6 and 5 respectively)

BracketingNthOrderBrentSolver(double relativeAccuracy, double absoluteAccuracy, double functionValueAccuracy, int maximalOrder)
Construct a solver.

BracketingNthOrderBrentSolver(double relativeAccuracy, double absoluteAccuracy, int maximalOrder)
Construct a solver.

BracketingNthOrderBrentSolver(double absoluteAccuracy, int maximalOrder)
Construct a solver.

Method Summary

protected double	doSolve() Method for implementing actual optimization algorithms in derived classes.
int	getMaximalOrder() Get the maximal order.
private double	guessX(double targetY, double[] x, double[] y, int start, int end) Guess an x value by nth order inverse polynomial interpolation.
double	solve(int maxEval, UnivariateFunction f, double min, double max, AllowedSolution allowedSolution) Solve for a zero in the given interval.
double	solve(int maxEval, UnivariateFunction f, double min, double max, double startValue, AllowedSolution allowedSolution) Solve for a zero in the given interval, start at startValue.

Methods inherited from class org.apache.commons.math3.analysis.solvers.BaseAbstractUnivariateSolver

computeObjectiveValue, getAbsoluteAccuracy, getEvaluations, getFunctionValueAccuracy, getMax, getMaxEvaluations, getMin, getRelativeAccuracy, getStartValue, incrementEvaluationCount, isBracketing, isSequence, setup, solve, solve, solve, verifyBracketing, verifyInterval, verifySequence

Methods inherited from class java.lang.Object

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

Methods inherited from interface org.apache.commons.math3.analysis.solvers.BaseUnivariateSolver

getAbsoluteAccuracy, getEvaluations, getFunctionValueAccuracy, getMaxEvaluations, getRelativeAccuracy, solve, solve, solve

Field Detail

DEFAULT_ABSOLUTE_ACCURACY

private static final double DEFAULT_ABSOLUTE_ACCURACY

Default absolute accuracy.

See Also:

Constant Field Values

DEFAULT_MAXIMAL_ORDER

private static final int DEFAULT_MAXIMAL_ORDER

Default maximal order.

See Also:

Constant Field Values

MAXIMAL_AGING

private static final int MAXIMAL_AGING

Maximal aging triggering an attempt to balance the bracketing interval.

See Also:

Constant Field Values

REDUCTION_FACTOR

private static final double REDUCTION_FACTOR

Reduction factor for attempts to balance the bracketing interval.

See Also:

Constant Field Values

maximalOrder

private final int maximalOrder

Maximal order.

allowed

private AllowedSolution allowed

The kinds of solutions that the algorithm may accept.

Constructor Detail

BracketingNthOrderBrentSolver

public BracketingNthOrderBrentSolver()

Construct a solver with default accuracy and maximal order (1e-6 and 5 respectively)

BracketingNthOrderBrentSolver

public BracketingNthOrderBrentSolver(double absoluteAccuracy,
                                     int maximalOrder)
                              throws NumberIsTooSmallException

Construct a solver.

Parameters:

absoluteAccuracy - Absolute accuracy.

maximalOrder - maximal order.

Throws:

NumberIsTooSmallException - if maximal order is lower than 2

BracketingNthOrderBrentSolver

public BracketingNthOrderBrentSolver(double relativeAccuracy,
                                     double absoluteAccuracy,
                                     int maximalOrder)
                              throws NumberIsTooSmallException

Construct a solver.

Parameters:

relativeAccuracy - Relative accuracy.

absoluteAccuracy - Absolute accuracy.

maximalOrder - maximal order.

Throws:

NumberIsTooSmallException - if maximal order is lower than 2

BracketingNthOrderBrentSolver

public BracketingNthOrderBrentSolver(double relativeAccuracy,
                                     double absoluteAccuracy,
                                     double functionValueAccuracy,
                                     int maximalOrder)
                              throws NumberIsTooSmallException

Construct a solver.

Parameters:

relativeAccuracy - Relative accuracy.

absoluteAccuracy - Absolute accuracy.

functionValueAccuracy - Function value accuracy.

maximalOrder - maximal order.

Throws:

NumberIsTooSmallException - if maximal order is lower than 2

Method Detail

getMaximalOrder

public int getMaximalOrder()

Get the maximal order.

Returns:

maximal order

doSolve

protected double doSolve()
                  throws TooManyEvaluationsException,
                         NumberIsTooLargeException,
                         NoBracketingException

Method for implementing actual optimization algorithms in derived classes.

Specified by:

doSolve in class BaseAbstractUnivariateSolver<UnivariateFunction>

Returns:

the root.

Throws:

TooManyEvaluationsException - if the maximal number of evaluations is exceeded.

NoBracketingException - if the initial search interval does not bracket a root and the solver requires it.

NumberIsTooLargeException

guessX

private double guessX(double targetY,
                      double[] x,
                      double[] y,
                      int start,
                      int end)

Guess an x value by n^th order inverse polynomial interpolation.

The x value is guessed by evaluating polynomial Q(y) at y = targetY, where Q is built such that for all considered points (x_i, y_i), Q(y_i) = x_i.

Parameters:

targetY - target value for y

x - reference points abscissas for interpolation, note that this array is modified during computation

y - reference points ordinates for interpolation

start - start index of the points to consider (inclusive)

end - end index of the points to consider (exclusive)

Returns:

guessed root (will be a NaN if two points share the same y)

solve

public double solve(int maxEval,
                    UnivariateFunction f,
                    double min,
                    double max,
                    AllowedSolution allowedSolution)
             throws TooManyEvaluationsException,
                    NumberIsTooLargeException,
                    NoBracketingException

Solve for a zero in the given interval. A solver may require that the interval brackets a single zero root. Solvers that do require bracketing should be able to handle the case where one of the endpoints is itself a root.

Specified by:

solve in interface BracketedUnivariateSolver<UnivariateFunction>

Parameters:

maxEval - Maximum number of evaluations.

f - Function to solve.

min - Lower bound for the interval.

max - Upper bound for the interval.

allowedSolution - The kind of solutions that the root-finding algorithm may accept as solutions.

Returns:

A value where the function is zero.

Throws:

TooManyEvaluationsException - if the allowed number of evaluations is exceeded.

NumberIsTooLargeException

NoBracketingException

solve

public double solve(int maxEval,
                    UnivariateFunction f,
                    double min,
                    double max,
                    double startValue,
                    AllowedSolution allowedSolution)
             throws TooManyEvaluationsException,
                    NumberIsTooLargeException,
                    NoBracketingException

Solve for a zero in the given interval, start at startValue. A solver may require that the interval brackets a single zero root. Solvers that do require bracketing should be able to handle the case where one of the endpoints is itself a root.

Specified by:

solve in interface BracketedUnivariateSolver<UnivariateFunction>

Parameters:

maxEval - Maximum number of evaluations.

f - Function to solve.

min - Lower bound for the interval.

max - Upper bound for the interval.

startValue - Start value to use.

allowedSolution - The kind of solutions that the root-finding algorithm may accept as solutions.

Returns:

A value where the function is zero.

Throws:

TooManyEvaluationsException - if the allowed number of evaluations is exceeded.

NumberIsTooLargeException

NoBracketingException