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.

[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.

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

[edit] Data preprocessing

Let the data points be $(x k, y k)$ for $k = 1,..., n$

Compute the slopes of the secant lines between successive points:

$\Delta_k =\frac{y_{k+1}-y_k}{x_{k+1}-x_k}$

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

$m_k = \frac{\Delta_{k-1}+\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}$
For $k=1,\dots,n-1$ , if $Δ k = 0$ (if two successive $y k = y k + 1$ are equal), then set $m k = m k + 1 = 0,$ as the spline connecting these points must be flat to preserve monotonicity. Ignore step 4 and 5 for those $k$ .
Let $α k = m k / Δ k$ and $β k = m k + 1 / Δ k$ .
Now, since to prevent overshoot or undershoot, 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 $m k = τ k α k Δ k$ and $m k + 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 $x k$ , $y k$ , and $m k$ for $k = 1,..., n$ .

To evaluate at $x$ , find the largest $x lower$ and smallest $x upper$ among $x k$ such that $x_\text{lower} \leq x \leq x_\text{upper}$ . Calculate

h = x upper - x lower

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

then the interpolant is

f interpolated (x) = y lower h 00 (t) + h m lower h 10 (t) + y upper h 01 (t) + h m upper h 11 (t)

where $h i i$ 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 (SIAM) 17 (2): 238–246. doi:10.1137/0717021.

Monotone cubic interpolation

From Wikipedia, the free encyclopedia

Contents

[edit] Monotone cubic Hermite interpolation

[edit] Data preprocessing

[edit] Cubic interpolation

[edit] References

Views

Personal tools

Navigation

Search

Interaction

Toolbox