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 m_i 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 (x_k,y_k) for k=1,...,n

  1. Compute the slopes of the secant lines between successive points:

    \Delta_k =\frac{y_{k%2B1}-y_k}{x_{k%2B1}-x_k}

    for k=1,\dots,n-1.
  2. Initialize the tangents at every data point as the average of the secants,

    m_k = \frac{\Delta_{k-1}%2B\Delta_k}{2}

    for k=2,\dots,n-1; these may be updated in further steps. For the endpoints, use one-sided differences:

    m_1 = \Delta_1 \quad \text{and} \quad m_n = \Delta_{n-1}

  3. For k=1,\dots,n-1, if \Delta_k = 0 (if two successive y_k=y_{k%2B1} are equal), then set m_k = m_{k%2B1} = 0, as the spline connecting these points must be flat to preserve monotonicity. Ignore step 4 and 5 for those k.
  4. Let \alpha_k = m_k/\Delta_k and \beta_k = m_{k%2B1}/\Delta_k. If \alpha or \beta are computed to be less than zero, then the input data points are not strictly monotone. In such cases, piecewise monotone curves can still be generated by choosing m_{k}=m_{k%2B1}=0, although global strict monotonicity is not possible.
  5. To prevent overshoot and ensure monotonicity, the function

    \phi(\alpha, \beta) = \alpha - \frac{(2 \alpha %2B \beta - 3)^2}{3(\alpha %2B \beta - 2)}

    must have a value greater than (or equal to, if monotonicity need not be strict) zero. One simple way to satisfy this constraint is to restrict the magnitude of vector (\alpha_k, \beta_k) to a circle of radius 3. That is, if \alpha_k^2 %2B \beta_k^2 > 9, then set m_k = \tau_k \alpha_k \Delta_k and m_{k%2B1} = \tau_k \beta_k \Delta_k where \tau_k = \frac{3}{\sqrt{\alpha_k^2 %2B \beta_k^2}}.

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 x_k, y_k, and m_k for k=1,...,n.

To evaluate at x, find the smallest value larger than x, x_\text{upper}, and the largest value smaller than x, x_\text{lower}, among x_k such that x_\text{lower} \leq x \leq x_\text{upper}. Calculate

h = x_\text{upper}-x_\text{lower} and t = \frac{x - x_\text{lower}}{h}

then the interpolant is

f_\text{interpolated}(x) = y_\text{lower} h_{00}(t) %2B h m_\text{lower} h_{10}(t) %2B y_\text{upper} h_{01}(t) %2B h m_\text{upper}h_{11}(t)

where h_{ii} are the basis functions for the cubic Hermite spline.

External links

References