PolynomialFunctionNewtonForm.java
/*
* 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.math4.legacy.analysis.polynomials;
import org.apache.commons.math4.legacy.analysis.differentiation.DerivativeStructure;
import org.apache.commons.math4.legacy.analysis.differentiation.UnivariateDifferentiableFunction;
import org.apache.commons.math4.legacy.exception.DimensionMismatchException;
import org.apache.commons.math4.legacy.exception.NoDataException;
import org.apache.commons.math4.legacy.exception.NullArgumentException;
import org.apache.commons.math4.legacy.exception.util.LocalizedFormats;
/**
* Implements the representation of a real polynomial function in
* Newton Form. For reference, see <b>Elementary Numerical Analysis</b>,
* ISBN 0070124477, chapter 2.
* <p>
* The formula of polynomial in Newton form is
* p(x) = a[0] + a[1](x-c[0]) + a[2](x-c[0])(x-c[1]) + ... +
* a[n](x-c[0])(x-c[1])...(x-c[n-1])
* Note that the length of a[] is one more than the length of c[]</p>
*
* @since 1.2
*/
public class PolynomialFunctionNewtonForm implements UnivariateDifferentiableFunction {
/**
* The coefficients of the polynomial, ordered by degree -- i.e.
* coefficients[0] is the constant term and coefficients[n] is the
* coefficient of x^n where n is the degree of the polynomial.
*/
private double[] coefficients;
/**
* Centers of the Newton polynomial.
*/
private final double[] c;
/**
* When all c[i] = 0, a[] becomes normal polynomial coefficients,
* i.e. a[i] = coefficients[i].
*/
private final double[] a;
/**
* Whether the polynomial coefficients are available.
*/
private boolean coefficientsComputed;
/**
* Construct a Newton polynomial with the given a[] and c[]. The order of
* centers are important in that if c[] shuffle, then values of a[] would
* completely change, not just a permutation of old a[].
* <p>
* The constructor makes copy of the input arrays and assigns them.</p>
*
* @param a Coefficients in Newton form formula.
* @param c Centers.
* @throws NullArgumentException if any argument is {@code null}.
* @throws NoDataException if any array has zero length.
* @throws DimensionMismatchException if the size difference between
* {@code a} and {@code c} is not equal to 1.
*/
public PolynomialFunctionNewtonForm(double[] a, double[] c)
throws NullArgumentException, NoDataException, DimensionMismatchException {
verifyInputArray(a, c);
this.a = new double[a.length];
this.c = new double[c.length];
System.arraycopy(a, 0, this.a, 0, a.length);
System.arraycopy(c, 0, this.c, 0, c.length);
coefficientsComputed = false;
}
/**
* Calculate the function value at the given point.
*
* @param z Point at which the function value is to be computed.
* @return the function value.
*/
@Override
public double value(double z) {
return evaluate(a, c, z);
}
/**
* {@inheritDoc}
* @since 3.1
*/
@Override
public DerivativeStructure value(final DerivativeStructure t) {
verifyInputArray(a, c);
final int n = c.length;
DerivativeStructure value = new DerivativeStructure(t.getFreeParameters(), t.getOrder(), a[n]);
for (int i = n - 1; i >= 0; i--) {
value = t.subtract(c[i]).multiply(value).add(a[i]);
}
return value;
}
/**
* Returns the degree of the polynomial.
*
* @return the degree of the polynomial
*/
public int degree() {
return c.length;
}
/**
* Returns a copy of coefficients in Newton form formula.
* <p>
* Changes made to the returned copy will not affect the polynomial.</p>
*
* @return a fresh copy of coefficients in Newton form formula
*/
public double[] getNewtonCoefficients() {
double[] out = new double[a.length];
System.arraycopy(a, 0, out, 0, a.length);
return out;
}
/**
* Returns a copy of the centers array.
* <p>
* Changes made to the returned copy will not affect the polynomial.</p>
*
* @return a fresh copy of the centers array.
*/
public double[] getCenters() {
double[] out = new double[c.length];
System.arraycopy(c, 0, out, 0, c.length);
return out;
}
/**
* Returns a copy of the coefficients array.
* <p>
* Changes made to the returned copy will not affect the polynomial.</p>
*
* @return a fresh copy of the coefficients array.
*/
public double[] getCoefficients() {
if (!coefficientsComputed) {
computeCoefficients();
}
double[] out = new double[coefficients.length];
System.arraycopy(coefficients, 0, out, 0, coefficients.length);
return out;
}
/**
* Evaluate the Newton polynomial using nested multiplication. It is
* also called <a href="http://mathworld.wolfram.com/HornersRule.html">
* Horner's Rule</a> and takes O(N) time.
*
* @param a Coefficients in Newton form formula.
* @param c Centers.
* @param z Point at which the function value is to be computed.
* @return the function value.
* @throws NullArgumentException if any argument is {@code null}.
* @throws NoDataException if any array has zero length.
* @throws DimensionMismatchException if the size difference between
* {@code a} and {@code c} is not equal to 1.
*/
public static double evaluate(double[] a, double[] c, double z)
throws NullArgumentException, DimensionMismatchException, NoDataException {
verifyInputArray(a, c);
final int n = c.length;
double value = a[n];
for (int i = n - 1; i >= 0; i--) {
value = a[i] + (z - c[i]) * value;
}
return value;
}
/**
* Calculate the normal polynomial coefficients given the Newton form.
* It also uses nested multiplication but takes O(N^2) time.
*/
protected void computeCoefficients() {
final int n = degree();
coefficients = new double[n+1];
for (int i = 0; i <= n; i++) {
coefficients[i] = 0.0;
}
coefficients[0] = a[n];
for (int i = n-1; i >= 0; i--) {
for (int j = n-i; j > 0; j--) {
coefficients[j] = coefficients[j-1] - c[i] * coefficients[j];
}
coefficients[0] = a[i] - c[i] * coefficients[0];
}
coefficientsComputed = true;
}
/**
* Verifies that the input arrays are valid.
* <p>
* The centers must be distinct for interpolation purposes, but not
* for general use. Thus it is not verified here.</p>
*
* @param a the coefficients in Newton form formula
* @param c the centers
* @throws NullArgumentException if any argument is {@code null}.
* @throws NoDataException if any array has zero length.
* @throws DimensionMismatchException if the size difference between
* {@code a} and {@code c} is not equal to 1.
* @see org.apache.commons.math4.legacy.analysis.interpolation.DividedDifferenceInterpolator#computeDividedDifference(double[],
* double[])
*/
protected static void verifyInputArray(double[] a, double[] c)
throws NullArgumentException, NoDataException, DimensionMismatchException {
NullArgumentException.check(a);
NullArgumentException.check(c);
if (a.length == 0 || c.length == 0) {
throw new NoDataException(LocalizedFormats.EMPTY_POLYNOMIALS_COEFFICIENTS_ARRAY);
}
if (a.length != c.length + 1) {
throw new DimensionMismatchException(LocalizedFormats.ARRAY_SIZES_SHOULD_HAVE_DIFFERENCE_1,
a.length, c.length);
}
}
}