Spline interpolation

Cubic spline interpolation is a fast, efficient 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 interpolation - in O(log(N)) time.

Contents     Spline types: linear spline     Spline types: Hermite spline     Spline types: cubic spline     Spline types: Akima spline     Splines in ALGLIB     Splines in ALGLIB: interpolation splines     Splines in ALGLIB: regression splines (spline fitting)     Splines in ALGLIB: interpolation, differentiation, other operations     Manual entries     Links

Spline types: linear spline

The linear spline is just a piecewise linear function. The linear splines have 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.

Spline types: 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. The interpolation accuracy is much better than in the piecewise linear case.

Spline types: cubic spline

All splines considered on this page are cubic splines - 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).

Spline types: 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 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 ²).

Splines in ALGLIB

Operations with spline models are performed in two stages: :

• Spline construction using one of the subroutines (subroutine choice will depend on the problem to be solved). Result is a Spline1DInterpolant structure containing the model built.
• Operations with the model (interpolation, model copying/serialization, etc.).

Splines in ALGLIB: interpolation splines

Interpolation spline, i.e. spline which passes through all points of data set, can be built with several subroutines:

• Spline1DBuildLinear - builds linear spline
• Spline1DBuildCubic - builds cubic spline
• Spline1DBuildHermite - builds Hermite spline
• Spline1DBuildAkima - builds Akima spline

Splines in ALGLIB: regression splines (spline fitting)

Regression spline is a spline which is built using reduced set of knots (M knots) and is fitted to the data set consisting of N points (N may be significantly larger than M). ALGLIB uses simple but efficient knot selection strategy: it divides interval containing data into M-1 subinterval and builds basis splines using this grid. Regression splines allows to solve both unconstrained and constrained problems (with constraints on function value or first derivative).

Note #1
Excessive constraints may be inconsistent, especially when you work with simple models. See Reference manual, Spline1DFitCubicWC and Spline1DFitHermiteWC comments, for more information on this subject.

Regression spline can be built with following subroutines

• Spline1DFitCubicWC - builds cubic regression spline, with constraints and individual weights.
• Spline1DFitHermiteWC - builds Hermite regression spline, with constraints and individual weights. Hermite spline is much more flexible than cubic spline, but less smooth (continuous only up to the first derivative).
• Spline1DFitCubic and Spline1DFitHermite - "lightweight" variants of their "Weighted-Constrained" counterparts, may be used to solve problems without weights/constraints.

Splines in ALGLIB: interpolation, differentiation, other operations

Interpolation is done with Spline1DCalc (spline value calculation) or Spline1DDiff (spline itself, first and second derivatives) subroutines. Spline integration is done with Spline1DIntegrate subroutine. Spline1DLinTransX and Spline1DLinTransY allows to make change of spline argument or to scale spline as whole.

Other operations include copying (Spline1DCopy subroutine), serialization/unserialization (Spline1DSerialize/Spline1DUnserialize subroutines), access to coefficients table (Spline1DUnpack subroutine).

Links

1. 'Spline_interpolation', Wikipedia

Manual entries

C++		spline1d.h
C#		spline1d.cs
MPFR		spline1d.h
Delphi		spline1d.pas
FreePascal		spline1d.pas
VBA		spline1d.bas

This article is intended for personal use only.

Download ALGLIB