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

Fields
`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

Constructors
Constructor and Description
`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

Methods
`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 nth 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 (xi, yi), Q(yi) = xi.

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`