Spline interpolation

Third-degree spline interpolation is a fast, effective and stable method of function interpolation. Parallel with the rational interpolation, the spline interpolation is an alternative for the polynomial interpolation.

The spline interpolation is based on the following principle. The interpolation interval is divided into small subintervals. Each of these subintervals is interpolated by using the third-degree polynomial. The polynomial coefficients are chosen to satisfy certain conditions (these conditions depend on the interpolation method). General requirements are function continuity and, of course, passing through all given points. There could also be additional requirements: function linearity between nodes, continuity of higher derivatives and so on.

The main advantages of spline interpolation are its stability and calculation simplicity. Sets of linear equations which should be solved to construct splines are very well-conditioned, therefore, the polynomial coefficients are calculated precisely. As a result, the calculation scheme stays stable even for big N. The construction of spline coefficients table is performed in O(N) time, and calculating the spline value in given point - in O(log(N)) time.

Spline operations

This module can work with several types of interpolating splines which are considered below. Each type of spline has its own subroutine to construct a coefficient table. After constructing, this table is passed into the SplineInterpolation subroutine. All spline types in this module are third-degree splines, so the spline values are calculated by the same subroutine. The SplineUnpack subroutine can transform the spline coefficient table into a readable form. You could also create a copy of the spline. To do this, use the SplineCopy subroutine.

In addition to the spline value calculation, you can also calculate the spline derivatives and integrals. The first and second spline derivatives could be calculated by using the SplineDifferentiation subroutine. The definite integral on interval [a, t] (where a is the left boundary of the interpolation interval) can be calculated by using the SplineIntegration subroutine.

To perform linear transformations, use the SplineLinTransX and SplineLinTransY subroutines. The first one transforms argument x = a·t+b, the second transforms the spline: S₂ (x) = a·S(x)+b.

Linear spline

The linear spline is a spline which consists of first-degree polynomials, i.e. from line sections. The linear splines provide low precision, it should also be noted that they do not even provide first derivative continuity. However, in some cases, piecewise linear approximation could be better than higher degree approximation. For example, the linear spline keeps the monotony of a set of points.

On the graph you can see the linear spline interpolating function f = cos(0.5·π·x) on [-1;1].

The linear spline coefficient table is constructed by using the BuildLinearSpline subroutine. Technically, the linear spline is implemented as a third-degree spline having two leading coefficients equal 0. That's why all algorithms from this module are applicable to this spline. For example, the subroutine for spline differentiating can calculate the first and second derivative (although the second derivative will always be equal 0).

Cubic Hermite spline

The cubic Hermite spline is a third-degree spline, whose derivative has given values in nodes. For each node not only the function value is given, but its first derivative value too. Hermite's cubic spline has a continuous first derivative, but its second derivative is discontinuous.

On the graph you can see the cubic Hermite spline interpolating function f = cos(0.5·π·x) on [-1;1]. As you can see, the interpolation accuracy is much better than the linear spline accuracy.

The Hermite spline coefficient table is constructed by BuildHermiteSpline subroutine.

Cubic spline

All splines considered on this page are cubic splines. This means that they are all piecewise cubic functions. However, if someone says "cubic spline", they usually mean a special cubic spline with continuous first and second derivatives. The cubic spline is given by the function values in the nodes and derivative values on the edges of the interpolation interval (either of the first or second derivatives).

If the exact values of the first derivative in both boundaries are known, such spline is called fundamental. This spline has interpolation error O(h ⁴).

If the value of the first (or second) derivative is unknown, we can set the so-called natural boundary conditions S''(A) = 0, S''(B) = 0. Thus, we get a natural spline. The natural spline has interpolation error O(h ²). The closer to the boundary nodes the more the error becomes. In the inner nodes the interpolation accuracy is much better.

One more boundary condition which we can use when boundary derivatives are unknown is the "parabolically terminated spline". In this case, the boundary interval is represented as the second (instead of the third) degree polynomial (for inner intervals, third-degree polynomials are still used). In a number of cases this provides better accuracy than natural boundary conditions.

At last, we can combine different types of boundary conditions for different boundaries. It does make sense if we haven't full information about the function behavior at the boundaries (e.g., we know the left boundary derivative, and have no information about the right boundary derivative).

On the graph you can see the cubic spline interpolating function f = cos(0.5·π·x) on [-1;1]. The interpolation accuracy is close to the cubic Hermite spline accuracy.

The cubic spline coefficient table is constructed by using the BuildCubicSpline subroutine.

Akima spline

The Akima spline is a special spline which is stable to the outliers. The disadvantage of cubic splines is that they could oscillate in the neighborhood of an outlier. On the graph on the right you can see a set of points having one outlier. The cubic spline with boundary conditions is green-colored. On the intervals which are next to the outlier, the spline noticeably deviates from the given function - because of the outlier. Akima spline is red-colored. We can see that in contrast to the cubic spline, the Akima spline is less affected by the outliers.

An important property of the Akima spline is its locality - function values in [x_i , x_i+1 ] depends on f_i-2 , f_i-1  , f_i  , f_i+1 , f_i+2 , f_i+3  only. The second property which should be taken into account is the non-linearity of the Akima spline interpolation - the result of interpolation of the sum of two functions doesn't equal the sum of the interpolations schemes constructed on the basis of the given functions. No less than 5 points are required to construct the Akima spline. In the inner area (i.e. between x₂  and x_N-3  when the index goes from 0 to N-1) the interpolation error has order O(h ²).

The Akima spline coefficient table is constructed by using the BuildAkimaSpline subroutine.

Links

1. 'Spline_interpolation', Wikipedia

Source codes