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.
Introduction
Elastic rulers 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.
Figure 1: Interpolation with cubic splines between eight points. Hand-drawn technical drawings were made for ship-building etc. using flexible rulers that were bent to follow pre-defined points (the "knots") The approach to mathematically model the shape of such elastic rulers fixed by n+1 "knots"
(
x
i
,
y
i
)
i
=
0
,
1
,
⋯
,
n
{\displaystyle (x_{i},y_{i})\quad i=0,1,\cdots ,n}
(
x
i
−
1
,
y
i
−
1
)
{\displaystyle (x_{i-1}\ ,\ y_{i-1})}
(
x
i
,
y
i
)
{\displaystyle (x_{i}\ ,\ y_{i})}
y
=
q
i
(
x
)
i
=
1
,
2
,
⋯
,
n
{\displaystyle y=q_{i}(x)\quad i=1,2,\cdots ,n}
The curvature of a curve
y
=
f
(
x
)
{\displaystyle y=f(x)}
is
κ
=
y
″
(
1
+
y
′
2
)
3
/
2
{\displaystyle \kappa ={\frac {y''}{(1+y'^{2})^{3/2}}}}
As the elastic ruler will take a shape that minimizes the bending under the constraint of passing through all "knots" both
y
′
{\displaystyle y'}
y
″
{\displaystyle y''}
q
i
′
(
x
i
)
=
q
i
+
1
′
(
x
i
)
{\displaystyle q'_{i}(x_{i})=q'_{i+1}(x_{i})}
and that
q
i
″
(
x
i
)
=
q
i
+
1
″
(
x
i
)
{\displaystyle q''_{i}(x_{i})=q''_{i+1}(x_{i})}
for all i ,
1
≤
i
≤
n
−
1
{\displaystyle 1\leq i\leq n-1}
Algorithm to find the interpolating cubic spline
A third order polynomial
q
(
x
)
{\displaystyle q(x)}
q
(
x
1
)
=
y
1
{\displaystyle q(x_{1})=y_{1}}
q
(
x
2
)
=
y
2
{\displaystyle q(x_{2})=y_{2}}
q
′
(
x
1
)
=
k
1
{\displaystyle q^{'}(x_{1})=k_{1}}
q
′
(
x
2
)
=
k
2
{\displaystyle q^{'}(x_{2})=k_{2}}
can be written in the symmetrical form
q
=
(
1
−
t
)
y
1
+
t
y
2
+
t
(
1
−
t
)
(
a
(
1
−
t
)
+
b
t
)
{\displaystyle q\ =\ (1-t)\ y_{1}+\ t\ y_{2}\ +\ t\ (1-t)\ (a\ (1-t)+b\ t)}
1
where
t
=
x
−
x
1
x
2
−
x
1
{\displaystyle t={\frac {x-x_{1}}{x_{2}-x_{1}}}}
2
and
a
=
k
1
(
x
2
−
x
1
)
−
(
y
2
−
y
1
)
{\displaystyle a=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})}
3
b
=
−
k
2
(
x
2
−
x
1
)
+
(
y
2
−
y
1
)
{\displaystyle b=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})}
4
q
′
=
d
q
d
x
=
d
q
d
t
d
t
d
x
=
d
q
d
t
1
x
2
−
x
1
{\displaystyle q^{'}={\frac {dq}{dx}}={\frac {dq}{dt}}\ {\frac {dt}{dx}}={\frac {dq}{dt}}\ {\frac {1}{x_{2}-x_{1}}}}
q
′
=
y
2
−
y
1
x
2
−
x
1
+
(
1
−
2
t
)
a
(
1
−
t
)
+
b
t
x
2
−
x
1
+
t
(
1
−
t
)
b
−
a
x
2
−
x
1
{\displaystyle q^{'}\ ={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}+(1-2t)\ {\frac {a\ (1-t)+b\ t}{x_{2}-x_{1}}}\ +\ \ t\ (1-t)\ {\frac {b-a}{x_{2}-x_{1}}}}
5
q
″
=
2
b
−
2
a
+
(
a
−
b
)
3
t
(
x
2
−
x
1
)
2
{\displaystyle q^{''}=2{\frac {b-2a+(a-b)3t}{{(x_{2}-x_{1})}^{2}}}}
6
Setting
x
=
x
1
{\displaystyle x=x_{1}}
x
=
x
2
{\displaystyle x=x_{2}}
5 6 2
q
′
(
x
1
)
=
k
1
{\displaystyle q^{'}(x_{1})=k_{1}}
q
′
(
x
2
)
=
k
2
{\displaystyle q^{'}(x_{2})=k_{2}}
q
″
(
x
1
)
=
2
b
−
2
a
(
x
2
−
x
1
)
2
{\displaystyle q^{''}(x_{1})=2{\frac {b-2a}{{(x_{2}-x_{1})}^{2}}}}
7
q
″
(
x
2
)
=
2
a
−
2
b
(
x
2
−
x
1
)
2
{\displaystyle q^{''}(x_{2})=2{\frac {a-2b}{{(x_{2}-x_{1})}^{2}}}}
8
If now
(
x
i
,
y
i
)
i
=
0
,
1
,
⋯
,
n
{\displaystyle (x_{i},y_{i})\quad i=0,1,\cdots ,n}
are n+1 points and
q
i
=
(
1
−
t
)
y
i
−
1
+
t
y
i
+
t
(
1
−
t
)
(
a
i
(
1
−
t
)
+
b
i
t
)
i
=
1
,
⋯
,
n
{\displaystyle q_{i}\ =\ (1-t)\ y_{i-1}+\ t\ y_{i}\ +\ t\ (1-t)\ (a_{i}\ (1-t)+b_{i}\ t)\quad i=1,\cdots ,n}
9
where
t
=
x
−
x
i
−
1
x
i
−
x
i
−
1
{\displaystyle t={\frac {x-x_{i-1}}{x_{i}-x_{i-1}}}}
are n third degree polynomials interpolating
y
{\displaystyle y}
x
i
−
1
≤
x
<
x
i
≤
{\displaystyle x_{i-1}\leq x<x_{i}\leq }
i
=
1
,
⋯
,
n
{\displaystyle i=1,\cdots ,n}
q
i
′
(
x
i
)
=
q
i
+
1
′
(
x
i
)
{\displaystyle q_{i}^{'}(x_{i})=q_{i+1}^{'}(x_{i})}
for
i
=
1
,
⋯
,
n
−
1
{\displaystyle i=1,\cdots ,n-1}
then the n polynomials together define a derivable function in the interval
x
0
≤
x
≤
x
n
{\displaystyle x_{0}\leq x\leq x_{n}}
a
i
=
k
i
−
1
(
x
i
−
x
i
−
1
)
−
(
y
i
−
y
i
−
1
)
{\displaystyle a_{i}=k_{i-1}(x_{i}-x_{i-1})-(y_{i}-y_{i-1})}
10
b
i
=
−
k
i
(
x
i
−
x
i
−
1
)
+
(
y
i
−
y
i
−
1
)
{\displaystyle b_{i}=-k_{i}(x_{i}-x_{i-1})+(y_{i}-y_{i-1})}
11
for
i
=
1
,
⋯
,
n
{\displaystyle i=1,\cdots ,n}
k
0
=
q
1
′
(
x
0
)
{\displaystyle k_{0}=q_{1}^{'}(x_{0})}
12
k
i
=
q
i
′
(
x
i
)
=
q
i
+
1
′
(
x
i
)
i
=
1
,
⋯
,
n
−
1
{\displaystyle k_{i}=q_{i}^{'}(x_{i})=q_{i+1}^{'}(x_{i})\quad i=1,\cdots ,n-1}
13
k
n
=
q
n
′
(
x
n
)
{\displaystyle k_{n}=q_{n}^{'}(x_{n})}
14
If the sequence
k
0
,
k
1
,
⋯
,
k
n
{\displaystyle k_{0},k_{1},\cdots ,k_{n}}
q
i
″
(
x
i
)
=
q
i
+
1
″
(
x
i
)
{\displaystyle q_{i}^{''}(x_{i})=q_{i+1}^{''}(x_{i})}
for
i
=
1
,
⋯
,
n
−
1
{\displaystyle i=1,\cdots ,n-1}
the resulting function will even have a continuous second derivative.
From (7 8 10 11
k
i
−
1
x
i
−
x
i
−
1
+
(
1
x
i
−
x
i
−
1
+
1
x
i
+
1
−
x
i
)
2
k
i
+
k
i
+
1
x
i
+
1
−
x
i
=
3
(
y
i
−
y
i
−
1
(
x
i
−
x
i
−
1
)
2
+
y
i
+
1
−
y
i
(
x
i
+
1
−
x
i
)
2
)
{\displaystyle {\frac {k_{i-1}}{x_{i}-x_{i-1}}}+\left({\frac {1}{x_{i}-x_{i-1}}}+{\frac {1}{x_{i+1}-x_{i}}}\right)\ 2k_{i}+{\frac {k_{i+1}}{x_{i+1}-x_{i}}}=3\ \left({\frac {y_{i}-y_{i-1}}{{(x_{i}-x_{i-1})}^{2}}}+{\frac {y_{i+1}-y_{i}}{{(x_{i+1}-x_{i})}^{2}}}\right)}
15
for
i
=
1
,
⋯
,
n
−
1
{\displaystyle i=1,\cdots ,n-1}
The relations (15
k
0
,
k
1
,
⋯
,
k
n
{\displaystyle k_{0},k_{1},\cdots ,k_{n}}
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
q
″
=
0
{\displaystyle q''=0}
q
″
{\displaystyle q''}
x
{\displaystyle x}
15
q
i
″
(
x
0
)
=
2
3
(
y
1
−
y
0
)
−
(
k
1
+
2
k
0
)
(
x
1
−
x
0
)
(
x
1
−
x
0
)
2
=
0
{\displaystyle q_{i}^{''}(x_{0})\ =2\ {\frac {3(y_{1}-y_{0})-(k_{1}+2k_{0})(x_{1}-x_{0})}{{(x_{1}-x_{0})}^{2}}}=0}
q
n
″
(
x
n
)
=
−
2
3
(
y
n
−
y
n
−
1
)
−
(
2
k
n
+
k
n
−
1
)
(
x
n
−
x
n
−
1
)
(
x
n
−
x
n
−
1
)
2
=
0
{\displaystyle q_{n}^{''}(x_{n})\ =-2\ {\frac {3(y_{n}-y_{n-1})-(2k_{n}+k_{n-1})(x_{n}-x_{n-1})}{{(x_{n}-x_{n-1})}^{2}}}=0}
i.e. that
2
x
1
−
x
0
k
0
+
1
x
1
−
x
0
k
1
=
3
y
1
−
y
0
(
x
1
−
x
0
)
2
{\displaystyle {\frac {2}{x_{1}-x_{0}}}k_{0}\ +{\frac {1}{x_{1}-x_{0}}}k_{1}=3\ {\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}}}
16
1
x
n
−
x
n
−
1
k
n
−
1
+
2
x
n
−
x
n
−
1
k
n
=
3
y
n
−
y
n
−
1
(
x
n
−
x
n
−
1
)
2
{\displaystyle {\frac {1}{x_{n}-x_{n-1}}}k_{n-1}\ +{\frac {2}{x_{n}-x_{n-1}}}k_{n}=3\ {\frac {y_{n}-y_{n-1}}{(x_{n}-x_{n-1})^{2}}}}
17
(15 16 17
k
0
,
k
1
,
⋯
,
k
n
{\displaystyle k_{0},k_{1},\cdots ,k_{n}}
Example
Figure 2: Interpolation with cubic "natural" splines between three points. In case of three points the values for
k
0
,
k
1
,
k
2
{\displaystyle k_{0},k_{1},k_{2}}
[
a
11
a
12
0
a
21
a
22
a
23
0
a
32
a
33
]
[
k
0
k
1
k
2
]
=
[
b
1
b
2
b
3
]
{\displaystyle {\begin{bmatrix}a_{11}&a_{12}&0\\a_{21}&a_{22}&a_{23}\\0&a_{32}&a_{33}\\\end{bmatrix}}{\begin{bmatrix}k_{0}\\k_{1}\\k_{2}\\\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\b_{3}\\\end{bmatrix}}}
with
a
11
=
2
x
1
−
x
0
{\displaystyle a_{11}={\frac {2}{x_{1}-x_{0}}}}
a
12
=
1
x
1
−
x
0
{\displaystyle a_{12}={\frac {1}{x_{1}-x_{0}}}}
a
21
=
1
x
1
−
x
0
{\displaystyle a_{21}={\frac {1}{x_{1}-x_{0}}}}
a
22
=
2
(
1
x
1
−
x
0
+
1
x
2
−
x
1
)
{\displaystyle a_{22}=2\ \left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\right)}
a
23
=
1
x
2
−
x
1
{\displaystyle a_{23}={\frac {1}{x_{2}-x_{1}}}}
a
32
=
1
x
2
−
x
1
{\displaystyle a_{32}={\frac {1}{x_{2}-x_{1}}}}
a
33
=
2
x
2
−
x
1
{\displaystyle a_{33}={\frac {2}{x_{2}-x_{1}}}}
b
1
=
3
y
1
−
y
0
(
x
1
−
x
0
)
2
{\displaystyle b_{1}=3\ {\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}}}
b
2
=
3
(
y
1
−
y
0
(
x
1
−
x
0
)
2
+
y
2
−
y
1
(
x
2
−
x
1
)
2
)
{\displaystyle b_{2}=3\ \left({\frac {y_{1}-y_{0}}{{(x_{1}-x_{0})}^{2}}}+{\frac {y_{2}-y_{1}}{{(x_{2}-x_{1})}^{2}}}\right)}
b
3
=
3
y
2
−
y
1
(
x
2
−
x
1
)
2
{\displaystyle b_{3}=3\ {\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}}
For the three points
(
−
1
,
0.5
)
,
(
0
,
0
)
,
(
3
,
3
)
{\displaystyle (-1,0.5)\ ,\ (0,0)\ ,\ (3,3)}
one gets that
k
0
=
−
0.6875
,
k
1
=
−
0.1250
,
k
2
=
1.5625
{\displaystyle k_{0}=-0.6875\ ,\ k_{1}=-0.1250\ ,\ k_{2}=1.5625}
and from (10 11
a
1
=
k
0
(
x
1
−
x
0
)
−
(
y
1
−
y
0
)
=
−
0.1875
{\displaystyle a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0.1875}
b
1
=
−
k
1
(
x
1
−
x
0
)
+
(
y
1
−
y
0
)
=
−
0.3750
{\displaystyle b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750}
a
2
=
k
1
(
x
2
−
x
1
)
−
(
y
2
−
y
1
)
=
−
3.3750
{\displaystyle a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750}
b
2
=
−
k
2
(
x
2
−
x
1
)
+
(
y
2
−
y
1
)
=
−
1.6875
{\displaystyle b_{2}=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})=-1.6875}
In figure 2 the spline function consisting of the two cubic polynomials
q
1
(
x
)
{\displaystyle q_{1}(x)}
q
2
(
x
)
{\displaystyle q_{2}(x)}
9
See also
External links
