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.
1 Spline types
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.
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.
Catmull-Rom spline is a Hermite spline whose derivatives are chosen to be
Catmull-Rom spline is continuous up to the first derivative; second derivative is discontinuous. It is local: spline values depend only on four function values (two on the left of x, two on the right). It supports two kinds of boundary conditions:
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).
At last, we can combine different types of boundary conditions for different boundaries. It does make sense if we have only partial 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).
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 [xi , xi+1 ] depends on fi-2 , fi-1 , fi , fi+1 , fi+2 , fi+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 x2 and xN-3 when the index goes from 0 to N-1) the interpolation error has order O(h 2).
Operations with spline models are performed in two stages: :
Following functions can be used to build spline:
After spline is built and you havestructure, you can use following functions:
Conversion from one grid to another is one of the frequently encountered problems involving cubic splines. We have old grid x and function values y (on x) and new grid x2 . We want to calculate function values on a new grid x2 using cubic splines. Additionally, we may need first or second derivatives.
We can solve this problem by building cubic spline with 2 ·log(n1 )) complexity.function and calling for each of the new nodes (see below). Such code has O(n
... initialization of x, y, x2 ... alglib::spline1dbuildcubic(x, y, spline); for(i=0; i<n2; i++) y2[i] = alglib::spline1dcalc(spline, x2[i]); ... now y2 contains new values ...
However, there is an easier and faster solution - to use special functions for grid operations:
These functions return results exactly equivalent to the values calculated by the code above. However, they use another algorithm which creates specialized representation of a cubic spline. This representation is optimized for only one kind of operations: conversion/differentiation. It allows to increase performance on presorted grids to O(max(n2 ,n1 )).
If grids are not presorted, complexity increases to O(n2 ·log(n2 )+n1 ·log(n1 )) because of time needed to sort grids. However, it is still beneficial to use specialized functions.
With these functions we can write more compact and efficient code:
... initialization of x, y, x2 ... alglib::spline1dconvcubic(x, y, x2, y2); ... now y2 contains new values ...
ALGLIB Reference Manual includes following examples on cubic spline interpolation:
ALGLIB package supports curve fitting using penalized regression splines. Fitting by penalized regression splines can be used to solve noisy fitting problems, underdetermined problems, and problems which need adaptive control over smoothing. It is one of the best one dimensional fitting algorithms. If you need stable and easy to tune fitting algo, we recommend you to choose penalized splines.
This functionality is described in more details in the corresponding chapter of ALGLIB User Guide.
In this section we will show numerical results obtained from solution of different problems. We will investigate following "typical" problems:
Consider the following problem: interpolation of f(x)=sin(x) on [-π/2,+π/2]. We use equidistant grid with N nodes and four different types of cubic splines:
Having investigating dependency of interpolation error on number of nodes, we can get following chart:
We can see that in this case the best choise is to use cubic spline with exact boundary conditions. If we don't know derivative value at boundary points, we can use cubic spline with exact boundary conditions and get slightly worse results. Other choices - Catmull-Rom spline and cubic spline with natural boundary conditions - give us significantly larger interpolation error.
This conclusion holds true in most cases. If you know derivative at the boundary, use it. If you don't - use parabolically terminated spline.
We didn't show results for Hermite spline on the chart above. Usually it gives results similar to spline with exact boundary conditions, but requires more information.
This article is intended for personal use only.
C++ source. MPFR/GMP is used.
GMP source is available from gmplib.org. MPFR source is available from www.mpfr.org.
Python version (CPython and IronPython are supported).