Cubic spline interpolation/fitting is a fast, efficient and stable method of function interpolation/approximation. ALGLIB package provides you with dual licensed (open source and commercial) implementation of spline-related functionality in several programming languages, including our flagship products:
Our implementation of cubic splines is well tested and has following distinctive features (see below for more complete discussion):
1 Spline types
Linear spline
Hermite spline
Catmull-Rom spline
Cubic spline
Akima spline
Monotone spline
2 Spline interpolation in ALGLIB
Spline construction
Interpolation, differentiation, integration, transformation
Fast batch interpolation on a grid
Cubic spline fitting
Examples
3 Numerical results
Interpolation by different spline types
4 Downloads section
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 [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_{2 } and x_{N-3 } when the index goes from 0 to N-1) the interpolation error has order O(h^{ 2}).
Monotone cubic interpolation is a variant of cubic spline that preserves monotonicity of the data being interpolated.
Spline construction is performed using one of the functions below. The result is a spline1dinterpolant structure containing the spline model:
After spline is built and you have spline1dinterpolant structure, 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 x_{2 }. We want to calculate function values on a new grid x_{2 } using cubic splines. Additionally, we may need first or second derivatives.
We can solve this problem by building cubic spline with spline1dbuildcubic function and calling spline1ddiff for each of the new nodes (see below). Such code has O(n_{2 }·log(n_{1 })) complexity. However, there is an easier and faster solution - to use special functions for grid operations:
These functions use 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(n_{2 },n_{1 })).
Note #1
If grids are not presorted, complexity increases to O(n_{2 }·log(n_{2 })+n_{1 }·log(n_{1 })) because of time needed to sort grids.
However, it is still beneficial to use specialized functions.
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.
ALGLIB Reference Manual includes following examples on cubic spline interpolation:
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.
Note #2
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 licensed for personal use only.
ALGLIB Project offers you two editions of ALGLIB:
ALGLIB Free Edition:
delivered for free
offers full set of numerical functionality
extensive algorithmic optimizations
no low level optimizations
non-commercial license
ALGLIB Commercial Edition:
flexible pricing
offers full set of numerical functionality
extensive algorithmic optimizations
high performance (SMP, SIMD)
commercial license with support plan
Links to download sections for Free and Commercial editions can be found below: