Spline interpolation and fitting

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):

Contents

    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

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.

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.

Catmull-Rom spline

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:

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).

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).

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, xi+1 ] depends on fi-2 , fi-1 , f, 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 x and xN-3  when the index goes from 0 to N-1) the interpolation error has order O(h 2).

Monotone spline

Monotone cubic interpolation is a variant of cubic spline that preserves monotonicity of the data being interpolated.

Spline interpolation in ALGLIB

Spline construction

Spline construction is performed using one of the functions below. The result is a spline1dinterpolant structure containing the spline model:

Interpolation, differentiation, integration, transformation

After spline is built and you have spline1dinterpolant structure, you can use following functions:

Fast batch interpolation on a grid

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. We want to calculate function values on a new grid x 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·log(n)) 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,n)).

Note #1
If grids are not presorted, complexity increases to O(n·log(n)+n·log(n)) because of time needed to sort grids. However, it is still beneficial to use specialized functions.

Cubic spline fitting

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.

Examples

ALGLIB Reference Manual includes following examples on cubic spline interpolation:

Numerical results

In this section we will show numerical results obtained from solution of different problems. We will investigate following "typical" problems:

Interpolation by different spline types

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.

Download ALGLIB for C++ / C# / ...

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:

ALGLIB 3.14.0 for C++

C++ library.
Delivered with sources.
Monolithic design.
Extreme portability.
Editions:   FREE   COMMERCIAL

ALGLIB 3.14.0 for C#

C# library with native kernels.
Delivered with sources.
VB.NET and IronPython wrappers.
Extreme portability.
Editions:   FREE   COMMERCIAL

ALGLIB 3.14.0 for Delphi

Delphi wrapper around C core.
Delivered as precompiled binary.
Compatible with FreePascal.
Editions:   FREE   COMMERCIAL

ALGLIB 3.14.0 for CPython

CPython wrapper around C core.
Delivered as precompiled binary.
Editions:   FREE   COMMERCIAL