001: /*
002: * Copyright 2003-2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.math.analysis;
017:
018: /**
019: * Computes a natural (also known as "free", "unclamped") cubic spline interpolation for the data set.
020: * <p>
021: * The {@link #interpolate(double[], double[])} method returns a {@link PolynomialSplineFunction}
022: * consisting of n cubic polynomials, defined over the subintervals determined by the x values,
023: * x[0] < x[i] ... < x[n]. The x values are referred to as "knot points."
024: * <p>
025: * The value of the PolynomialSplineFunction at a point x that is greater than or equal to the smallest
026: * knot point and strictly less than the largest knot point is computed by finding the subinterval to which
027: * x belongs and computing the value of the corresponding polynomial at <code>x - x[i] </code> where
028: * <code>i</code> is the index of the subinterval. See {@link PolynomialSplineFunction} for more details.
029: * <p>
030: * The interpolating polynomials satisfy: <ol>
031: * <li>The value of the PolynomialSplineFunction at each of the input x values equals the
032: * corresponding y value.</li>
033: * <li>Adjacent polynomials are equal through two derivatives at the knot points (i.e., adjacent polynomials
034: * "match up" at the knot points, as do their first and second derivatives).</li>
035: * </ol>
036: * <p>
037: * The cubic spline interpolation algorithm implemented is as described in R.L. Burden, J.D. Faires,
038: * <u>Numerical Analysis</u>, 4th Ed., 1989, PWS-Kent, ISBN 0-53491-585-X, pp 126-131.
039: *
040: * @version $Revision: 355770 $ $Date: 2005-12-10 12:48:57 -0700 (Sat, 10 Dec 2005) $
041: *
042: */
043: public class SplineInterpolator implements UnivariateRealInterpolator {
044:
045: /**
046: * Computes an interpolating function for the data set.
047: * @param x the arguments for the interpolation points
048: * @param y the values for the interpolation points
049: * @return a function which interpolates the data set
050: */
051: public UnivariateRealFunction interpolate(double x[], double y[]) {
052: if (x.length != y.length) {
053: throw new IllegalArgumentException(
054: "Dataset arrays must have same length.");
055: }
056:
057: if (x.length < 3) {
058: throw new IllegalArgumentException(
059: "At least 3 datapoints are required to compute a spline interpolant");
060: }
061:
062: // Number of intervals. The number of data points is n + 1.
063: int n = x.length - 1;
064:
065: for (int i = 0; i < n; i++) {
066: if (x[i] >= x[i + 1]) {
067: throw new IllegalArgumentException(
068: "Dataset x values must be strictly increasing.");
069: }
070: }
071:
072: // Differences between knot points
073: double h[] = new double[n];
074: for (int i = 0; i < n; i++) {
075: h[i] = x[i + 1] - x[i];
076: }
077:
078: double mu[] = new double[n];
079: double z[] = new double[n + 1];
080: mu[0] = 0d;
081: z[0] = 0d;
082: double g = 0;
083: for (int i = 1; i < n; i++) {
084: g = 2d * (x[i + 1] - x[i - 1]) - h[i - 1] * mu[i - 1];
085: mu[i] = h[i] / g;
086: z[i] = (3d
087: * (y[i + 1] * h[i - 1] - y[i]
088: * (x[i + 1] - x[i - 1]) + y[i - 1] * h[i])
089: / (h[i - 1] * h[i]) - h[i - 1] * z[i - 1])
090: / g;
091: }
092:
093: // cubic spline coefficients -- b is linear, c quadratic, d is cubic (original y's are constants)
094: double b[] = new double[n];
095: double c[] = new double[n + 1];
096: double d[] = new double[n];
097:
098: z[n] = 0d;
099: c[n] = 0d;
100:
101: for (int j = n - 1; j >= 0; j--) {
102: c[j] = z[j] - mu[j] * c[j + 1];
103: b[j] = (y[j + 1] - y[j]) / h[j] - h[j]
104: * (c[j + 1] + 2d * c[j]) / 3d;
105: d[j] = (c[j + 1] - c[j]) / (3d * h[j]);
106: }
107:
108: PolynomialFunction polynomials[] = new PolynomialFunction[n];
109: double coefficients[] = new double[4];
110: for (int i = 0; i < n; i++) {
111: coefficients[0] = y[i];
112: coefficients[1] = b[i];
113: coefficients[2] = c[i];
114: coefficients[3] = d[i];
115: polynomials[i] = new PolynomialFunction(coefficients);
116: }
117:
118: return new PolynomialSplineFunction(x, polynomials);
119: }
120:
121: }
|