Monotone cubic interpolation


In the mathematical field 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.

Monotone cubic Hermite interpolation

Monotone interpolation can be accomplished using cubic Hermite spline with the tangents modified to ensure the monotonicity of the resulting Hermite spline.
An algorithm is also available for monotone quintic Hermite interpolation.

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. Note that only one pass of the algorithm is required.
Let the data points be indexed in sorted order for.
  1. Compute the slopes of the secant lines between successive points:
    for.

  2. These assignments are provisional, and may be superseded in the remaining steps. Initialize the tangents at every interior data point as the average of the secants,
    for.

    For the endpoints, use one-sided differences:
    .
    If and have opposite signs, set.

  3. For, where ever ,
    set as the spline connecting these points must be flat to preserve monotonicity.
    Ignore steps 4 and 5 for those.

  4. Let
    .
    If either or is negative, then the input data points are not strictly monotone, and is a local extremum. In such cases, piecewise monotone curves can still be generated by choosing if or if, although strict monotonicity is not possible globally.

  5. To prevent overshoot and ensure monotonicity, at least one of the following three conditions must be met:

Cubic interpolation

After the preprocessing above, evaluation of the interpolated spline is equivalent to a cubic Hermite spline, using the data, , and for.
To evaluate at, find the index in the sequence where, lies between, and, that is:. Calculate
then the interpolated value is
where are the basis functions for the cubic Hermite spline.

Example implementation

The following Python implementation takes a data set and produces a monotone cubic spline interpolant function:

"""
Monotone Cubic Spline Interpolation.
"""
def create_interpolant:
n = len
if n != len:
raise ValueError
if n 0:
return lambda x:
if n 1:
value = float
return lambda x:
# Sort xs and ys together
sorted_pairs = sorted
xs =
ys =
# Compute consecutive differences and slopes
dxs = - xs for i in range]
dys = - ys for i in range]
ms =
# Compute first-degree coefficients
c1s = , ms
if m * m_next <= 0:
c1s.append
else:
dx, dx_next = dxs, dxs
common = dx + dx_next
c1s.append / m +
)
c1s.append
# Compute second- and third-degree coefficients
c2s, c3s = ,
for i in range:
c1, m = c1s, ms
inv_dx = 1 / dxs
common = c1 + c1s - 2 * m
c2s.append
c3s.append
def interpolant:
# Clamp x to range
if x <= xs:
i = 0
elif x >= xs:
i = n - 2
else:
# Binary search for interval
low, high = 0, n - 2
while low <= high:
mid = // 2
if xs < x:
low = mid + 1
else:
high = mid - 1
i = max
dx = x - xs
val = ys + dx *
dval = c1s + dx *
return val, dval
return interpolant
  1. Example usage
if __name__ "__main__":
X =
Y =
spline = create_interpolant
print
print
for x, y in zip:
print
print
print\tdP
M = 25
for i in range:
x = X + * i / M
p, dp = spline
print