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

Example showing non-monotone cubic interpolation (in red) and monotone cubic interpolation (in blue) of a monotone data set.

Monotone interpolation can be accomplished using cubic Hermite spline with the tangents ${\displaystyle m_{i}}$ 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 ${\displaystyle (x_{k},y_{k})}$ indexed in sorted order for ${\displaystyle k=1,\,\dots \,n}$.

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

   ${\displaystyle \delta _{k}={\frac {y_{k+1}-y_{k}}{x_{k+1}-x_{k}}}}$

   for ${\displaystyle k=1,\,\dots \,n-1}$.
   
   
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,

   ${\displaystyle m_{k}={\frac {\delta _{k-1}+\delta _{k}}{2}}}$

   for ${\displaystyle k=2,\,\dots \,n-1}$.
   
   For the endpoints, use one-sided differences:

   ${\displaystyle m_{1}=\delta _{1}\quad {\text{ and }}\quad m_{n}=\delta _{n-1}\,}$.

   If ${\displaystyle \delta _{k-1}}$ and ${\displaystyle \delta _{k}}$ have opposite signs, set ${\displaystyle m_{k}=0}$.
   
   
3. For ${\displaystyle k=1,\,\dots \,n-1}$, where ever ${\displaystyle \delta _{k}=0}$ (where ever two successive ${\displaystyle y_{k}=y_{k+1}}$ are equal),
   set ${\displaystyle m_{k}=m_{k+1}=0,}$ as the spline connecting these points must be flat to preserve monotonicity.
   Ignore steps 4 and 5 for those ${\displaystyle k\,}$.
   
   
4. Let

   ${\displaystyle \alpha _{k}=m_{k}/\delta _{k}\quad {\text{ and }}\quad \beta _{k}=m_{k+1}/\delta _{k}}$.

   If either ${\displaystyle \alpha _{k}}$ or ${\displaystyle \beta _{k}}$ is negative, then the input data points are not strictly monotone, and ${\displaystyle (x_{k},\,y_{k})}$ is a local extremum. In such cases, piecewise monotone curves can still be generated by choosing ${\displaystyle m_{k}=0\,}$ if ${\displaystyle \alpha _{k}<0}$ or ${\displaystyle m_{k+1}=0\,}$ if ${\displaystyle \beta _{k}<0}$, 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:

(a) the function

${\displaystyle \phi _{k}=\alpha _{k}-{\frac {(2\alpha _{k}+\beta _{k}-3)^{2}}{3(\alpha _{k}+\beta _{k}-2)}}>0\,}$, or

(b) ${\displaystyle \alpha _{k}+2\beta _{k}-3\leq 0\,}$, or

(c) ${\displaystyle 2\alpha _{k}+\beta _{k}-3\leq 0\,}$.

Only condition (a) is sufficient to ensure strict monotonicity: ${\displaystyle \phi _{k}}$ must be positive.

One simple way to satisfy this constraint is to restrict the vector ${\displaystyle (\alpha _{k},\,\beta _{k})}$ to a circle of radius 3. That is, if ${\displaystyle \alpha _{k}^{2}+\beta _{k}^{2}>9\,}$, then set

${\displaystyle \tau _{k}={\frac {3}{\sqrt {\alpha _{k}^{2}+\beta _{k}^{2}}}}\,}$,

and rescale the tangents via

${\displaystyle m_{k}=\tau _{k}\,\alpha _{k}\,\delta _{k}\quad {\text{ and }}\quad m_{k+1}=\tau _{k}\,\beta _{k}\,\delta _{k}\,}$.

Alternatively it is sufficient to restrict ${\displaystyle \alpha _{k}\leq 3}$ and ${\displaystyle \beta _{k}\leq 3\,}$. To accomplish this, if ${\displaystyle \alpha _{k}>3\,}$, then set ${\displaystyle m_{k}=3\,\delta _{k}\,}$, and if ${\displaystyle \beta _{k}>3\,}$, then set ${\displaystyle m_{k+1}=3\,\delta _{k}\,}$.

Cubic interpolation

After the preprocessing above, evaluation of the interpolated spline is equivalent to a cubic Hermite spline, using the data ${\displaystyle x_{k}}$, ${\displaystyle y_{k}}$, and ${\displaystyle m_{k}}$ for ${\displaystyle k=1,\,\dots \,n}$.

To evaluate at ${\displaystyle x}$, find the index ${\displaystyle k}$ in the sequence where ${\displaystyle x}$, lies between ${\displaystyle x_{k}}$, and ${\displaystyle x_{k+1}}$, that is: ${\displaystyle x_{k}\leq x\leq x_{k+1}}$. Calculate

${\displaystyle \Delta =x_{k+1}-x_{k}\quad {\text{ and }}\quad t={\frac {x-x_{k}}{\Delta }}}$

then the interpolated value is

${\displaystyle f_{\text{interpolated}}(x)=y_{k}\cdot h_{00}(t)+\Delta \cdot m_{k}\cdot h_{10}(t)+y_{k+1}\cdot h_{01}(t)+\Delta \cdot m_{k+1}\cdot h_{11}(t)}$

where ${\displaystyle h_{ii}}$ 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."""defcreate_interpolant(xs,ys):n=len(xs)ifn!=len(ys):raiseValueError("xs and ys must have the same length.")ifn==0:returnlambdax:(0.0,0.0)ifn==1:value=float(ys[0])returnlambdax:(value,0.0)# Sort xs and ys togethersorted_pairs=sorted(zip(xs,ys),key=lambdap:p[0])xs=[float(x)forx,_insorted_pairs]ys=[float(y)for_,yinsorted_pairs]# Compute consecutive differences and slopesdxs=[xs[i+1]-xs[i]foriinrange(n-1)]dys=[ys[i+1]-ys[i]foriinrange(n-1)]ms=[dy/dxfordx,dyinzip(dxs,dys)]# Compute first-degree coefficients (c1s)c1s=[ms[0]]foriinrange(len(ms)-1):m,m_next=ms[i],ms[i+1]ifm*m_next<=0:c1s.append(0.0)else:dx,dx_next=dxs[i],dxs[i+1]common=dx+dx_nextc1s.append(3*common/((common+dx_next)/m+(common+dx)/m_next))c1s.append(ms[-1])# Compute second- and third-degree coefficients (c2s, c3s)c2s,c3s=[],[]foriinrange(len(c1s)-1):c1,m=c1s[i],ms[i]inv_dx=1/dxs[i]common=c1+c1s[i+1]-2*mc2s.append((m-c1-common)*inv_dx)c3s.append(common*inv_dx*inv_dx)definterpolant(x):# Clamp x to rangeifx<=xs[0]:i=0elifx>=xs[-1]:i=n-2else:# Binary search for intervallow,high=0,n-2whilelow<=high:mid=(low+high)//2ifxs[mid]<x:low=mid+1else:high=mid-1i=max(0,high)dx=x-xs[i]val=ys[i]+dx*(c1s[i]+dx*(c2s[i]+dx*c3s[i]))dval=c1s[i]+dx*(2*c2s[i]+dx*3*c3s[i])returnval,dvalreturninterpolant# Example usageif__name__=="__main__":X=[0,1,2,3,4]Y=[0,1,4,9,16]spline=create_interpolant(X,Y)print("# Data")print("x\tf(x)")forx,yinzip(X,Y):print(f"{x:.6f}\t{y:.6f}")print("\n# Interpolated values")print("x\tP(x)\tdP(x)/dx")M=25foriinrange(M+1):x=X[0]+(X[-1]-X[0])*i/Mp,dp=spline(x)print(f"{x:.6f}\t{p:.6f}\t{dp:.6f}")

References

• Fritsch, F. N.; Carlson, R. E. (1980). "Monotone Piecewise Cubic Interpolation". SIAM Journal on Numerical Analysis . 17 (2). SIAM: 238–246. Bibcode:1980SJNA...17..238F. doi:10.1137/0717021.
• Dougherty, R.L.; Edelman, A.; Hyman, J.M. (April 1989). "Positivity-, monotonicity-, or convexity-preserving cubic and quintic Hermite interpolation". Mathematics of Computation . 52 (186): 471–494. doi: 10.2307/2008477 . JSTOR   2008477.

External links

• GPLv2 licensed C++ implementation: MonotCubicInterpolator.cpp MonotCubicInterpolator.hpp