Spline interpolation

From Wikipedia, the free encyclopedia

Jump to: navigation, search

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. Thus, spline interpolation avoids the problem of Runge's phenomenon which occurs when using high degree polynomials.

Contents

[edit] Definition

Given n+1 distinct knots xi such that

x_0 < x_1 < \cdots < x_{n-1} < x_n, \,\!

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

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_{n-1}(x) & x \in [x_{n-1}, x_n] \end{matrix}\right.

where each Si(x) is a polynomial of degree k.

[edit] 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.

[edit] Linear spline interpolation

Linear spline interpolation is the simplest form of spline interpolation and is equivalent to linear interpolation. The data points are graphically connected by straight lines. The resultant spline would be a polygon if the end point is connected to the beginning points.

Algebraically, each Si is a linear function constructed as

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

The spline must be continuous at each data point, that is

S_{i-1}(x_i) = S_{i}(x_i) \qquad \mbox{ , } i=1,\ldots n -1

This is the case as we can easily see

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
S_{i}(x_i) = y_i + \frac{y_{i+1}-y_i}{x_{i+1}-x_i}(x_{i}-x_i) = y_{i}

[edit] Quadratic spline interpolation

The quadratic spline can be constructed as

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

The coefficients can be found by choosing a z0 and then using the recurrence relation:

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

The coefficients z above are basically a running derivative approximation. Since only two points are used to calculate the next iteration's curve (instead of three), this method is susceptible to severe oscillation effects when signal change is quickly followed by a steady signal. Without some sort of dampening, these oscillation effects make the above method a poor choice.

A more stable alternative to this method is a cubic spline passing through the middle points of the original data instead. To calculate Si(x) first select a j such that xj−1 < x < xj+1 and that |xj−1 − x| + |xj+1 − x| is minimized. Then, find a, b, c and d of S(x) = ax3 + bx2 + cx + d such that:

\begin{align} S \left( \frac{x_{j-1} + x_j}{2} \right) = \frac{y_{j-1} + y_j}{2}\\ S'\left( \frac{x_{j-1} + x_j}{2} \right) = \frac{y_j-y_{j-1}}{x_j-x_{j-1}}\\ S \left( \frac{x_j + x_{j+1}}{2} \right) = \frac{y_j + y_{j+1}}{2}\\ S'\left( \frac{x_j + x_{j+1}}{2} \right) = \frac{y_j-y_{j+1}}{x_{j+1}-x_j} \end{align}

In effect, this yields a set of curves that are continuous in the first degree, highly stable (i.e. aren't subject to oscillation effects) and does not require huge matrix solving.

[edit] Cubic spline interpolation

For a data set {xi} of n+1 points, we can construct a cubic spline with n piecewise cubic polynomials between the data points. If

S(x)=\left\{\begin{matrix} S_0(x),\ x\in[x_0,x_1]\\ S_1(x),\ x\in[x_1,x_2]\\ \cdots \\ S_{n-1}(x),\ x\in[x_{n-1},x_n]\end{matrix}\right.

represents the spline function interpolating the function f, we require:

  • the interpolating property, S(xi)=f(xi)
  • the splines to join up, Si-1(xi) = Si(xi), i =1,...,n-1
  • twice continuous differentiable, S'i-1(xi) = S'i(xi) and S''i-1(xi) = S''i(xi), i =1,...,n -1.

For the n cubic polynomials comprising S, this means to determine these polynomials, we need to determine 4n conditions (since for one polynomial of degree three, there are four conditions on choosing the curve). However, the interpolating property gives us n + 1 conditions, and the conditions on the interior data points give us n + 1 − 2 = n − 1 data points each, summing to 4n − 2 conditions. We require two other conditions, and these can be imposed upon the problem for different reasons.

One such choice results in the so-called clamped cubic spline, with

S'(x_0) = u \,\!
S'(x_k) = v \,\!

for given values u and v.

Alternately, we can set

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

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

Amongst all twice continuously differentiable functions, clamped and natural cubic splines yield the least oscillation about the function f which is interpolated.

Another choice gives the periodic cubic spline if

S(x_0) = S(x_n) \,\!
S'(x_0) = S'(x_n) \,\!
S''(x_0) = S''(x_n) \,\!

Another choice gives the complete cubic spline if

S(x_0) = S(x_n) \,\!
S'(x_0) = S'(x_n) \,\!
S''(x_0) = f'(x_0),\quad S''(x_n)=f'(x_n) \,\!

[edit] Minimality of the cubic splines

The cubic spline has a very important variational interpretation, in fact it is the function that minimizes the functional

J(f)=\int_a^b |f''(x)|^2 dx,

over the functions in the Sobolev space H2([a;b]).

The functional J contains an approximation of the total curvature \left|\frac{f''(x)}{(1+f'(x)^2)^{\frac{3}{2}}}\right| of the graph of f(x) and then the spline is the approximation of f(x) with minimal curvature. It is also aesthetically pleasing.

Since the total energy of an elastic strip is proportional to the curvature, the spline is the configuration of minimal energy of an elastic strip constrained to n points. A spline is also an instrument to design based on an elastic strip.

[edit] Interpolation using natural cubic spline

It can be defined as

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)

and


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

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

\begin{align} 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) \qquad \mbox{ , } i=1,\ldots n -1\\ z_n &= 0 \end{align}

[edit] Example

[edit] Linear spline interpolation

Consider the problem of finding a linear spline for

f(x) = e^{-x^2}

with the following knots

(x_0,f(x_0)) = (x_0,y_0) = \left(-1,\ e^{-1}\right) \,\!
(x_1,f(x_1)) = (x_1,y_1) = \left(-\frac{1}{2},\ e^{-\frac{1}{4}}\right) \,\!
(x_2,f(x_2)) = (x_2,y_2) = \left(0,\ 1\right) \,\!
(x_3,f(x_3)) = (x_3,y_3) = \left(\frac{1}{2},\ e^{-\frac{1}{4}}\right) \,\!
(x_4,f(x_4)) = (x_4,y_4) = \left(1,\ e^{-1}\right) \,\!

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

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.

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


[edit] See also

[edit] External links

Retrieved from "http://en.wikipedia.org/wiki/Spline_interpolation"
Personal tools