Spline interpolation
Encyclopedia
In the mathematical
field of numerical analysis
, spline interpolation is a form of interpolation
where the interpolant is a special type of piecewise
polynomial
called a spline
. Spline interpolation is preferred over polynomial interpolation
because the interpolation error can be made small even when using low degree polynomials for the spline. Spline interpolation avoids the problem of Runge's phenomenon
which occurs when interpolating between equidistant points with high degree polynomials.
that were bent to pass through a number of predefined points (the "knots") were used for making technical drawings for shipbuilding and construction by hand, as illustrated by figure 1.
The approach to mathematically model the shape of such elastic rulers fixed by n+1 "knots"
is to interpolate between all the pairs of "knots" 
and 
with polynomials 
The curvature
of a curve
is
As the elastic ruler will take a shape that minimizes the bending under the constraint of passing through all "knots" both
and 
will be continuous everywhere, also at the "knots". To achieve this one must have that
and that
for all i ,
. This can only be achieved if polynomials of degree 3 or higher are used. The classical approach is to use polynomials of degree 3, this is the case of "Cubic splines".
for which
can be written in the symmetrical form
where
and
As
one gets that
Setting
and 
in and one gets from that indeed 
, 
and that
If now
are n+1 points and
where
are n third degree polynomials interpolating
in the interval 
,
for
such that
for
then the n polynomials together define a derivable function in the interval
and
for
where
If the sequence
is such that in addition
for
the resulting function will even have a continuous second derivative.
From , , and follows that this is the case if and only if
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
field of numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
, spline interpolation is a form of interpolation
Interpolation
In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points....
where the interpolant is a special type of piecewise
Piecewise
On mathematics, a piecewise-defined function is a function whose definition changes depending on the value of the independent variable...
polynomial
Polynomial
In mathematics, a polynomial is an expression of finite length constructed from variables and constants, using only the operations of addition, subtraction, multiplication, and non-negative integer exponents...
called a spline
Spline (mathematics)
In mathematics, a spline is a sufficiently smooth piecewise-polynomial function. In interpolating problems, spline interpolation is often preferred to polynomial interpolation because it yields similar results, even when using low-degree polynomials, while avoiding Runge's phenomenon for higher...
. Spline interpolation is preferred over polynomial interpolation
Polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial: given some points, find a polynomial which goes exactly through these points.- Applications :...
because the interpolation error can be made small even when using low degree polynomials for the spline. Spline interpolation avoids the problem of Runge's phenomenon
Runge's phenomenon
In the mathematical field of numerical analysis, Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree...
which occurs when interpolating between equidistant points with high degree polynomials.
Introduction
Elastic rulersFlat spline
A spline or the more modern term flexible curve consists of a long strip fixed in position at a number of points that relaxes to form and hold a smooth curve passing through those points for the purpose of transferring that curve to another material....
that were bent to pass through a number of predefined points (the "knots") were used for making technical drawings for shipbuilding and construction by hand, as illustrated by figure 1.
The approach to mathematically model the shape of such elastic rulers fixed by n+1 "knots"
is to interpolate between all the pairs of "knots" and with polynomials The curvature
Curvature
In mathematics, curvature refers to any of a number of loosely related concepts in different areas of geometry. Intuitively, curvature is the amount by which a geometric object deviates from being flat, or straight in the case of a line, but this is defined in different ways depending on the context...
of a curve
is
As the elastic ruler will take a shape that minimizes the bending under the constraint of passing through all "knots" both
and will be continuous everywhere, also at the "knots". To achieve this one must have thatand that
for all i ,
. This can only be achieved if polynomials of degree 3 or higher are used. The classical approach is to use polynomials of degree 3, this is the case of "Cubic splines".Algorithm to find the interpolating cubic spline
A third order polynomial for whichcan be written in the symmetrical form
where
and
As
one gets that
Setting
and in and one gets from that indeed , and that
If now
are n+1 points and
where
are n third degree polynomials interpolating
in the interval ,for
such thatfor
then the n polynomials together define a derivable function in the interval
andfor
where
If the sequence
is such that in additionfor
the resulting function will even have a continuous second derivative.
From , , and follows that this is the case if and only if
-
for
The relations are n-1 linear equations for the n+1 values
.
For the elastic rulers being the model for the spline interpolation one has that to the left of the left-most "knot" and to the right of the right-most "knot" the ruler can move freely and will therefore take the form of a straight line with
. As 
should be a continuous function of 
one gets that for "Natural Splines" one in addition to the n-1 linear equations should have that
i.e. that
together with and constitute n+1 linear equations that uniquely define the n+1 parameters
Example
In case of three points the values for
are found by solving the linear equation system
with
For the three points
one gets that
and from and that
In figure 2 the spline function consisting of the two cubic polynomials
and 
given by is displayed
See also
- Cubic Hermite splineCubic Hermite splineIn the mathematical subfield of numerical analysis a cubic Hermite spline , named in honor of Charles Hermite, is a third-degree spline with each polynomial of the spline in Hermite form...
- Monotone cubic interpolationMonotone cubic interpolationIn the mathematical subfield of numerical analysis, monotone cubic interpolation is a variant of cubic interpolation that preserves monotonicity of the data set being interpolated....
- NURBS
- Multivariate interpolationMultivariate interpolationIn numerical analysis, multivariate interpolation or spatial interpolation is interpolation on functions of more than one variable.The function to be interpolated is known at given points and the interpolation problem consist of yielding values at arbitrary points .-Regular grid:For function...
- Polynomial interpolationPolynomial interpolationIn numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial: given some points, find a polynomial which goes exactly through these points.- Applications :...
- Smoothing splineSmoothing splineThe smoothing spline is a method of smoothing using a spline function.-Definition:Let ;x_1...
External links