Class UnivariateSolverUtils

    • Method Detail

      • 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,
                                       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,
                                                                  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.