org.hipparchus.analysis.solvers

Class UnivariateSolverUtils

java.lang.Object

org.hipparchus.analysis.solvers.UnivariateSolverUtils

public class UnivariateSolverUtils
extends Object

Utility routines for UnivariateSolver objects.

Method Summary

Modifier and Type	Method and Description
static <T extends RealFieldElement<T>> T[]	bracket(RealFieldUnivariateFunction<T> function, T initial, T lowerBound, T 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 <T extends RealFieldElement<T>> T[]	bracket(RealFieldUnivariateFunction<T> function, T initial, T lowerBound, T upperBound, int maximumIterations) This method simply calls bracket(function, initial, lowerBound, upperBound, q, r, maximumIterations) with q and r set to 1.0.
static <T extends RealFieldElement<T>> T[]	bracket(RealFieldUnivariateFunction<T> function, T initial, T lowerBound, T upperBound, T q, T 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) 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 MathIllegalArgumentException,
                           NullArgumentException

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:

MathIllegalArgumentException - 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 MathIllegalArgumentException,
                           NullArgumentException

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:

MathIllegalArgumentException - 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 MathIllegalArgumentException

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:

MathIllegalArgumentException - if the function has the same sign at the endpoints.

bracket

public static double[] bracket(UnivariateFunction function,
                               double initial,
                               double lowerBound,
                               double upperBound)
                        throws MathIllegalArgumentException,
                               NullArgumentException

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 MathIllegalStateException. 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:

MathIllegalArgumentException - if a root cannot be bracketed.

MathIllegalArgumentException - if maximumIterations <= 0.

NullArgumentException - if function is null.

bracket

public static double[] bracket(UnivariateFunction function,
                               double initial,
                               double lowerBound,
                               double upperBound,
                               int maximumIterations)
                        throws MathIllegalArgumentException,
                               NullArgumentException

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:

MathIllegalArgumentException - if the algorithm fails to find a and b satisfying the desired conditions.

MathIllegalArgumentException - 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 MathIllegalArgumentException

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 -- MathIllegalArgumentException
• maximumIterations iterations elapse -- MathIllegalArgumentException

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:

MathIllegalArgumentException - if function cannot be bracketed in the search interval

bracket

public static <T extends RealFieldElement<T>> T[] bracket(RealFieldUnivariateFunction<T> function,
                                                          T initial,
                                                          T lowerBound,
                                                          T upperBound)
                                                   throws MathIllegalArgumentException,
                                                          NullArgumentException

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

Type Parameters:

T - type of the field elements

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:

MathIllegalArgumentException - if a root cannot be bracketed.

MathIllegalArgumentException - if maximumIterations <= 0.

NullArgumentException - if function is null.

Since:

1.2

bracket

public static <T extends RealFieldElement<T>> T[] bracket(RealFieldUnivariateFunction<T> function,
                                                          T initial,
                                                          T lowerBound,
                                                          T upperBound,
                                                          int maximumIterations)
                                                   throws MathIllegalArgumentException,
                                                          NullArgumentException

This method simply calls bracket(function, initial, lowerBound, upperBound, q, r, maximumIterations) with q and r set to 1.0.

Type Parameters:

T - type of the field elements

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:

MathIllegalArgumentException - if the algorithm fails to find a and b satisfying the desired conditions.

MathIllegalArgumentException - if maximumIterations <= 0.

NullArgumentException - if function is null.

Since:

1.2

bracket

public static <T extends RealFieldElement<T>> T[] bracket(RealFieldUnivariateFunction<T> function,
                                                          T initial,
                                                          T lowerBound,
                                                          T upperBound,
                                                          T q,
                                                          T r,
                                                          int maximumIterations)
                                                   throws MathIllegalArgumentException

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 -- MathIllegalArgumentException
• maximumIterations iterations elapse -- MathIllegalArgumentException

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.

Type Parameters:

T - type of the field elements

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:

MathIllegalArgumentException - if function cannot be bracketed in the search interval

Since:

1.2

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 MathIllegalArgumentException

Check that the endpoints specify an interval.

Parameters:

lower - Lower endpoint.

upper - Upper endpoint.

Throws:

MathIllegalArgumentException - if lower >= upper.

verifySequence

public static void verifySequence(double lower,
                                  double initial,
                                  double upper)
                           throws MathIllegalArgumentException

Check that lower < initial < upper.

Parameters:

lower - Lower endpoint.

initial - Initial value.

upper - Upper endpoint.

Throws:

MathIllegalArgumentException - if lower >= initial or initial >= upper.

verifyBracketing

public static void verifyBracketing(UnivariateFunction function,
                                    double lower,
                                    double upper)
                             throws MathIllegalArgumentException,
                                    NullArgumentException

Check that the endpoints specify an interval and the end points bracket a root.

Parameters:

function - Function.

lower - Lower endpoint.

upper - Upper endpoint.

Throws:

MathIllegalArgumentException - if the function has the same sign at the endpoints.

NullArgumentException - if function is null.