public class UnivariateSolverUtils extends Object
UnivariateSolver
objects.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 . |
public static double solve(UnivariateFunction function, double x0, double x1) throws NullArgumentException, NoBracketingException
function
- Function.x0
- Lower bound for the interval.x1
- Upper bound for the interval.NoBracketingException
- if the function has the same sign at the
endpoints.NullArgumentException
- if function
is null
.public static double solve(UnivariateFunction function, double x0, double x1, double absoluteAccuracy) throws NullArgumentException, NoBracketingException
function
- Function.x0
- Lower bound for the interval.x1
- Upper bound for the interval.absoluteAccuracy
- Accuracy to be used by the solver.NoBracketingException
- if the function has the same sign at the
endpoints.NullArgumentException
- if function
is null
.public static double forceSide(int maxEval, UnivariateFunction f, BracketedUnivariateSolver<UnivariateFunction> bracketing, double baseRoot, double min, double max, AllowedSolution allowedSolution) throws NoBracketingException
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.NoBracketingException
- if the function has the same sign at the
endpoints.public static double[] bracket(UnivariateFunction function, double initial, double lowerBound, double upperBound) throws NullArgumentException, NotStrictlyPositiveException, NoBracketingException
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.
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).NoBracketingException
- if a root cannot be bracketted.NotStrictlyPositiveException
- if maximumIterations <= 0
.NullArgumentException
- if function
is null
.public static double[] bracket(UnivariateFunction function, double initial, double lowerBound, double upperBound, int maximumIterations) throws NullArgumentException, NotStrictlyPositiveException, NoBracketingException
bracket(function, initial, lowerBound, upperBound, q, r, maximumIterations)
with q
and r
set to 1.0.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 performNoBracketingException
- if the algorithm fails to find a and b
satisfying the desired conditions.NotStrictlyPositiveException
- if maximumIterations <= 0
.NullArgumentException
- if function
is null
.public static double[] bracket(UnivariateFunction function, double initial, double lowerBound, double upperBound, double q, double r, int maximumIterations) throws NoBracketingException
lowerBound <= a < initial < b <= upperBound
f(a) * f(b) <= 0
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:
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.
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 performNoBracketingException
- if function cannot be bracketed in the search intervalpublic static double midpoint(double a, double b)
a
- first value.b
- second value.public static boolean isBracketing(UnivariateFunction function, double lower, double upper) throws NullArgumentException
function
- Function.lower
- Lower endpoint.upper
- Upper endpoint.true
if the function values have opposite signs at the
given points.NullArgumentException
- if function
is null
.public static boolean isSequence(double start, double mid, double end)
start
- First number.mid
- Second number.end
- Third number.true
if the arguments form an increasing sequence.public static void verifyInterval(double lower, double upper) throws NumberIsTooLargeException
lower
- Lower endpoint.upper
- Upper endpoint.NumberIsTooLargeException
- if lower >= upper
.public static void verifySequence(double lower, double initial, double upper) throws NumberIsTooLargeException
lower < initial < upper
.lower
- Lower endpoint.initial
- Initial value.upper
- Upper endpoint.NumberIsTooLargeException
- if lower >= initial
or
initial >= upper
.public static void verifyBracketing(UnivariateFunction function, double lower, double upper) throws NullArgumentException, NoBracketingException
function
- Function.lower
- Lower endpoint.upper
- Upper endpoint.NoBracketingException
- if the function has the same sign at the
endpoints.NullArgumentException
- if function
is null
.Copyright © 2003–2016 The Apache Software Foundation. All rights reserved.