Class UnivariateSolverUtils
UnivariateSolver
objects.-
Method Summary
Modifier and TypeMethodDescriptionstatic <T extends CalculusFieldElement<T>>
T[]bracket
(CalculusFieldUnivariateFunction<T> function, T initial, T lowerBound, T upperBound) This method simply callsbracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
withq
andr
set to 1.0 andmaximumIterations
set toInteger.MAX_VALUE
.static <T extends CalculusFieldElement<T>>
T[]bracket
(CalculusFieldUnivariateFunction<T> function, T initial, T lowerBound, T upperBound, int maximumIterations) This method simply callsbracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
withq
andr
set to 1.0.static <T extends CalculusFieldElement<T>>
T[]bracket
(CalculusFieldUnivariateFunction<T> function, T initial, T lowerBound, T upperBound, T q, T r, int maximumIterations) This method attempts to find two values a and b satisfyinglowerBound <= a < initial < b <= upperBound
f(a) * f(b) <= 0
Iff
is continuous on[a,b]
, this means thata
andb
bracket a root off
.static double[]
bracket
(UnivariateFunction function, double initial, double lowerBound, double upperBound) This method simply callsbracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
withq
andr
set to 1.0 andmaximumIterations
set toInteger.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 satisfyinglowerBound <= a < initial < b <= upperBound
f(a) * f(b) <= 0
Iff
is continuous on[a,b]
, this means thata
andb
bracket a root off
.static double[]
bracket
(UnivariateFunction function, double initial, double lowerBound, double upperBound, int maximumIterations) This method simply callsbracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
withq
andr
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 thatlower < initial < upper
.
-
Method Details
-
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
- iffunction
isnull
.
-
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
- iffunction
isnull
.
-
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 solvebracketing
- bracketing solver to use for shifting the rootbaseRoot
- original root found by a previous non-bracketing solvermin
- minimal bound of the search intervalmax
- maximal bound of the search intervalallowedSolution
- 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 callsbracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
withq
andr
set to 1.0 andmaximumIterations
set toInteger.MAX_VALUE
.Note: this method can take
Integer.MAX_VALUE
iterations to throw aMathIllegalStateException.
Unless you are confident that there is a root betweenlowerBound
andupperBound
nearinitial
, it is better to usebracket(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
- ifmaximumIterations <= 0
.NullArgumentException
- iffunction
isnull
.
-
bracket
public static double[] bracket(UnivariateFunction function, double initial, double lowerBound, double upperBound, int maximumIterations) throws MathIllegalArgumentException, NullArgumentException This method simply callsbracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
withq
andr
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
- ifmaximumIterations <= 0
.NullArgumentException
- iffunction
isnull
.
-
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
f
is continuous on[a,b]
, this means thata
andb
bracket a root off
.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 iterationk>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
andq
. When the multiplicative factorr
is set to 1, the sequence is a simple arithmetic sequence with linear increase. When the multiplicative factorr
is larger than 1, the sequence has an asymptotically exponential rate. Note than the additive parameterq
should never be set to zero, otherwise the interval would degenerate to the single initial point for all values ofk
.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 andq
should be set to the order of magnitude of the error margin. When the location of the root is really a wild guess, thenr
should be set to a value larger than 1 (typically 2 to double the interval length at each iteration) andq
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 useinitial = 4
,r = 1
,q = 2
, the algorithm will computef(4-2) = f(2) = -1
andf(4+2) = f(6) = -5
fork = 1
, thenf(4-4) = f(0) = +1
andf(4+4) = f(8) = -7
fork = 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 (here4
) may lie outside of the returned bracketing interval.- Parameters:
function
- function to checkinitial
- 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 sequencemaximumIterations
- 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 CalculusFieldElement<T>> T[] bracket(CalculusFieldUnivariateFunction<T> function, T initial, T lowerBound, T upperBound) throws MathIllegalArgumentException, NullArgumentException This method simply callsbracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
withq
andr
set to 1.0 andmaximumIterations
set toInteger.MAX_VALUE
.Note: this method can take
Integer.MAX_VALUE
iterations to throw aMathIllegalStateException.
Unless you are confident that there is a root betweenlowerBound
andupperBound
nearinitial
, it is better to usebracket(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
- ifmaximumIterations <= 0
.NullArgumentException
- iffunction
isnull
.- Since:
- 1.2
-
bracket
public static <T extends CalculusFieldElement<T>> T[] bracket(CalculusFieldUnivariateFunction<T> function, T initial, T lowerBound, T upperBound, int maximumIterations) throws MathIllegalArgumentException, NullArgumentException This method simply callsbracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
withq
andr
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
- ifmaximumIterations <= 0
.NullArgumentException
- iffunction
isnull
.- Since:
- 1.2
-
bracket
public static <T extends CalculusFieldElement<T>> T[] bracket(CalculusFieldUnivariateFunction<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
f
is continuous on[a,b]
, this means thata
andb
bracket a root off
.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 iterationk>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
andq
. When the multiplicative factorr
is set to 1, the sequence is a simple arithmetic sequence with linear increase. When the multiplicative factorr
is larger than 1, the sequence has an asymptotically exponential rate. Note than the additive parameterq
should never be set to zero, otherwise the interval would degenerate to the single initial point for all values ofk
.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 andq
should be set to the order of magnitude of the error margin. When the location of the root is really a wild guess, thenr
should be set to a value larger than 1 (typically 2 to double the interval length at each iteration) andq
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 useinitial = 4
,r = 1
,q = 2
, the algorithm will computef(4-2) = f(2) = -1
andf(4+2) = f(6) = -5
fork = 1
, thenf(4-4) = f(0) = +1
andf(4+4) = f(8) = -7
fork = 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 (here4
) may lie outside of the returned bracketing interval.- Type Parameters:
T
- type of the field elements- Parameters:
function
- function to checkinitial
- 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 sequencemaximumIterations
- 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
- iffunction
isnull
.
-
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
Check that the endpoints specify an interval.- Parameters:
lower
- Lower endpoint.upper
- Upper endpoint.- Throws:
MathIllegalArgumentException
- iflower >= upper
.
-
verifySequence
public static void verifySequence(double lower, double initial, double upper) throws MathIllegalArgumentException Check thatlower < initial < upper
.- Parameters:
lower
- Lower endpoint.initial
- Initial value.upper
- Upper endpoint.- Throws:
MathIllegalArgumentException
- iflower >= initial
orinitial >= 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
- iffunction
isnull
.
-