Return-Path: X-Original-To: apmail-commons-commits-archive@minotaur.apache.org Delivered-To: apmail-commons-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 5D0B110908 for ; Mon, 16 Feb 2015 22:40:01 +0000 (UTC) Received: (qmail 54187 invoked by uid 500); 16 Feb 2015 22:39:36 -0000 Delivered-To: apmail-commons-commits-archive@commons.apache.org Received: (qmail 52475 invoked by uid 500); 16 Feb 2015 22:39:35 -0000 Mailing-List: contact commits-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list commits@commons.apache.org Received: (qmail 47225 invoked by uid 99); 16 Feb 2015 22:39:32 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Mon, 16 Feb 2015 22:39:32 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id AFDC8E0D5F; Mon, 16 Feb 2015 22:39:31 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: tn@apache.org To: commits@commons.apache.org Date: Mon, 16 Feb 2015 22:40:10 -0000 Message-Id: In-Reply-To: References: X-Mailer: ASF-Git Admin Mailer Subject: [40/82] [partial] [math] Update for next development iteration: commons-math4 http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialSplineFunction.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialSplineFunction.java b/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialSplineFunction.java deleted file mode 100644 index 7b402e5..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialSplineFunction.java +++ /dev/null @@ -1,246 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.analysis.polynomials; - -import java.util.Arrays; - -import org.apache.commons.math3.util.MathArrays; -import org.apache.commons.math3.analysis.DifferentiableUnivariateFunction; -import org.apache.commons.math3.analysis.UnivariateFunction; -import org.apache.commons.math3.analysis.differentiation.DerivativeStructure; -import org.apache.commons.math3.analysis.differentiation.UnivariateDifferentiableFunction; -import org.apache.commons.math3.exception.NonMonotonicSequenceException; -import org.apache.commons.math3.exception.OutOfRangeException; -import org.apache.commons.math3.exception.NumberIsTooSmallException; -import org.apache.commons.math3.exception.DimensionMismatchException; -import org.apache.commons.math3.exception.NullArgumentException; -import org.apache.commons.math3.exception.util.LocalizedFormats; - -/** - * Represents a polynomial spline function. - *

- * A polynomial spline function consists of a set of - * interpolating polynomials and an ascending array of domain - * knot points, determining the intervals over which the spline function - * is defined by the constituent polynomials. The polynomials are assumed to - * have been computed to match the values of another function at the knot - * points. The value consistency constraints are not currently enforced by - * PolynomialSplineFunction itself, but are assumed to hold among - * the polynomials and knot points passed to the constructor.

- *

- * N.B.: The polynomials in the polynomials property must be - * centered on the knot points to compute the spline function values. - * See below.

- *

- * The domain of the polynomial spline function is - * [smallest knot, largest knot]. Attempts to evaluate the - * function at values outside of this range generate IllegalArgumentExceptions. - *

- *

- * The value of the polynomial spline function for an argument x - * is computed as follows: - *

    - *
  1. The knot array is searched to find the segment to which x - * belongs. If x is less than the smallest knot point or greater - * than the largest one, an IllegalArgumentException - * is thrown.
    2. - *
  2. Let j be the index of the largest knot point that is less - * than or equal to x. The value returned is
    - * polynomials[j](x - knot[j])

- * - */ -public class PolynomialSplineFunction implements UnivariateDifferentiableFunction, DifferentiableUnivariateFunction { - /** - * Spline segment interval delimiters (knots). - * Size is n + 1 for n segments. - */ - private final double knots[]; - /** - * The polynomial functions that make up the spline. The first element - * determines the value of the spline over the first subinterval, the - * second over the second, etc. Spline function values are determined by - * evaluating these functions at {@code (x - knot[i])} where i is the - * knot segment to which x belongs. - */ - private final PolynomialFunction polynomials[]; - /** - * Number of spline segments. It is equal to the number of polynomials and - * to the number of partition points - 1. - */ - private final int n; - - - /** - * Construct a polynomial spline function with the given segment delimiters - * and interpolating polynomials. - * The constructor copies both arrays and assigns the copies to the knots - * and polynomials properties, respectively. - * - * @param knots Spline segment interval delimiters. - * @param polynomials Polynomial functions that make up the spline. - * @throws NullArgumentException if either of the input arrays is {@code null}. - * @throws NumberIsTooSmallException if knots has length less than 2. - * @throws DimensionMismatchException if {@code polynomials.length != knots.length - 1}. - * @throws NonMonotonicSequenceException if the {@code knots} array is not strictly increasing. - * - */ - public PolynomialSplineFunction(double knots[], PolynomialFunction polynomials[]) - throws NullArgumentException, NumberIsTooSmallException, - DimensionMismatchException, NonMonotonicSequenceException{ - if (knots == null || - polynomials == null) { - throw new NullArgumentException(); - } - if (knots.length < 2) { - throw new NumberIsTooSmallException(LocalizedFormats.NOT_ENOUGH_POINTS_IN_SPLINE_PARTITION, - 2, knots.length, false); - } - if (knots.length - 1 != polynomials.length) { - throw new DimensionMismatchException(polynomials.length, knots.length); - } - MathArrays.checkOrder(knots); - - this.n = knots.length -1; - this.knots = new double[n + 1]; - System.arraycopy(knots, 0, this.knots, 0, n + 1); - this.polynomials = new PolynomialFunction[n]; - System.arraycopy(polynomials, 0, this.polynomials, 0, n); - } - - /** - * Compute the value for the function. - * See {@link PolynomialSplineFunction} for details on the algorithm for - * computing the value of the function. - * - * @param v Point for which the function value should be computed. - * @return the value. - * @throws OutOfRangeException if {@code v} is outside of the domain of the - * spline function (smaller than the smallest knot point or larger than the - * largest knot point). - */ - public double value(double v) { - if (v < knots[0] || v > knots[n]) { - throw new OutOfRangeException(v, knots[0], knots[n]); - } - int i = Arrays.binarySearch(knots, v); - if (i < 0) { - i = -i - 2; - } - // This will handle the case where v is the last knot value - // There are only n-1 polynomials, so if v is the last knot - // then we will use the last polynomial to calculate the value. - if ( i >= polynomials.length ) { - i--; - } - return polynomials[i].value(v - knots[i]); - } - - /** - * Get the derivative of the polynomial spline function. - * - * @return the derivative function. - */ - public UnivariateFunction derivative() { - return polynomialSplineDerivative(); - } - - /** - * Get the derivative of the polynomial spline function. - * - * @return the derivative function. - */ - public PolynomialSplineFunction polynomialSplineDerivative() { - PolynomialFunction derivativePolynomials[] = new PolynomialFunction[n]; - for (int i = 0; i < n; i++) { - derivativePolynomials[i] = polynomials[i].polynomialDerivative(); - } - return new PolynomialSplineFunction(knots, derivativePolynomials); - } - - - /** {@inheritDoc} - * @since 3.1 - */ - public DerivativeStructure value(final DerivativeStructure t) { - final double t0 = t.getValue(); - if (t0 < knots[0] || t0 > knots[n]) { - throw new OutOfRangeException(t0, knots[0], knots[n]); - } - int i = Arrays.binarySearch(knots, t0); - if (i < 0) { - i = -i - 2; - } - // This will handle the case where t is the last knot value - // There are only n-1 polynomials, so if t is the last knot - // then we will use the last polynomial to calculate the value. - if ( i >= polynomials.length ) { - i--; - } - return polynomials[i].value(t.subtract(knots[i])); - } - - /** - * Get the number of spline segments. - * It is also the number of polynomials and the number of knot points - 1. - * - * @return the number of spline segments. - */ - public int getN() { - return n; - } - - /** - * Get a copy of the interpolating polynomials array. - * It returns a fresh copy of the array. Changes made to the copy will - * not affect the polynomials property. - * - * @return the interpolating polynomials. - */ - public PolynomialFunction[] getPolynomials() { - PolynomialFunction p[] = new PolynomialFunction[n]; - System.arraycopy(polynomials, 0, p, 0, n); - return p; - } - - /** - * Get an array copy of the knot points. - * It returns a fresh copy of the array. Changes made to the copy - * will not affect the knots property. - * - * @return the knot points. - */ - public double[] getKnots() { - double out[] = new double[n + 1]; - System.arraycopy(knots, 0, out, 0, n + 1); - return out; - } - - /** - * Indicates whether a point is within the interpolation range. - * - * @param x Point. - * @return {@code true} if {@code x} is a valid point. - */ - public boolean isValidPoint(double x) { - if (x < knots[0] || - x > knots[n]) { - return false; - } else { - return true; - } - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java b/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java deleted file mode 100644 index e6eccef..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/polynomials/PolynomialsUtils.java +++ /dev/null @@ -1,446 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.analysis.polynomials; - -import java.util.ArrayList; -import java.util.HashMap; -import java.util.List; -import java.util.Map; - -import org.apache.commons.math3.fraction.BigFraction; -import org.apache.commons.math3.util.CombinatoricsUtils; -import org.apache.commons.math3.util.FastMath; - -/** - * A collection of static methods that operate on or return polynomials. - * - * @since 2.0 - */ -public class PolynomialsUtils { - - /** Coefficients for Chebyshev polynomials. */ - private static final List CHEBYSHEV_COEFFICIENTS; - - /** Coefficients for Hermite polynomials. */ - private static final List HERMITE_COEFFICIENTS; - - /** Coefficients for Laguerre polynomials. */ - private static final List LAGUERRE_COEFFICIENTS; - - /** Coefficients for Legendre polynomials. */ - private static final List LEGENDRE_COEFFICIENTS; - - /** Coefficients for Jacobi polynomials. */ - private static final Map> JACOBI_COEFFICIENTS; - - static { - - // initialize recurrence for Chebyshev polynomials - // T0(X) = 1, T1(X) = 0 + 1 * X - CHEBYSHEV_COEFFICIENTS = new ArrayList(); - CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE); - CHEBYSHEV_COEFFICIENTS.add(BigFraction.ZERO); - CHEBYSHEV_COEFFICIENTS.add(BigFraction.ONE); - - // initialize recurrence for Hermite polynomials - // H0(X) = 1, H1(X) = 0 + 2 * X - HERMITE_COEFFICIENTS = new ArrayList(); - HERMITE_COEFFICIENTS.add(BigFraction.ONE); - HERMITE_COEFFICIENTS.add(BigFraction.ZERO); - HERMITE_COEFFICIENTS.add(BigFraction.TWO); - - // initialize recurrence for Laguerre polynomials - // L0(X) = 1, L1(X) = 1 - 1 * X - LAGUERRE_COEFFICIENTS = new ArrayList(); - LAGUERRE_COEFFICIENTS.add(BigFraction.ONE); - LAGUERRE_COEFFICIENTS.add(BigFraction.ONE); - LAGUERRE_COEFFICIENTS.add(BigFraction.MINUS_ONE); - - // initialize recurrence for Legendre polynomials - // P0(X) = 1, P1(X) = 0 + 1 * X - LEGENDRE_COEFFICIENTS = new ArrayList(); - LEGENDRE_COEFFICIENTS.add(BigFraction.ONE); - LEGENDRE_COEFFICIENTS.add(BigFraction.ZERO); - LEGENDRE_COEFFICIENTS.add(BigFraction.ONE); - - // initialize map for Jacobi polynomials - JACOBI_COEFFICIENTS = new HashMap>(); - - } - - /** - * Private constructor, to prevent instantiation. - */ - private PolynomialsUtils() { - } - - /** - * Create a Chebyshev polynomial of the first kind. - *

Chebyshev - * polynomials of the first kind are orthogonal polynomials. - * They can be defined by the following recurrence relations: - * 

-     *  T0(X)   = 1
-     *  T1(X)   = X
-     *  Tk+1(X) = 2X Tk(X) - Tk-1(X)
-     *

- * @param degree degree of the polynomial - * @return Chebyshev polynomial of specified degree - */ - public static PolynomialFunction createChebyshevPolynomial(final int degree) { - return buildPolynomial(degree, CHEBYSHEV_COEFFICIENTS, - new RecurrenceCoefficientsGenerator() { - private final BigFraction[] coeffs = { BigFraction.ZERO, BigFraction.TWO, BigFraction.ONE }; - /** {@inheritDoc} */ - public BigFraction[] generate(int k) { - return coeffs; - } - }); - } - - /** - * Create a Hermite polynomial. - *

Hermite - * polynomials are orthogonal polynomials. - * They can be defined by the following recurrence relations: - * 

-     *  H0(X)   = 1
-     *  H1(X)   = 2X
-     *  Hk+1(X) = 2X Hk(X) - 2k Hk-1(X)
-     *

- - * @param degree degree of the polynomial - * @return Hermite polynomial of specified degree - */ - public static PolynomialFunction createHermitePolynomial(final int degree) { - return buildPolynomial(degree, HERMITE_COEFFICIENTS, - new RecurrenceCoefficientsGenerator() { - /** {@inheritDoc} */ - public BigFraction[] generate(int k) { - return new BigFraction[] { - BigFraction.ZERO, - BigFraction.TWO, - new BigFraction(2 * k)}; - } - }); - } - - /** - * Create a Laguerre polynomial. - *

Laguerre - * polynomials are orthogonal polynomials. - * They can be defined by the following recurrence relations: - * 

-     *        L0(X)   = 1
-     *        L1(X)   = 1 - X
-     *  (k+1) Lk+1(X) = (2k + 1 - X) Lk(X) - k Lk-1(X)
-     *

- * @param degree degree of the polynomial - * @return Laguerre polynomial of specified degree - */ - public static PolynomialFunction createLaguerrePolynomial(final int degree) { - return buildPolynomial(degree, LAGUERRE_COEFFICIENTS, - new RecurrenceCoefficientsGenerator() { - /** {@inheritDoc} */ - public BigFraction[] generate(int k) { - final int kP1 = k + 1; - return new BigFraction[] { - new BigFraction(2 * k + 1, kP1), - new BigFraction(-1, kP1), - new BigFraction(k, kP1)}; - } - }); - } - - /** - * Create a Legendre polynomial. - *

Legendre - * polynomials are orthogonal polynomials. - * They can be defined by the following recurrence relations: - * 

-     *        P0(X)   = 1
-     *        P1(X)   = X
-     *  (k+1) Pk+1(X) = (2k+1) X Pk(X) - k Pk-1(X)
-     *

- * @param degree degree of the polynomial - * @return Legendre polynomial of specified degree - */ - public static PolynomialFunction createLegendrePolynomial(final int degree) { - return buildPolynomial(degree, LEGENDRE_COEFFICIENTS, - new RecurrenceCoefficientsGenerator() { - /** {@inheritDoc} */ - public BigFraction[] generate(int k) { - final int kP1 = k + 1; - return new BigFraction[] { - BigFraction.ZERO, - new BigFraction(k + kP1, kP1), - new BigFraction(k, kP1)}; - } - }); - } - - /** - * Create a Jacobi polynomial. - *

Jacobi - * polynomials are orthogonal polynomials. - * They can be defined by the following recurrence relations: - * 

-     *        P0vw(X)   = 1
-     *        P-1vw(X)  = 0
-     *  2k(k + v + w)(2k + v + w - 2) Pkvw(X) =
-     *  (2k + v + w - 1)[(2k + v + w)(2k + v + w - 2) X + v2 - w2] Pk-1vw(X)
-     *  - 2(k + v - 1)(k + w - 1)(2k + v + w) Pk-2vw(X)
-     *

- * @param degree degree of the polynomial - * @param v first exponent - * @param w second exponent - * @return Jacobi polynomial of specified degree - */ - public static PolynomialFunction createJacobiPolynomial(final int degree, final int v, final int w) { - - // select the appropriate list - final JacobiKey key = new JacobiKey(v, w); - - if (!JACOBI_COEFFICIENTS.containsKey(key)) { - - // allocate a new list for v, w - final List list = new ArrayList(); - JACOBI_COEFFICIENTS.put(key, list); - - // Pv,w,0(x) = 1; - list.add(BigFraction.ONE); - - // P1(x) = (v - w) / 2 + (2 + v + w) * X / 2 - list.add(new BigFraction(v - w, 2)); - list.add(new BigFraction(2 + v + w, 2)); - - } - - return buildPolynomial(degree, JACOBI_COEFFICIENTS.get(key), - new RecurrenceCoefficientsGenerator() { - /** {@inheritDoc} */ - public BigFraction[] generate(int k) { - k++; - final int kvw = k + v + w; - final int twoKvw = kvw + k; - final int twoKvwM1 = twoKvw - 1; - final int twoKvwM2 = twoKvw - 2; - final int den = 2 * k * kvw * twoKvwM2; - - return new BigFraction[] { - new BigFraction(twoKvwM1 * (v * v - w * w), den), - new BigFraction(twoKvwM1 * twoKvw * twoKvwM2, den), - new BigFraction(2 * (k + v - 1) * (k + w - 1) * twoKvw, den) - }; - } - }); - - } - - /** Inner class for Jacobi polynomials keys. */ - private static class JacobiKey { - - /** First exponent. */ - private final int v; - - /** Second exponent. */ - private final int w; - - /** Simple constructor. - * @param v first exponent - * @param w second exponent - */ - public JacobiKey(final int v, final int w) { - this.v = v; - this.w = w; - } - - /** Get hash code. - * @return hash code - */ - @Override - public int hashCode() { - return (v << 16) ^ w; - } - - /** Check if the instance represent the same key as another instance. - * @param key other key - * @return true if the instance and the other key refer to the same polynomial - */ - @Override - public boolean equals(final Object key) { - - if ((key == null) || !(key instanceof JacobiKey)) { - return false; - } - - final JacobiKey otherK = (JacobiKey) key; - return (v == otherK.v) && (w == otherK.w); - - } - } - - /** - * Compute the coefficients of the polynomial Ps(x) - * whose values at point {@code x} will be the same as the those from the - * original polynomial P(x) when computed at {@code x + shift}. - * Thus, if P(x) = Σi ai xi, - * then - * 
-     *  
-     *   
-     *    
-     *    
-     *   
-     *   
-     *    
-     *    
-     *   
-     *  
Ps(x)= Σi bi xi
= Σi ai (x + shift)i

-     *
- * - * @param coefficients Coefficients of the original polynomial. - * @param shift Shift value. - * @return the coefficients bi of the shifted - * polynomial. - */ - public static double[] shift(final double[] coefficients, - final double shift) { - final int dp1 = coefficients.length; - final double[] newCoefficients = new double[dp1]; - - // Pascal triangle. - final int[][] coeff = new int[dp1][dp1]; - for (int i = 0; i < dp1; i++){ - for(int j = 0; j <= i; j++){ - coeff[i][j] = (int) CombinatoricsUtils.binomialCoefficient(i, j); - } - } - - // First polynomial coefficient. - for (int i = 0; i < dp1; i++){ - newCoefficients[0] += coefficients[i] * FastMath.pow(shift, i); - } - - // Superior order. - final int d = dp1 - 1; - for (int i = 0; i < d; i++) { - for (int j = i; j < d; j++){ - newCoefficients[i + 1] += coeff[j + 1][j - i] * - coefficients[j + 1] * FastMath.pow(shift, j - i); - } - } - - return newCoefficients; - } - - - /** Get the coefficients array for a given degree. - * @param degree degree of the polynomial - * @param coefficients list where the computed coefficients are stored - * @param generator recurrence coefficients generator - * @return coefficients array - */ - private static PolynomialFunction buildPolynomial(final int degree, - final List coefficients, - final RecurrenceCoefficientsGenerator generator) { - - final int maxDegree = (int) FastMath.floor(FastMath.sqrt(2 * coefficients.size())) - 1; - synchronized (PolynomialsUtils.class) { - if (degree > maxDegree) { - computeUpToDegree(degree, maxDegree, generator, coefficients); - } - } - - // coefficient for polynomial 0 is l [0] - // coefficients for polynomial 1 are l [1] ... l [2] (degrees 0 ... 1) - // coefficients for polynomial 2 are l [3] ... l [5] (degrees 0 ... 2) - // coefficients for polynomial 3 are l [6] ... l [9] (degrees 0 ... 3) - // coefficients for polynomial 4 are l[10] ... l[14] (degrees 0 ... 4) - // coefficients for polynomial 5 are l[15] ... l[20] (degrees 0 ... 5) - // coefficients for polynomial 6 are l[21] ... l[27] (degrees 0 ... 6) - // ... - final int start = degree * (degree + 1) / 2; - - final double[] a = new double[degree + 1]; - for (int i = 0; i <= degree; ++i) { - a[i] = coefficients.get(start + i).doubleValue(); - } - - // build the polynomial - return new PolynomialFunction(a); - - } - - /** Compute polynomial coefficients up to a given degree. - * @param degree maximal degree - * @param maxDegree current maximal degree - * @param generator recurrence coefficients generator - * @param coefficients list where the computed coefficients should be appended - */ - private static void computeUpToDegree(final int degree, final int maxDegree, - final RecurrenceCoefficientsGenerator generator, - final List coefficients) { - - int startK = (maxDegree - 1) * maxDegree / 2; - for (int k = maxDegree; k < degree; ++k) { - - // start indices of two previous polynomials Pk(X) and Pk-1(X) - int startKm1 = startK; - startK += k; - - // Pk+1(X) = (a[0] + a[1] X) Pk(X) - a[2] Pk-1(X) - BigFraction[] ai = generator.generate(k); - - BigFraction ck = coefficients.get(startK); - BigFraction ckm1 = coefficients.get(startKm1); - - // degree 0 coefficient - coefficients.add(ck.multiply(ai[0]).subtract(ckm1.multiply(ai[2]))); - - // degree 1 to degree k-1 coefficients - for (int i = 1; i < k; ++i) { - final BigFraction ckPrev = ck; - ck = coefficients.get(startK + i); - ckm1 = coefficients.get(startKm1 + i); - coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1])).subtract(ckm1.multiply(ai[2]))); - } - - // degree k coefficient - final BigFraction ckPrev = ck; - ck = coefficients.get(startK + k); - coefficients.add(ck.multiply(ai[0]).add(ckPrev.multiply(ai[1]))); - - // degree k+1 coefficient - coefficients.add(ck.multiply(ai[1])); - - } - - } - - /** Interface for recurrence coefficients generation. */ - private interface RecurrenceCoefficientsGenerator { - /** - * Generate recurrence coefficients. - * @param k highest degree of the polynomials used in the recurrence - * @return an array of three coefficients such that - * Pk+1(X) = (a[0] + a[1] X) Pk(X) - a[2] Pk-1(X) - */ - BigFraction[] generate(int k); - } - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/polynomials/package-info.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/polynomials/package-info.java b/src/main/java/org/apache/commons/math3/analysis/polynomials/package-info.java deleted file mode 100644 index 85b99f7..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/polynomials/package-info.java +++ /dev/null @@ -1,23 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -/** - * - * Univariate real polynomials implementations, seen as differentiable - * univariate real functions. - * - */ -package org.apache.commons.math3.analysis.polynomials; http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractDifferentiableUnivariateSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractDifferentiableUnivariateSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractDifferentiableUnivariateSolver.java deleted file mode 100644 index d0fda00..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractDifferentiableUnivariateSolver.java +++ /dev/null @@ -1,82 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.analysis.DifferentiableUnivariateFunction; -import org.apache.commons.math3.analysis.UnivariateFunction; -import org.apache.commons.math3.exception.TooManyEvaluationsException; - -/** - * Provide a default implementation for several functions useful to generic - * solvers. - * - * @since 3.0 - * @deprecated as of 3.1, replaced by {@link AbstractUnivariateDifferentiableSolver} - */ -@Deprecated -public abstract class AbstractDifferentiableUnivariateSolver - extends BaseAbstractUnivariateSolver - implements DifferentiableUnivariateSolver { - /** Derivative of the function to solve. */ - private UnivariateFunction functionDerivative; - - /** - * Construct a solver with given absolute accuracy. - * - * @param absoluteAccuracy Maximum absolute error. - */ - protected AbstractDifferentiableUnivariateSolver(final double absoluteAccuracy) { - super(absoluteAccuracy); - } - - /** - * Construct a solver with given accuracies. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - * @param functionValueAccuracy Maximum function value error. - */ - protected AbstractDifferentiableUnivariateSolver(final double relativeAccuracy, - final double absoluteAccuracy, - final double functionValueAccuracy) { - super(relativeAccuracy, absoluteAccuracy, functionValueAccuracy); - } - - /** - * Compute the objective function value. - * - * @param point Point at which the objective function must be evaluated. - * @return the objective function value at specified point. - * @throws TooManyEvaluationsException if the maximal number of evaluations is exceeded. - */ - protected double computeDerivativeObjectiveValue(double point) - throws TooManyEvaluationsException { - incrementEvaluationCount(); - return functionDerivative.value(point); - } - - /** - * {@inheritDoc} - */ - @Override - protected void setup(int maxEval, DifferentiableUnivariateFunction f, - double min, double max, double startValue) { - super.setup(maxEval, f, min, max, startValue); - functionDerivative = f.derivative(); - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractPolynomialSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractPolynomialSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractPolynomialSolver.java deleted file mode 100644 index d641e87..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractPolynomialSolver.java +++ /dev/null @@ -1,80 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.analysis.polynomials.PolynomialFunction; - -/** - * Base class for solvers. - * - * @since 3.0 - */ -public abstract class AbstractPolynomialSolver - extends BaseAbstractUnivariateSolver - implements PolynomialSolver { - /** Function. */ - private PolynomialFunction polynomialFunction; - - /** - * Construct a solver with given absolute accuracy. - * - * @param absoluteAccuracy Maximum absolute error. - */ - protected AbstractPolynomialSolver(final double absoluteAccuracy) { - super(absoluteAccuracy); - } - /** - * Construct a solver with given accuracies. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - */ - protected AbstractPolynomialSolver(final double relativeAccuracy, - final double absoluteAccuracy) { - super(relativeAccuracy, absoluteAccuracy); - } - /** - * Construct a solver with given accuracies. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - * @param functionValueAccuracy Maximum function value error. - */ - protected AbstractPolynomialSolver(final double relativeAccuracy, - final double absoluteAccuracy, - final double functionValueAccuracy) { - super(relativeAccuracy, absoluteAccuracy, functionValueAccuracy); - } - - /** - * {@inheritDoc} - */ - @Override - protected void setup(int maxEval, PolynomialFunction f, - double min, double max, double startValue) { - super.setup(maxEval, f, min, max, startValue); - polynomialFunction = f; - } - - /** - * @return the coefficients of the polynomial function. - */ - protected double[] getCoefficients() { - return polynomialFunction.getCoefficients(); - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractUnivariateDifferentiableSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractUnivariateDifferentiableSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractUnivariateDifferentiableSolver.java deleted file mode 100644 index 9745e9b..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractUnivariateDifferentiableSolver.java +++ /dev/null @@ -1,82 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.analysis.differentiation.DerivativeStructure; -import org.apache.commons.math3.analysis.differentiation.UnivariateDifferentiableFunction; -import org.apache.commons.math3.exception.TooManyEvaluationsException; - -/** - * Provide a default implementation for several functions useful to generic - * solvers. - * - * @since 3.1 - */ -public abstract class AbstractUnivariateDifferentiableSolver - extends BaseAbstractUnivariateSolver - implements UnivariateDifferentiableSolver { - - /** Function to solve. */ - private UnivariateDifferentiableFunction function; - - /** - * Construct a solver with given absolute accuracy. - * - * @param absoluteAccuracy Maximum absolute error. - */ - protected AbstractUnivariateDifferentiableSolver(final double absoluteAccuracy) { - super(absoluteAccuracy); - } - - /** - * Construct a solver with given accuracies. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - * @param functionValueAccuracy Maximum function value error. - */ - protected AbstractUnivariateDifferentiableSolver(final double relativeAccuracy, - final double absoluteAccuracy, - final double functionValueAccuracy) { - super(relativeAccuracy, absoluteAccuracy, functionValueAccuracy); - } - - /** - * Compute the objective function value. - * - * @param point Point at which the objective function must be evaluated. - * @return the objective function value and derivative at specified point. - * @throws TooManyEvaluationsException - * if the maximal number of evaluations is exceeded. - */ - protected DerivativeStructure computeObjectiveValueAndDerivative(double point) - throws TooManyEvaluationsException { - incrementEvaluationCount(); - return function.value(new DerivativeStructure(1, 1, 0, point)); - } - - /** - * {@inheritDoc} - */ - @Override - protected void setup(int maxEval, UnivariateDifferentiableFunction f, - double min, double max, double startValue) { - super.setup(maxEval, f, min, max, startValue); - function = f; - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractUnivariateSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractUnivariateSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractUnivariateSolver.java deleted file mode 100644 index 078c70f..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/AbstractUnivariateSolver.java +++ /dev/null @@ -1,60 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.analysis.UnivariateFunction; - -/** - * Base class for solvers. - * - * @since 3.0 - */ -public abstract class AbstractUnivariateSolver - extends BaseAbstractUnivariateSolver - implements UnivariateSolver { - /** - * Construct a solver with given absolute accuracy. - * - * @param absoluteAccuracy Maximum absolute error. - */ - protected AbstractUnivariateSolver(final double absoluteAccuracy) { - super(absoluteAccuracy); - } - /** - * Construct a solver with given accuracies. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - */ - protected AbstractUnivariateSolver(final double relativeAccuracy, - final double absoluteAccuracy) { - super(relativeAccuracy, absoluteAccuracy); - } - /** - * Construct a solver with given accuracies. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - * @param functionValueAccuracy Maximum function value error. - */ - protected AbstractUnivariateSolver(final double relativeAccuracy, - final double absoluteAccuracy, - final double functionValueAccuracy) { - super(relativeAccuracy, absoluteAccuracy, functionValueAccuracy); - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/AllowedSolution.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/AllowedSolution.java b/src/main/java/org/apache/commons/math3/analysis/solvers/AllowedSolution.java deleted file mode 100644 index a02a29b..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/AllowedSolution.java +++ /dev/null @@ -1,75 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.analysis.solvers; - - -/** The kinds of solutions that a {@link BracketedUnivariateSolver - * (bracketed univariate real) root-finding algorithm} may accept as solutions. - * This basically controls whether or not under-approximations and - * over-approximations are allowed. - * - *

If all solutions are accepted ({@link #ANY_SIDE}), then the solution - * that the root-finding algorithm returns for a given root may be equal to the - * actual root, but it may also be an approximation that is slightly smaller - * or slightly larger than the actual root. Root-finding algorithms generally - * only guarantee that the returned solution is within the requested - * tolerances. In certain cases however, in particular for - * {@link org.apache.commons.math3.ode.events.EventHandler state events} of - * {@link org.apache.commons.math3.ode.ODEIntegrator ODE solvers}, it - * may be necessary to guarantee that a solution is returned that lies on a - * specific side the solution.

- * - * @see BracketedUnivariateSolver - * @since 3.0 - */ -public enum AllowedSolution { - /** There are no additional side restriction on the solutions for - * root-finding. That is, both under-approximations and over-approximations - * are allowed. So, if a function f(x) has a root at x = x0, then the - * root-finding result s may be smaller than x0, equal to x0, or greater - * than x0. - */ - ANY_SIDE, - - /** Only solutions that are less than or equal to the actual root are - * acceptable as solutions for root-finding. In other words, - * over-approximations are not allowed. So, if a function f(x) has a root - * at x = x0, then the root-finding result s must satisfy s <= x0. - */ - LEFT_SIDE, - - /** Only solutions that are greater than or equal to the actual root are - * acceptable as solutions for root-finding. In other words, - * under-approximations are not allowed. So, if a function f(x) has a root - * at x = x0, then the root-finding result s must satisfy s >= x0. - */ - RIGHT_SIDE, - - /** Only solutions for which values are less than or equal to zero are - * acceptable as solutions for root-finding. So, if a function f(x) has - * a root at x = x0, then the root-finding result s must satisfy f(s) <= 0. - */ - BELOW_SIDE, - - /** Only solutions for which values are greater than or equal to zero are - * acceptable as solutions for root-finding. So, if a function f(x) has - * a root at x = x0, then the root-finding result s must satisfy f(s) >= 0. - */ - ABOVE_SIDE; - -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/BaseAbstractUnivariateSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/BaseAbstractUnivariateSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/BaseAbstractUnivariateSolver.java deleted file mode 100644 index 4fb9ecf..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/BaseAbstractUnivariateSolver.java +++ /dev/null @@ -1,318 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.analysis.UnivariateFunction; -import org.apache.commons.math3.exception.MaxCountExceededException; -import org.apache.commons.math3.exception.NoBracketingException; -import org.apache.commons.math3.exception.TooManyEvaluationsException; -import org.apache.commons.math3.exception.NumberIsTooLargeException; -import org.apache.commons.math3.exception.NullArgumentException; -import org.apache.commons.math3.util.Incrementor; -import org.apache.commons.math3.util.MathUtils; - -/** - * Provide a default implementation for several functions useful to generic - * solvers. - * The default values for relative and function tolerances are 1e-14 - * and 1e-15, respectively. It is however highly recommended to not - * rely on the default, but rather carefully consider values that match - * user's expectations, as well as the specifics of each implementation. - * - * @param Type of function to solve. - * - * @since 2.0 - */ -public abstract class BaseAbstractUnivariateSolver - implements BaseUnivariateSolver { - /** Default relative accuracy. */ - private static final double DEFAULT_RELATIVE_ACCURACY = 1e-14; - /** Default function value accuracy. */ - private static final double DEFAULT_FUNCTION_VALUE_ACCURACY = 1e-15; - /** Function value accuracy. */ - private final double functionValueAccuracy; - /** Absolute accuracy. */ - private final double absoluteAccuracy; - /** Relative accuracy. */ - private final double relativeAccuracy; - /** Evaluations counter. */ - private final Incrementor evaluations = new Incrementor(); - /** Lower end of search interval. */ - private double searchMin; - /** Higher end of search interval. */ - private double searchMax; - /** Initial guess. */ - private double searchStart; - /** Function to solve. */ - private FUNC function; - - /** - * Construct a solver with given absolute accuracy. - * - * @param absoluteAccuracy Maximum absolute error. - */ - protected BaseAbstractUnivariateSolver(final double absoluteAccuracy) { - this(DEFAULT_RELATIVE_ACCURACY, - absoluteAccuracy, - DEFAULT_FUNCTION_VALUE_ACCURACY); - } - - /** - * Construct a solver with given accuracies. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - */ - protected BaseAbstractUnivariateSolver(final double relativeAccuracy, - final double absoluteAccuracy) { - this(relativeAccuracy, - absoluteAccuracy, - DEFAULT_FUNCTION_VALUE_ACCURACY); - } - - /** - * Construct a solver with given accuracies. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - * @param functionValueAccuracy Maximum function value error. - */ - protected BaseAbstractUnivariateSolver(final double relativeAccuracy, - final double absoluteAccuracy, - final double functionValueAccuracy) { - this.absoluteAccuracy = absoluteAccuracy; - this.relativeAccuracy = relativeAccuracy; - this.functionValueAccuracy = functionValueAccuracy; - } - - /** {@inheritDoc} */ - public int getMaxEvaluations() { - return evaluations.getMaximalCount(); - } - /** {@inheritDoc} */ - public int getEvaluations() { - return evaluations.getCount(); - } - /** - * @return the lower end of the search interval. - */ - public double getMin() { - return searchMin; - } - /** - * @return the higher end of the search interval. - */ - public double getMax() { - return searchMax; - } - /** - * @return the initial guess. - */ - public double getStartValue() { - return searchStart; - } - /** - * {@inheritDoc} - */ - public double getAbsoluteAccuracy() { - return absoluteAccuracy; - } - /** - * {@inheritDoc} - */ - public double getRelativeAccuracy() { - return relativeAccuracy; - } - /** - * {@inheritDoc} - */ - public double getFunctionValueAccuracy() { - return functionValueAccuracy; - } - - /** - * Compute the objective function value. - * - * @param point Point at which the objective function must be evaluated. - * @return the objective function value at specified point. - * @throws TooManyEvaluationsException if the maximal number of evaluations - * is exceeded. - */ - protected double computeObjectiveValue(double point) - throws TooManyEvaluationsException { - incrementEvaluationCount(); - return function.value(point); - } - - /** - * Prepare for computation. - * Subclasses must call this method if they override any of the - * {@code solve} methods. - * - * @param f Function to solve. - * @param min Lower bound for the interval. - * @param max Upper bound for the interval. - * @param startValue Start value to use. - * @param maxEval Maximum number of evaluations. - * @exception NullArgumentException if f is null - */ - protected void setup(int maxEval, - FUNC f, - double min, double max, - double startValue) - throws NullArgumentException { - // Checks. - MathUtils.checkNotNull(f); - - // Reset. - searchMin = min; - searchMax = max; - searchStart = startValue; - function = f; - evaluations.setMaximalCount(maxEval); - evaluations.resetCount(); - } - - /** {@inheritDoc} */ - public double solve(int maxEval, FUNC f, double min, double max, double startValue) - throws TooManyEvaluationsException, - NoBracketingException { - // Initialization. - setup(maxEval, f, min, max, startValue); - - // Perform computation. - return doSolve(); - } - - /** {@inheritDoc} */ - public double solve(int maxEval, FUNC f, double min, double max) { - return solve(maxEval, f, min, max, min + 0.5 * (max - min)); - } - - /** {@inheritDoc} */ - public double solve(int maxEval, FUNC f, double startValue) - throws TooManyEvaluationsException, - NoBracketingException { - return solve(maxEval, f, Double.NaN, Double.NaN, startValue); - } - - /** - * Method for implementing actual optimization algorithms in derived - * classes. - * - * @return the root. - * @throws TooManyEvaluationsException if the maximal number of evaluations - * is exceeded. - * @throws NoBracketingException if the initial search interval does not bracket - * a root and the solver requires it. - */ - protected abstract double doSolve() - throws TooManyEvaluationsException, NoBracketingException; - - /** - * Check whether the function takes opposite signs at the endpoints. - * - * @param lower Lower endpoint. - * @param upper Upper endpoint. - * @return {@code true} if the function values have opposite signs at the - * given points. - */ - protected boolean isBracketing(final double lower, - final double upper) { - return UnivariateSolverUtils.isBracketing(function, lower, upper); - } - - /** - * Check whether the arguments form a (strictly) increasing sequence. - * - * @param start First number. - * @param mid Second number. - * @param end Third number. - * @return {@code true} if the arguments form an increasing sequence. - */ - protected boolean isSequence(final double start, - final double mid, - final double end) { - return UnivariateSolverUtils.isSequence(start, mid, end); - } - - /** - * Check that the endpoints specify an interval. - * - * @param lower Lower endpoint. - * @param upper Upper endpoint. - * @throws NumberIsTooLargeException if {@code lower >= upper}. - */ - protected void verifyInterval(final double lower, - final double upper) - throws NumberIsTooLargeException { - UnivariateSolverUtils.verifyInterval(lower, upper); - } - - /** - * Check that {@code lower < initial < upper}. - * - * @param lower Lower endpoint. - * @param initial Initial value. - * @param upper Upper endpoint. - * @throws NumberIsTooLargeException if {@code lower >= initial} or - * {@code initial >= upper}. - */ - protected void verifySequence(final double lower, - final double initial, - final double upper) - throws NumberIsTooLargeException { - UnivariateSolverUtils.verifySequence(lower, initial, upper); - } - - /** - * Check that the endpoints specify an interval and the function takes - * opposite signs at the endpoints. - * - * @param lower Lower endpoint. - * @param upper Upper endpoint. - * @throws NullArgumentException if the function has not been set. - * @throws NoBracketingException if the function has the same sign at - * the endpoints. - */ - protected void verifyBracketing(final double lower, - final double upper) - throws NullArgumentException, - NoBracketingException { - UnivariateSolverUtils.verifyBracketing(function, lower, upper); - } - - /** - * Increment the evaluation count by one. - * Method {@link #computeObjectiveValue(double)} calls this method internally. - * It is provided for subclasses that do not exclusively use - * {@code computeObjectiveValue} to solve the function. - * See e.g. {@link AbstractUnivariateDifferentiableSolver}. - * - * @throws TooManyEvaluationsException when the allowed number of function - * evaluations has been exhausted. - */ - protected void incrementEvaluationCount() - throws TooManyEvaluationsException { - try { - evaluations.incrementCount(); - } catch (MaxCountExceededException e) { - throw new TooManyEvaluationsException(e.getMax()); - } - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/BaseSecantSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/BaseSecantSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/BaseSecantSolver.java deleted file mode 100644 index 44a2173..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/BaseSecantSolver.java +++ /dev/null @@ -1,278 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.util.FastMath; -import org.apache.commons.math3.analysis.UnivariateFunction; -import org.apache.commons.math3.exception.ConvergenceException; -import org.apache.commons.math3.exception.MathInternalError; - -/** - * Base class for all bracketing Secant-based methods for root-finding - * (approximating a zero of a univariate real function). - * - *

Implementation of the {@link RegulaFalsiSolver Regula Falsi} and - * {@link IllinoisSolver Illinois} methods is based on the - * following article: M. Dowell and P. Jarratt, - * A modified regula falsi method for computing the root of an - * equation, BIT Numerical Mathematics, volume 11, number 2, - * pages 168-174, Springer, 1971.

- * - *

Implementation of the {@link PegasusSolver Pegasus} method is - * based on the following article: M. Dowell and P. Jarratt, - * The "Pegasus" method for computing the root of an equation, - * BIT Numerical Mathematics, volume 12, number 4, pages 503-508, Springer, - * 1972.

- * - *

The {@link SecantSolver Secant} method is not a - * bracketing method, so it is not implemented here. It has a separate - * implementation.

- * - * @since 3.0 - */ -public abstract class BaseSecantSolver - extends AbstractUnivariateSolver - implements BracketedUnivariateSolver { - - /** Default absolute accuracy. */ - protected static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6; - - /** The kinds of solutions that the algorithm may accept. */ - private AllowedSolution allowed; - - /** The Secant-based root-finding method to use. */ - private final Method method; - - /** - * Construct a solver. - * - * @param absoluteAccuracy Absolute accuracy. - * @param method Secant-based root-finding method to use. - */ - protected BaseSecantSolver(final double absoluteAccuracy, final Method method) { - super(absoluteAccuracy); - this.allowed = AllowedSolution.ANY_SIDE; - this.method = method; - } - - /** - * Construct a solver. - * - * @param relativeAccuracy Relative accuracy. - * @param absoluteAccuracy Absolute accuracy. - * @param method Secant-based root-finding method to use. - */ - protected BaseSecantSolver(final double relativeAccuracy, - final double absoluteAccuracy, - final Method method) { - super(relativeAccuracy, absoluteAccuracy); - this.allowed = AllowedSolution.ANY_SIDE; - this.method = method; - } - - /** - * Construct a solver. - * - * @param relativeAccuracy Maximum relative error. - * @param absoluteAccuracy Maximum absolute error. - * @param functionValueAccuracy Maximum function value error. - * @param method Secant-based root-finding method to use - */ - protected BaseSecantSolver(final double relativeAccuracy, - final double absoluteAccuracy, - final double functionValueAccuracy, - final Method method) { - super(relativeAccuracy, absoluteAccuracy, functionValueAccuracy); - this.allowed = AllowedSolution.ANY_SIDE; - this.method = method; - } - - /** {@inheritDoc} */ - public double solve(final int maxEval, final UnivariateFunction f, - final double min, final double max, - final AllowedSolution allowedSolution) { - return solve(maxEval, f, min, max, min + 0.5 * (max - min), allowedSolution); - } - - /** {@inheritDoc} */ - public double solve(final int maxEval, final UnivariateFunction f, - final double min, final double max, final double startValue, - final AllowedSolution allowedSolution) { - this.allowed = allowedSolution; - return super.solve(maxEval, f, min, max, startValue); - } - - /** {@inheritDoc} */ - @Override - public double solve(final int maxEval, final UnivariateFunction f, - final double min, final double max, final double startValue) { - return solve(maxEval, f, min, max, startValue, AllowedSolution.ANY_SIDE); - } - - /** - * {@inheritDoc} - * - * @throws ConvergenceException if the algorithm failed due to finite - * precision. - */ - @Override - protected final double doSolve() - throws ConvergenceException { - // Get initial solution - double x0 = getMin(); - double x1 = getMax(); - double f0 = computeObjectiveValue(x0); - double f1 = computeObjectiveValue(x1); - - // If one of the bounds is the exact root, return it. Since these are - // not under-approximations or over-approximations, we can return them - // regardless of the allowed solutions. - if (f0 == 0.0) { - return x0; - } - if (f1 == 0.0) { - return x1; - } - - // Verify bracketing of initial solution. - verifyBracketing(x0, x1); - - // Get accuracies. - final double ftol = getFunctionValueAccuracy(); - final double atol = getAbsoluteAccuracy(); - final double rtol = getRelativeAccuracy(); - - // Keep track of inverted intervals, meaning that the left bound is - // larger than the right bound. - boolean inverted = false; - - // Keep finding better approximations. - while (true) { - // Calculate the next approximation. - final double x = x1 - ((f1 * (x1 - x0)) / (f1 - f0)); - final double fx = computeObjectiveValue(x); - - // If the new approximation is the exact root, return it. Since - // this is not an under-approximation or an over-approximation, - // we can return it regardless of the allowed solutions. - if (fx == 0.0) { - return x; - } - - // Update the bounds with the new approximation. - if (f1 * fx < 0) { - // The value of x1 has switched to the other bound, thus inverting - // the interval. - x0 = x1; - f0 = f1; - inverted = !inverted; - } else { - switch (method) { - case ILLINOIS: - f0 *= 0.5; - break; - case PEGASUS: - f0 *= f1 / (f1 + fx); - break; - case REGULA_FALSI: - // Detect early that algorithm is stuck, instead of waiting - // for the maximum number of iterations to be exceeded. - if (x == x1) { - throw new ConvergenceException(); - } - break; - default: - // Should never happen. - throw new MathInternalError(); - } - } - // Update from [x0, x1] to [x0, x]. - x1 = x; - f1 = fx; - - // If the function value of the last approximation is too small, - // given the function value accuracy, then we can't get closer to - // the root than we already are. - if (FastMath.abs(f1) <= ftol) { - switch (allowed) { - case ANY_SIDE: - return x1; - case LEFT_SIDE: - if (inverted) { - return x1; - } - break; - case RIGHT_SIDE: - if (!inverted) { - return x1; - } - break; - case BELOW_SIDE: - if (f1 <= 0) { - return x1; - } - break; - case ABOVE_SIDE: - if (f1 >= 0) { - return x1; - } - break; - default: - throw new MathInternalError(); - } - } - - // If the current interval is within the given accuracies, we - // are satisfied with the current approximation. - if (FastMath.abs(x1 - x0) < FastMath.max(rtol * FastMath.abs(x1), - atol)) { - switch (allowed) { - case ANY_SIDE: - return x1; - case LEFT_SIDE: - return inverted ? x1 : x0; - case RIGHT_SIDE: - return inverted ? x0 : x1; - case BELOW_SIDE: - return (f1 <= 0) ? x1 : x0; - case ABOVE_SIDE: - return (f1 >= 0) ? x1 : x0; - default: - throw new MathInternalError(); - } - } - } - } - - /** Secant-based root-finding methods. */ - protected enum Method { - - /** - * The {@link RegulaFalsiSolver Regula Falsi} or - * False Position method. - */ - REGULA_FALSI, - - /** The {@link IllinoisSolver Illinois} method. */ - ILLINOIS, - - /** The {@link PegasusSolver Pegasus} method. */ - PEGASUS; - - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/BaseUnivariateSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/BaseUnivariateSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/BaseUnivariateSolver.java deleted file mode 100644 index f00590e..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/BaseUnivariateSolver.java +++ /dev/null @@ -1,142 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.analysis.UnivariateFunction; -import org.apache.commons.math3.exception.MathIllegalArgumentException; -import org.apache.commons.math3.exception.TooManyEvaluationsException; - - -/** - * Interface for (univariate real) rootfinding algorithms. - * Implementations will search for only one zero in the given interval. - * - * This class is not intended for use outside of the Apache Commons Math - * library, regular user should rely on more specific interfaces like - * {@link UnivariateSolver}, {@link PolynomialSolver} or {@link - * DifferentiableUnivariateSolver}. - * @param Type of function to solve. - * - * @since 3.0 - * @see UnivariateSolver - * @see PolynomialSolver - * @see DifferentiableUnivariateSolver - */ -public interface BaseUnivariateSolver { - /** - * Get the maximum number of function evaluations. - * - * @return the maximum number of function evaluations. - */ - int getMaxEvaluations(); - - /** - * Get the number of evaluations of the objective function. - * The number of evaluations corresponds to the last call to the - * {@code optimize} method. It is 0 if the method has not been - * called yet. - * - * @return the number of evaluations of the objective function. - */ - int getEvaluations(); - - /** - * Get the absolute accuracy of the solver. Solutions returned by the - * solver should be accurate to this tolerance, i.e., if ε is the - * absolute accuracy of the solver and {@code v} is a value returned by - * one of the {@code solve} methods, then a root of the function should - * exist somewhere in the interval ({@code v} - ε, {@code v} + ε). - * - * @return the absolute accuracy. - */ - double getAbsoluteAccuracy(); - - /** - * Get the relative accuracy of the solver. The contract for relative - * accuracy is the same as {@link #getAbsoluteAccuracy()}, but using - * relative, rather than absolute error. If ρ is the relative accuracy - * configured for a solver and {@code v} is a value returned, then a root - * of the function should exist somewhere in the interval - * ({@code v} - ρ {@code v}, {@code v} + ρ {@code v}). - * - * @return the relative accuracy. - */ - double getRelativeAccuracy(); - - /** - * Get the function value accuracy of the solver. If {@code v} is - * a value returned by the solver for a function {@code f}, - * then by contract, {@code |f(v)|} should be less than or equal to - * the function value accuracy configured for the solver. - * - * @return the function value accuracy. - */ - double getFunctionValueAccuracy(); - - /** - * Solve for a zero root in the given interval. - * A solver may require that the interval brackets a single zero root. - * Solvers that do require bracketing should be able to handle the case - * where one of the endpoints is itself a root. - * - * @param maxEval Maximum number of evaluations. - * @param f Function to solve. - * @param min Lower bound for the interval. - * @param max Upper bound for the interval. - * @return a value where the function is zero. - * @throws MathIllegalArgumentException - * if the arguments do not satisfy the requirements specified by the solver. - * @throws TooManyEvaluationsException if - * the allowed number of evaluations is exceeded. - */ - double solve(int maxEval, FUNC f, double min, double max) - throws MathIllegalArgumentException, TooManyEvaluationsException; - - /** - * Solve for a zero in the given interval, start at {@code startValue}. - * A solver may require that the interval brackets a single zero root. - * Solvers that do require bracketing should be able to handle the case - * where one of the endpoints is itself a root. - * - * @param maxEval Maximum number of evaluations. - * @param f Function to solve. - * @param min Lower bound for the interval. - * @param max Upper bound for the interval. - * @param startValue Start value to use. - * @return a value where the function is zero. - * @throws MathIllegalArgumentException - * if the arguments do not satisfy the requirements specified by the solver. - * @throws TooManyEvaluationsException if - * the allowed number of evaluations is exceeded. - */ - double solve(int maxEval, FUNC f, double min, double max, double startValue) - throws MathIllegalArgumentException, TooManyEvaluationsException; - - /** - * Solve for a zero in the vicinity of {@code startValue}. - * - * @param f Function to solve. - * @param startValue Start value to use. - * @return a value where the function is zero. - * @param maxEval Maximum number of evaluations. - * @throws org.apache.commons.math3.exception.MathIllegalArgumentException - * if the arguments do not satisfy the requirements specified by the solver. - * @throws org.apache.commons.math3.exception.TooManyEvaluationsException if - * the allowed number of evaluations is exceeded. - */ - double solve(int maxEval, FUNC f, double startValue); -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/BisectionSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/BisectionSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/BisectionSolver.java deleted file mode 100644 index 49f4057..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/BisectionSolver.java +++ /dev/null @@ -1,91 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.util.FastMath; -import org.apache.commons.math3.exception.TooManyEvaluationsException; - -/** - * Implements the - * bisection algorithm for finding zeros of univariate real functions. - *

- * The function should be continuous but not necessarily smooth.

- * - */ -public class BisectionSolver extends AbstractUnivariateSolver { - /** Default absolute accuracy. */ - private static final double DEFAULT_ABSOLUTE_ACCURACY = 1e-6; - - /** - * Construct a solver with default accuracy (1e-6). - */ - public BisectionSolver() { - this(DEFAULT_ABSOLUTE_ACCURACY); - } - /** - * Construct a solver. - * - * @param absoluteAccuracy Absolute accuracy. - */ - public BisectionSolver(double absoluteAccuracy) { - super(absoluteAccuracy); - } - /** - * Construct a solver. - * - * @param relativeAccuracy Relative accuracy. - * @param absoluteAccuracy Absolute accuracy. - */ - public BisectionSolver(double relativeAccuracy, - double absoluteAccuracy) { - super(relativeAccuracy, absoluteAccuracy); - } - - /** - * {@inheritDoc} - */ - @Override - protected double doSolve() - throws TooManyEvaluationsException { - double min = getMin(); - double max = getMax(); - verifyInterval(min, max); - final double absoluteAccuracy = getAbsoluteAccuracy(); - double m; - double fm; - double fmin; - - while (true) { - m = UnivariateSolverUtils.midpoint(min, max); - fmin = computeObjectiveValue(min); - fm = computeObjectiveValue(m); - - if (fm * fmin > 0) { - // max and m bracket the root. - min = m; - } else { - // min and m bracket the root. - max = m; - } - - if (FastMath.abs(max - min) <= absoluteAccuracy) { - m = UnivariateSolverUtils.midpoint(min, max); - return m; - } - } - } -} http://git-wip-us.apache.org/repos/asf/commons-math/blob/a7b4803f/src/main/java/org/apache/commons/math3/analysis/solvers/BracketedUnivariateSolver.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/math3/analysis/solvers/BracketedUnivariateSolver.java b/src/main/java/org/apache/commons/math3/analysis/solvers/BracketedUnivariateSolver.java deleted file mode 100644 index 789fc99..0000000 --- a/src/main/java/org/apache/commons/math3/analysis/solvers/BracketedUnivariateSolver.java +++ /dev/null @@ -1,92 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one or more - * contributor license agreements. See the NOTICE file distributed with - * this work for additional information regarding copyright ownership. - * The ASF licenses this file to You under the Apache License, Version 2.0 - * (the "License"); you may not use this file except in compliance with - * the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, software - * distributed under the License is distributed on an "AS IS" BASIS, - * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. - * See the License for the specific language governing permissions and - * limitations under the License. - */ - -package org.apache.commons.math3.analysis.solvers; - -import org.apache.commons.math3.analysis.UnivariateFunction; - -/** Interface for {@link UnivariateSolver (univariate real) root-finding - * algorithms} that maintain a bracketed solution. There are several advantages - * to having such root-finding algorithms: - *
    - *
  • The bracketed solution guarantees that the root is kept within the - * interval. As such, these algorithms generally also guarantee - * convergence.
    • - *
  • The bracketed solution means that we have the opportunity to only - * return roots that are greater than or equal to the actual root, or - * are less than or equal to the actual root. That is, we can control - * whether under-approximations and over-approximations are - * {@link AllowedSolution allowed solutions}. Other root-finding - * algorithms can usually only guarantee that the solution (the root that - * was found) is around the actual root.
    • - *
- * - *

For backwards compatibility, all root-finding algorithms must have - * {@link AllowedSolution#ANY_SIDE ANY_SIDE} as default for the allowed - * solutions.

- * @param Type of function to solve. - * - * @see AllowedSolution - * @since 3.0 - */ -public interface BracketedUnivariateSolver - extends BaseUnivariateSolver { - - /** - * Solve for a zero in the given interval. - * A solver may require that the interval brackets a single zero root. - * Solvers that do require bracketing should be able to handle the case - * where one of the endpoints is itself a root. - * - * @param maxEval Maximum number of evaluations. - * @param f Function to solve. - * @param min Lower bound for the interval. - * @param max Upper bound for the interval. - * @param allowedSolution The kind of solutions that the root-finding algorithm may - * accept as solutions. - * @return A value where the function is zero. - * @throws org.apache.commons.math3.exception.MathIllegalArgumentException - * if the arguments do not satisfy the requirements specified by the solver. - * @throws org.apache.commons.math3.exception.TooManyEvaluationsException if - * the allowed number of evaluations is exceeded. - */ - double solve(int maxEval, FUNC f, double min, double max, - AllowedSolution allowedSolution); - - /** - * Solve for a zero in the given interval, start at {@code startValue}. - * A solver may require that the interval brackets a single zero root. - * Solvers that do require bracketing should be able to handle the case - * where one of the endpoints is itself a root. - * - * @param maxEval Maximum number of evaluations. - * @param f Function to solve. - * @param min Lower bound for the interval. - * @param max Upper bound for the interval. - * @param startValue Start value to use. - * @param allowedSolution The kind of solutions that the root-finding algorithm may - * accept as solutions. - * @return A value where the function is zero. - * @throws org.apache.commons.math3.exception.MathIllegalArgumentException - * if the arguments do not satisfy the requirements specified by the solver. - * @throws org.apache.commons.math3.exception.TooManyEvaluationsException if - * the allowed number of evaluations is exceeded. - */ - double solve(int maxEval, FUNC f, double min, double max, double startValue, - AllowedSolution allowedSolution); - -}