Monotone cubic interpolation

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.

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.

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

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

   Δ k = y k + 1 − y k x k + 1 − x k

   for k = 1 , … , n − 1 .
2. Initialize the tangents at every data point as the average of the secants,

   m k = Δ k − 1 + Δ k 2

   for k = 2 , … , n − 1 ; if Δ k − 1 and Δ k have different sign, set m k = 0 . These may be updated in further steps. For the endpoints, use one-sided differences:

   m 1 = Δ 1 and m n = Δ n − 1

3. For k = 1 , … , 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 .
4. Let α k = m k / Δ k and β k = m k + 1 / Δ k . If α k or β k − 1 are computed to be less than zero, then the input data points are not strictly monotone, and ( x k , y k ) is a local extremum. In such cases, piecewise monotone curves can still be generated by choosing m k = 0 , although global strict monotonicity is not possible.
5. To prevent overshoot and ensure monotonicity, at least one of the following conditions must be met:
   1. the function

      ϕ ( α , β ) = α − ( 2 α + β − 3 ) 2 3 ( α + β − 2 )

      must have a value greater than or equal to zero;
   2. α + 2 β − 3 ≤ 0 ; or
   3. 2 α + β − 3 ≤ 0 .

If monotonicity must be strict then ϕ ( α , β ) must have a value strictly greater than zero.

One simple way to satisfy this constraint is to restrict the vector ( α k , β k ) to a circle of radius 3. That is, if α k 2 + β k 2 > 9 , then set m k = τ k α k Δ k and m k + 1 = τ k β k Δ k where τ k = 3 α k 2 + β k 2 .

Alternatively it is sufficient to restrict α k ≤ 3 and β k ≤ 3 . To accomplish this if α k > 3 , then set m k = 3 × Δ k . Similarly for β .

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 upper , and the largest value smaller than x , x lower , among x k such that x lower ≤ x ≤ x upper . Calculate

then the interpolant is

where h i i are the basis functions for the cubic Hermite spline.

Example implementation

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