Package 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 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 - 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 CalculusFieldElement<T>> T[] bracket(CalculusFieldUnivariateFunction<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 CalculusFieldElement<T>> T[] bracket(CalculusFieldUnivariateFunction<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 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
      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.