Monotone cubic interpolation

From Wikipedia, the free encyclopedia

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

[edit] Monotone cubic Hermite interpolation

Example showing cubic and monotone cubic interpolation of a monotone data set. Note that the red line is not monotone.
Example showing cubic and monotone cubic interpolation of a monotone data set. Note that the red line is not monotone.

Monotone interpolation can be accomplished using cubic Hermite spline with the tangents mi modified to ensure the monotonicity of the resulting Hermite spline.

[edit] Data preprocessing

Let the data points be (xk,yk) for k = 1,...,n

  1. Initialize tangents at every data point,

    m_k = \frac{y_{k}-y_{k-1}}{2(x_{k}-x_{k-1})} + \frac{y_{k+1}-y_k}{2(x_{k+1}-x_k)}

    for k = 2,...,n − 1. For the endpoints, use one-sided differences:

    m_1 = \frac{y_2-y_1}{x_2 - x_1} \quad \text{and} \quad m_n = \frac{y_n - y_{n-1}}{x_n - x_{n-1}}

  2. Initialize Δk = (yk + 1 − yk) / (xk + 1 − xk) for k = 1,...,n − 1.
  3. For k = 1,...,n − 1, if Δk = 0, then set mk = mk + 1 = 0. Ignore step 4 and 5 for those k.
  4. Let αk = mk / Δk and βk = mk + 1 / Δk.
  5. Now, since we are trying to restrict the position vector (αk,βk) to a circle of radius 3, if \alpha_k^2 + \beta_k^2 > 9, then set mk = τkαkΔk and mk + 1 = τkβkΔk where \tau_k = \frac{3}{\sqrt{\alpha_k^2 + \beta_k^2}}.

Note that only one pass of the algorithm is required.

[edit] 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 largest xlower and smallest xupper among xk such that x_\text{lower} \leq x \leq x_\text{upper}. Calculate

h = xupper − xlower and t = \frac{x - x_\text{lower}}{h}

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.

[edit] References

  • Fritsch, F. N.; Carlson, R. E. (1980). "Monotone Piecewise Cubic Interpolation". SIAM Journal on Numerical Analysis 17 (2): 238–246. SIAM. doi:10.1137/0717021.