Spline interpolation

From Wikipedia, the free encyclopedia

Jump to: navigation, search

[edit] 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)\quad i=0,1,\cdots ,n$ is to interpolate between all the pairs of "knots" $(x_{i-1}\ ,\ y_{i-1})$ and $(x_i\ ,\ y_i)$ with polynomials $y=q_i(x) \quad i=1,2,\cdots ,n$

The curvature of a curve

$y=f(x)$

is

$\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'$ and $y''$ will be continuous everywhere, also at the "knots". To achieve this one must have that

$q'_i(x_i) = q'_{i+1}(x_i)$

and that

$q''_i(x_i) = q''_{i+1}(x_i)$

for all i , $1 \le i \le n-1$ . 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".

[edit] Algorithm to find the interpolating cubic spline

A third order polynomial $q(x)$ for which

$q(x_1)=y_1$

$q(x_2)=y_2$

$q^'(x_1)=k_1$

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

(1)

where

$t=\frac{x-x_1}{x_2-x_1}$

(2)

and

$a= k_1 (x_2 - x_1)-(y_2 - y_1)$

(3)

$b=-k_2 (x_2 - x_1)+(y_2 - y_1)$

(4)

As $q^'= \frac{d q}{d x} = \frac{d q}{d t} \ \frac{d t}{d x} = \frac{d q}{d t} \ \frac{1}{x_2-x_1}$ one gets that

$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\frac {b-2a+(a-b)3t}{{(x_2-x_1)}^2}$

(6)

Setting $x=x_1$ and $x=x_2$ in (5) and (6) one gets from (2) that indeed $q^'(x_1)= k_1$ , $q^'(x_2) = k_2$ and that

$q^{''}(x_1)=2\frac {b-2a}{{(x_2-x_1)}^2}$

(7)

$q^{''}(x_2)=2\frac {a-2b}{{(x_2-x_1)}^2}$

(8)

If now

$(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)\quad i=1,\cdots ,n$

(9)

where

$t=\frac{x-x_{i-1}}{x_i-x_{i-1}}$

are n third degree polynomials interpolating $y$ in the interval $x_{i-1} \le x<x_i \le$ , for $i=1,\cdots ,n$ such that

$q^'_i(x_i)=q^'_{i+1}(x_i)$

for $i=1,\cdots ,n-1$

then the n polynomials together define a differentiable function in the interval $x_0 \le x \le x_n$ and

$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})$

(11)

for $i=1,\cdots ,n$ where

$k_0=q_1^'(x_0)$

(12)

$k_i=q_i^'(x_i)=q_{i+1}^'(x_i) \quad i=1,\cdots ,n-1$

(13)

$k_n=q_n^'(x_n)$

(14)

If the sequence $k_0,k_1, \cdots ,k_n$ is such that in addition

$q^{''}_i(x_i)=q^{''}_{i+1}(x_i)$

for $i=1,\cdots ,n-1$

the resulting function will even have a continuous second derivative.

From (7), (8), (10) and (11) follows that this is the case if and only if

$\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,\cdots ,n-1$

The relations (15) are n-1 linear equations for the n+1 values $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$ . As $q''$ should be a continuous function of $x$ one gets that for "Natural Splines" one in addition to the n-1 linear equations (15) should have that

$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\ \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

$\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)

$\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) together with (16) and (17) constitute n+1 linear equations that uniquely define the n+1 parameters $k_0,k_1, \cdots ,k_n$

[edit] 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$ are found by solving the linear equation system

$\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}$