org.apache.commons.math3.analysis.solvers

## Class UnivariateSolverUtils

• java.lang.Object
• org.apache.commons.math3.analysis.solvers.UnivariateSolverUtils
• ### Method Summary

Methods
Modifier and Type Method and Description
static double[] bracket(UnivariateFunction function, double initial, double lowerBound, double upperBound)
This method simply calls bracket(function, initial, lowerBound, upperBound, q, r, maximumIterations) with q and r set to 1.0 and maximumIterations set to Integer.MAX_VALUE.
static double[] bracket(UnivariateFunction function, double initial, double lowerBound, double upperBound, double q, double r, int maximumIterations)
This method attempts to find two values a and b satisfying lowerBound <= a < initial < b <= upperBound f(a) * f(b) <= 0 If f is continuous on [a,b], this means that a and b bracket a root of f.
static double[] bracket(UnivariateFunction function, double initial, double lowerBound, double upperBound, int maximumIterations)
This method simply calls bracket(function, initial, lowerBound, upperBound, q, r, maximumIterations) with q and r set to 1.0.
static double forceSide(int maxEval, UnivariateFunction f, BracketedUnivariateSolver<UnivariateFunction> bracketing, double baseRoot, double min, double max, AllowedSolution allowedSolution)
Force a root found by a non-bracketing solver to lie on a specified side, as if the solver were a bracketing one.
static boolean isBracketing(UnivariateFunction function, double lower, double upper)
Check whether the interval bounds bracket a root.
static boolean isSequence(double start, double mid, double end)
Check whether the arguments form a (strictly) increasing sequence.
static double midpoint(double a, double b)
Compute the midpoint of two values.
static double solve(UnivariateFunction function, double x0, double x1)
Convenience method to find a zero of a univariate real function.
static double solve(UnivariateFunction function, double x0, double x1, double absoluteAccuracy)
Convenience method to find a zero of a univariate real function.
static void verifyBracketing(UnivariateFunction function, double lower, double upper)
Check that the endpoints specify an interval and the end points bracket a root.
static void verifyInterval(double lower, double upper)
Check that the endpoints specify an interval.
static void verifySequence(double lower, double initial, double upper)
Check that lower < initial < upper.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Method Detail

• #### solve

public static double solve(UnivariateFunction function,
double x0,
double x1)
throws NullArgumentException,
NoBracketingException
Convenience method to find a zero of a univariate real function. A default solver is used.
Parameters:
function - Function.
x0 - Lower bound for the interval.
x1 - Upper bound for the interval.
Returns:
a value where the function is zero.
Throws:
NoBracketingException - if the function has the same sign at the endpoints.
NullArgumentException - if function is null.
• #### solve

public static double solve(UnivariateFunction function,
double x0,
double x1,
double absoluteAccuracy)
throws NullArgumentException,
NoBracketingException
Convenience method to find a zero of a univariate real function. A default solver is used.
Parameters:
function - Function.
x0 - Lower bound for the interval.
x1 - Upper bound for the interval.
absoluteAccuracy - Accuracy to be used by the solver.
Returns:
a value where the function is zero.
Throws:
NoBracketingException - if the function has the same sign at the endpoints.
NullArgumentException - if function is null.
• #### forceSide

public static double forceSide(int maxEval,
UnivariateFunction f,
BracketedUnivariateSolver<UnivariateFunction> bracketing,
double baseRoot,
double min,
double max,
AllowedSolution allowedSolution)
throws NoBracketingException
Force a root found by a non-bracketing solver to lie on a specified side, as if the solver were a bracketing one.
Parameters:
maxEval - maximal number of new evaluations of the function (evaluations already done for finding the root should have already been subtracted from this number)
f - function to solve
bracketing - bracketing solver to use for shifting the root
baseRoot - original root found by a previous non-bracketing solver
min - minimal bound of the search interval
max - maximal bound of the search interval
allowedSolution - the kind of solutions that the root-finding algorithm may accept as solutions.
Returns:
a root approximation, on the specified side of the exact root
Throws:
NoBracketingException - if the function has the same sign at the endpoints.
• #### bracket

public static double[] bracket(UnivariateFunction function,
double initial,
double lowerBound,
double upperBound)
throws NullArgumentException,
NotStrictlyPositiveException,
NoBracketingException
This method simply calls bracket(function, initial, lowerBound, upperBound, q, r, maximumIterations) with q and r set to 1.0 and maximumIterations set to Integer.MAX_VALUE.

Note: this method can take Integer.MAX_VALUE iterations to throw a ConvergenceException. Unless you are confident that there is a root between lowerBound and upperBound near initial, it is better to use bracket(function, initial, lowerBound, upperBound, q, r, maximumIterations), explicitly specifying the maximum number of iterations.

Parameters:
function - Function.
initial - Initial midpoint of interval being expanded to bracket a root.
lowerBound - Lower bound (a is never lower than this value)
upperBound - Upper bound (b never is greater than this value).
Returns:
a two-element array holding a and b.
Throws:
NoBracketingException - if a root cannot be bracketted.
NotStrictlyPositiveException - if maximumIterations <= 0.
NullArgumentException - if function is null.
• #### bracket

public static double[] bracket(UnivariateFunction function,
double initial,
double lowerBound,
double upperBound,
int maximumIterations)
throws NullArgumentException,
NotStrictlyPositiveException,
NoBracketingException
This method simply calls bracket(function, initial, lowerBound, upperBound, q, r, maximumIterations) with q and r set to 1.0.
Parameters:
function - Function.
initial - Initial midpoint of interval being expanded to bracket a root.
lowerBound - Lower bound (a is never lower than this value).
upperBound - Upper bound (b never is greater than this value).
maximumIterations - Maximum number of iterations to perform
Returns:
a two element array holding a and b.
Throws:
NoBracketingException - if the algorithm fails to find a and b satisfying the desired conditions.
NotStrictlyPositiveException - if maximumIterations <= 0.
NullArgumentException - if function is null.
• #### bracket

public static double[] bracket(UnivariateFunction function,
double initial,
double lowerBound,
double upperBound,
double q,
double r,
int maximumIterations)
throws NoBracketingException
This method attempts to find two values a and b satisfying
• lowerBound <= a < initial < b <= upperBound
• f(a) * f(b) <= 0
If f is continuous on [a,b], this means that a and b bracket a root of f.

The algorithm checks the sign of $$f(l_k)$$ and $$f(u_k)$$ for increasing values of k, where $$l_k = max(lower, initial - \delta_k)$$, $$u_k = min(upper, initial + \delta_k)$$, using recurrence $$\delta_{k+1} = r \delta_k + q, \delta_0 = 0$$ and starting search with $$k=1$$. The algorithm stops when one of the following happens:

• at least one positive and one negative value have been found -- success!
• both endpoints have reached their respective limits -- NoBracketingException
• maximumIterations iterations elapse -- NoBracketingException

If different signs are found at first iteration (k=1), then the returned interval will be $$[a, b] = [l_1, u_1]$$. If different signs are found at a later iteration k>1, then the returned interval will be either $$[a, b] = [l_{k+1}, l_{k}]$$ or $$[a, b] = [u_{k}, u_{k+1}]$$. A root solver called with these parameters will therefore start with the smallest bracketing interval known at this step.

Interval expansion rate is tuned by changing the recurrence parameters r and q. When the multiplicative factor r is set to 1, the sequence is a simple arithmetic sequence with linear increase. When the multiplicative factor r is larger than 1, the sequence has an asymptotically exponential rate. Note than the additive parameter q should never be set to zero, otherwise the interval would degenerate to the single initial point for all values of k.

As a rule of thumb, when the location of the root is expected to be approximately known within some error margin, r should be set to 1 and q should be set to the order of magnitude of the error margin. When the location of the root is really a wild guess, then r should be set to a value larger than 1 (typically 2 to double the interval length at each iteration) and q should be set according to half the initial search interval length.

As an example, if we consider the trivial function f(x) = 1 - x and use initial = 4, r = 1, q = 2, the algorithm will compute f(4-2) = f(2) = -1 and f(4+2) = f(6) = -5 for k = 1, then f(4-4) = f(0) = +1 and f(4+4) = f(8) = -7 for k = 2. Then it will return the interval [0, 2] as the smallest one known to be bracketing the root. As shown by this example, the initial value (here 4) may lie outside of the returned bracketing interval.

Parameters:
function - function to check
initial - Initial midpoint of interval being expanded to bracket a root.
lowerBound - Lower bound (a is never lower than this value).
upperBound - Upper bound (b never is greater than this value).
q - additive offset used to compute bounds sequence (must be strictly positive)
r - multiplicative factor used to compute bounds sequence
maximumIterations - Maximum number of iterations to perform
Returns:
a two element array holding the bracketing values.
Throws:
NoBracketingException - if function cannot be bracketed in the search interval
• #### midpoint

public static double midpoint(double a,
double b)
Compute the midpoint of two values.
Parameters:
a - first value.
b - second value.
Returns:
the midpoint.
• #### isBracketing

public static boolean isBracketing(UnivariateFunction function,
double lower,
double upper)
throws NullArgumentException
Check whether the interval bounds bracket a root. That is, if the values at the endpoints are not equal to zero, then the function takes opposite signs at the endpoints.
Parameters:
function - Function.
lower - Lower endpoint.
upper - Upper endpoint.
Returns:
true if the function values have opposite signs at the given points.
Throws:
NullArgumentException - if function is null.
• #### isSequence

public static boolean isSequence(double start,
double mid,
double end)
Check whether the arguments form a (strictly) increasing sequence.
Parameters:
start - First number.
mid - Second number.
end - Third number.
Returns:
true if the arguments form an increasing sequence.
• #### verifyInterval

public static void verifyInterval(double lower,
double upper)
throws NumberIsTooLargeException
Check that the endpoints specify an interval.
Parameters:
lower - Lower endpoint.
upper - Upper endpoint.
Throws:
NumberIsTooLargeException - if lower >= upper.
• #### verifySequence

public static void verifySequence(double lower,
double initial,
double upper)
throws NumberIsTooLargeException
Check that lower < initial < upper.
Parameters:
lower - Lower endpoint.
initial - Initial value.
upper - Upper endpoint.
Throws:
NumberIsTooLargeException - if lower >= initial or initial >= upper.
• #### verifyBracketing

public static void verifyBracketing(UnivariateFunction function,
double lower,
double upper)
throws NullArgumentException,
NoBracketingException
Check that the endpoints specify an interval and the end points bracket a root.
Parameters:
function - Function.
lower - Lower endpoint.
upper - Upper endpoint.
Throws:
NoBracketingException - if the function has the same sign at the endpoints.
NullArgumentException - if function is null.