NationMaster - Encyclopedia: Spline interpolation

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. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Numerical analysis is the study of approximate methods for the problems of continuous mathematics (as distinguished from discrete mathematics). ... In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ... In mathematics, a function f(x) of a real number variable x is defined piecewise, if f(x) is given by different expressions on various intervals. ... In mathematics, a polynomial is an expression that is constructed from one or more variables and constants, using only the operations of addition, subtraction, multiplication, and constant positive whole number exponents. ... One type of spline, a bÃ©zier curve In the mathematical subfield of numerical analysis, a spline is a special function defined piecewise by polynomials. ... In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. ... This article is about interpolation in mathematics. ... The red curve is the Runge function, the blue curve is a 5th-degree polynomial, while the green curve is a 9th-degree polynomial. ...

1 Definition
2 Spline interpolant
3 Linear spline interpolation
4 Quadratic spline interpolation
5 Cubic spline interpolation
- 5.1 Minimality of the cubic splines
- 5.2 Interpolation using natural cubic spline
6 Example
- 6.1 Linear spline interpolation
- 6.2 Quadratic spline interpolation
7 See also

Definition

Given n+1 distinct knots x_i such that

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

with n+1 knot values y_i we are trying to find a spline function of degree n Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A...

$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 S_i(x) is a polynomial of degree k.

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. A data set (or dataset) is a collection of data, usually presented in tabular form. ... Degrees of freedom is a general term used in explaining dependence on parameters, and implying the possibility of counting the number of those parameters. ...

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 point. Linear interpolation is a process employed in mathematics, and numerous applications including computer graphics. ... A line, or straight line, is, roughly speaking, an (infinitely) thin, (infinitely) long, straight geometrical object, i. ... Look up polygon in Wiktionary, the free dictionary. ...

Algebraically, each S_i is a linear function constructed as A linear function is a mathematical function term of the form: f(x) = m x + c where c is a constant. ...

$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(x_i) = S_{i+1}(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$

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 $z 0$ and then using the recurrence relation: In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ...

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

Cubic spline interpolation

For a data set {x_i} of n+1 points, we can construct a cubic spline with n piecewise cubic polynomials between the data points. If See also: cubic equation, Bézier curve, spline. ...

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

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

the interpolating property, S(x_i)=f(x_i)
the splines to join up, S_i-1(x_i) = S_i(x_i), i=1,...,n-1
twice continuous differentiable, S'_i-1(x_i) = S'_i(x_i) and S''_i-1(x_i) = S''_i(x_i), 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. A spline consists of a long strip of wood (a lath, not to be confused with lathe) fixed in position at a number of points. ...

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

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 function in the Sobolev space $H 2 ([a; b])$ . In mathematics, a Sobolev space is a normed space of functions obtained by imposing on a function f and its weak derivatives up to some order k the condition of finite Lp norm, for given p â‰¥ 1. ...

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, and also looks good, psychologically. In mathematics, curvature refers to a number of loosely related concepts in different areas of geometry. ...

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.

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_iright) (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) z_n &= 0 end{align}$

Example

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, 1right) ,!$

$(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 dots) are graphed below:

An image of a linear spline and the function it is approximating. ...

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:

An image of a quadratic spline and the function it is approximating. ...

Contents

Definition GA_googleFillSlot("encyclopedia_square");

Spline interpolant

Linear spline interpolation

Quadratic spline interpolation

Cubic spline interpolation

Minimality of the cubic splines

Interpolation using natural cubic spline

Example

Linear spline interpolation

Quadratic spline interpolation

See also

Definition