Spline interpolation

From open-encyclopedia.com - the free encyclopedia.

In the mathematical subfield of numerical analysis spline interpolation is a special form of interpolation where the interpolant is a piecewise polynomial called 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. Thus spline interpolation avoids the problem of Runge's phenomenon which occurs when using high degree polynomials.

Definition

Given n+1 distinct knots x_i such that

<math>x_0 < x_1 < ... < x_{n-1} < x_n, \,\! <math>

with n+1 knot values y_i we are trying to find a spline function of degree n

<math>

S(x) := \left\{\begin{matrix}

   S_0(x) & x \in [x_0, x_1] \\
   S_1(x) & x \in [x_1, x_2] \\
   \vdots & \vdots \\

S_{k-1}(x) & x \in [x_{k-1}, x_k] \end{matrix}\right. <math>

with each S_i(x) a polynomial of degree n.

Spline interpolant

Using polynomial interpolation the polynomial of degree n which interpolates the data set is uniquely defined by the data points. The spline of degree n which interpolates the same data set is not uniquely defined and we have to fill in n-1 additional degrees of freedom to construct a unique spline interpolant.

Linear spline interpolation

Linear spline interpolation is the most simple spline interpolation. Graphically we just connect the data points by straight lines. The spline is just a polygon.

Algebraically each S_i is a linear function constructed as

<math>S_i(x) = y_i + \frac{y_{i+1}-y_i}{x_{i+1}-x_i}(x-x_i)<math>

The spline must be continuous at each data point that is

<math>S_i(x_i) = S_{i+1}(x_i) \qquad \mbox{ , } i=0,\ldots k -1<math>

This is the case as we can easily see

<math>S_{i-1}(x_i) = y_{i-1} + \frac{y_{i}-y_{i-1}}{x_{i}-x_{i-1}}(x_i-x_{i-1}) = y_i<math>

<math>S_{i}(x_i) = y_i + \frac{y_{i+1}-y_i}{x_{i+1}-x_i}(x_i-x_i) = y_i<math>

Quadratic spline interpolation

The quadratic spline can be constructed as

<math>

S_i(x) = y_i + z_i(x-x_i) + \frac{z_{i+1}-z_i}{2(x_{i+1}-x_i)}(x-x_i)^2 <math>

The coefficients can be found by choosing a <math>z_0<math> and then using the recurrence relation:

<math>

z_{i+1} = -z_i + 2 \frac{y_{i+1}-y_i}{x_{i+1}-x_i} <math>

Cubic spline interpolation

To construct a unique cubic inpolating spline for the given data set we have to specify two additional degress of freedom.

The spline is called clamped cubic spline if

<math> S'(x_0) = u \,\!<math>

<math> S'(x_k) = v \,\!<math>

for given values u and v.

It is called periodic cubic spline if

<math> S(x_0) = S(x_n) \,\!<math>

<math> S'(x_0) = S'(x_n) \,\!<math>

<math> S''(x_0) = S''(x_n) \,\!<math>

And it is called natural cubic spline if

<math>S''(x_0) = S''(x_n) = 0 \,\!<math>.

The natural cubic spline is approximately the same curve as created by the spline device.

Interpolation using natural cubic spline

It can be defined as

<math>

S_i(x) = \frac{z_{i+1} (x-x_i)^3 + z_i (x_{i+1}-x)^3}{6h_i}

      + \left(\frac{y_{i+1}}{h_i} - \frac{h_i}{6} z_{i+1}\right)(x-x_i)
      + \left(\frac{y_{i}}{h_i} - \frac{h_i}{6} z_i\right) (x_{i+1}-x)

<math>

and

<math>h_i = x_{i+1} - x_i \,\!<math>.

The coefficients can be found by solving this system of equations:

<math>

\left\{\begin{matrix}

      z_0 = 0 \\

      h_{i-1}            z_{i-1}
      + 2(h_{i-1} + h_i) z_i
      + h_i              z_{i+1}

      = 6 \left(
          \frac{y_{i+1}-y_i}{h_i} - 
          \frac{y_i-y_{i-1}}{h_{i-1}}
          \right) \\

      z_n = 0

\end{matrix}\right. <math>

Example

Linear spline interpolation

Consider the problem of finding a linear spline for

<math>f(x) = e^{-x^2} <math>

with the following knots

<math> (x_0,f(x_0)) = (x_0,y_0) = \left(-1,\ e^{-1}\right) \,\! <math>

<math> (x_1,f(x_1)) = (x_1,y_1) = \left(-\frac{1}{2},\ e^{-\frac{1}{4}}\right) \,\! <math>

<math> (x_2,f(x_2)) = (x_2,y_2) = \left(0,\ 1\right) \,\! <math>

<math> (x_3,f(x_3)) = (x_3,y_3) = \left(\frac{1}{2},\ e^{-\frac{1}{4}}\right) \,\! <math>

<math> (x_4,f(x_4)) = (x_4,y_4) = \left(1,\ e^{-1}\right) \,\! <math>

After directly applying the spline formula, we get the following spline:

<math>

S(x) = \left\{\begin{matrix} e^{-1} + 2(e^{-\frac{1}{4}} - e^{-1})(x+1) & x \in [-1, -\frac{1}{2}] \\ e^{-\frac{1}{4}} + 2(1-e^{-\frac{1}{4}})(x+\frac{1}{2}) & x \in [-\frac{1}{2},0] \\ 1 + 2(e^{-\frac{1}{4}}-1)x & x \in [0,\frac{1}{2}] \\ e^{-\frac{1}{4}} + 2(e^{-1} - e^{-\frac{1}{4}})(x-\frac{1}{2}) & x \in [\frac{1}{2},1] \\ \end{matrix}\right. <math>

The spline function (blue lines) and the function it is approximating (red dots) are graphed below:

Quadratic spline interpolation

The graph below is an example of a spline function (blue lines) and the function it is approximating (red lines) for k=4:

See also

• Cubic Hermite spline