- Monotone cubic interpolation
-
In the mathematical subfield of numerical analysis, monotone cubic interpolation is a variant of cubic interpolation that preserves monotonicity of the data set being interpolated.
Monotonicity is preserved by linear interpolation but not guaranteed by cubic interpolation.
Contents
Monotone cubic Hermite interpolation
Monotone interpolation can be accomplished using cubic Hermite spline with the tangents mi modified to ensure the monotonicity of the resulting Hermite spline.
Interpolant selection
There are several ways of selecting interpolating tangents for each data point. This section will outline the use of the Fritsch–Carlson method.
Let the data points be (xk,yk) for k = 1,...,n
- Compute the slopes of the secant lines between successive points:
- Initialize the tangents at every data point as the average of the secants,
- For , if Δk = 0 (if two successive yk = yk + 1 are equal), then set mk = mk + 1 = 0, as the spline connecting these points must be flat to preserve monotonicity. Ignore step 4 and 5 for those k.
- Let αk = mk / Δk and βk = mk + 1 / Δk. If α or β are computed to be zero, then the input data points are not strictly monotone. In such cases, piecewise monotone curves can still be generated by choosing mk = mk + 1 = 0, although global strict monotonicity is not possible.
- To prevent overshoot and ensure monotonicity, the function
Note that only one pass of the algorithm is required.
Cubic interpolation
After the preprocessing, evaluation of the interpolated spline is equivalent to cubic Hermite spline, using the data xk, yk, and mk for k = 1,...,n.
To evaluate at x, find the smallest value larger than x, xupper, and the largest value smaller than x, xlower, among xk such that . Calculate
- h = xupper − xlower and
then the interpolant is
- finterpolated(x) = ylowerh00(t) + hmlowerh10(t) + yupperh01(t) + hmupperh11(t)
where hii are the basis functions for the cubic Hermite spline.
External links
- GPLv3 licensed C++ implementation: MonotCubicInterpolator.cpp MonotCubicInterpolator.hpp
References
- Fritsch, F. N.; Carlson, R. E. (1980). "Monotone Piecewise Cubic Interpolation". SIAM Journal on Numerical Analysis (SIAM) 17 (2): 238–246. doi:10.1137/0717021.
Categories:- Interpolation
- Splines
- Compute the slopes of the secant lines between successive points:
Wikimedia Foundation. 2010.