# Talk:Spline interpolation

WikiProject Computer graphics (Rated Start-class)
This article is within the scope of WikiProject Computer graphics, a collaborative effort to improve the coverage of computer graphics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start  This article has been rated as Start-Class on the project's quality scale.

## Where is equation 2?

Where is equation 2?

## Interpolation using natural cubic spline

I'm missing the good old and easy to understand description of natural cubic splines as there has been around october 2009. I was able to easily implement that. The new and more general description makes no sense to me.. :(

Here's the old description: Interpolation using natural cubic spline

Would be great if someone could look into that and maybe make the article more understandable again. Thanks! — Preceding unsigned comment added by 85.31.3.11 (talk) 11:41, 5 August 2011 (UTC)

## Definition

Given n+1 distinct knots xi such that
${\displaystyle x_{0}
with n+1 knot values yi we are trying to find a spline function of degree n
${\displaystyle 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.}$
with each Si(x) a polynomial of degree n.

Is this not confusing, using n both for the degree of the polynomial, and for the number of points? --Anonymus, wiki nl

There's a k for that. Very well explained then ;) --217.136.81.22, 11:16, 13 Jun 2005 (UTC)

## Natural cubic spline oscillation

Clamped and natural cubic splines yield the least oscillation about f than any other twice continuously differentiable function.

In the above sentence from the article, just what is f? Perhaps the article can be updated to clarify this. --Abelani, 19 November 2005

This is to confirm that someone has posted a clarification. --Abelani, 2:16, 27 November 2005 (UTC)

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

In the above sentence from the article, surely f itself is the function with the least oscillation about f. What is the restricted set of interpolation functions for which the statement is true and interesting? Harold f 03:27, 20 August 2006 (UTC)

## Interpolation using natural cubic spline

In the formulas for interpolation using natural cubic spline, it seems that one could replace each ${\displaystyle z_{i}}$ by ${\displaystyle 6z_{i}}$, enabling one to cancel 6s and obtain

${\displaystyle S_{i}(x)={\frac {z_{i+1}(x-x_{i})^{3}+z_{i}(x_{i+1}-x)^{3}}{h_{i}}}+\left({\frac {y_{i+1}}{h_{i}}}-h_{i}z_{i+1}\right)(x-x_{i})+\left({\frac {y_{i}}{h_{i}}}-h_{i}z_{i}\right)(x_{i+1}-x)}$

and

${\displaystyle {\begin{matrix}h_{i-1}z_{i-1}+2(h_{i-1}+h_{i})z_{i}+h_{i}z_{i+1}={\frac {y_{i+1}-y_{i}}{h_{i}}}-{\frac {y_{i}-y_{i-1}}{h_{i-1}}}\end{matrix}}}$

Is there any reason not to do that? --Jwwalker 01:51, 26 July 2006 (UTC)

## Graphs

Those graphs are a little kooky.. are they 1d or 2d? approximating in what sense?

The second one in particular, a spline approximation of an even function should still be even...

I agree, moving it here:

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

This might be Quadratic spline, but it is NOT how one would normally set up the values. I am pretty sure the quadratic curve should cross/align the midpoints of the linear interpolation curve.

—Preceding unsigned comment added by 80.216.134.151 (talk) 14:17, 9 December 2008 (UTC)

## Usage of the word 'knot'

Is it not 'nodes' in English instead of 'knots'?

I know you would say 'knots' when translating directly from e.g. German but all English textbooks I have call them 'nodes'. Somewikian (talk) 16:55, 6 January 2009 (UTC)

## Minimality Section

In the minimality of cubic spline section it says that the cubic spline minimizes

${\displaystyle J(f)=\int _{a}^{b}|f''(x)|^{2}dx}$,

over the functions in the Sobolev space ${\displaystyle H^{2}([a;b])}$.

That don't have any sense because the minimum it's attained for example with the null function. I think the minimization should be over the functions that interpolates a given function but i'm not sure, someone please correct this. Bunder (talk) 13:10, 12 March 2009 (UTC)

## complete cubic spline

Is this formulation for the complete cubic spline correct?

${\displaystyle S''(x_{0})=f'(x_{0}),\quad S''(x_{n})=f'(x_{n})\,\!}$

The mixing of second and first derivatives seems off to me. According to [1], I think it should be:

${\displaystyle S'(x_{0})=f'(x_{0}),\quad S'(x_{n})=f'(x_{n})\,\!}$

(all first derivatives) -- 128.104.112.179 (talk) 18:23, 20 October 2009 (UTC)

## Rewrite

{{Mergefrom|Spline (mathematics)#Algorithm for computing natural cubic splines|date=February 2010}} and "Spline (mathematics)" also

I agree!

I have here a draft of a radical rewrite that could/should replace both articles! Comments!

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

Making hand-drawn technical drawings for ship building or other constructions elastic rulers were used that were bent to pass through a number of predefined points (the "knots") as illustrated by the following figure.

Interpolation with cubic splines between eight points. Making traditional hand-drawn technical drawings for ship-building etc flexible rulers 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" ${\displaystyle (x_{i},y_{i})\quad i=0,1,\cdots ,n}$ is to interpolate between all the pairs of "knots" ${\displaystyle (x_{i-1}\ ,\ y_{i-1})}$ and ${\displaystyle (x_{i}\ ,\ y_{i})}$ with polynomials ${\displaystyle y=q_{i}(x)\quad i=1,2,\cdots ,n}$

The curvature of a curve

${\displaystyle y=f(x)}$

is

${\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 ${\displaystyle y'}$ and ${\displaystyle y''}$ will be continuous everywhere, also at the "knots". To achieve this one must have that ${\displaystyle q'_{i}(x_{i})=q'_{i+1}(x_{i})}$ and ${\displaystyle q''_{i}(x_{i})=q''_{i+1}(x_{i})}$ for all i , ${\displaystyle 1\leq i\leq 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".

### Cubic splines

A third order polynomial ${\displaystyle q(x)}$ for which

${\displaystyle q(x_{1})=y_{1}}$
${\displaystyle q(x_{2})=y_{2}}$
${\displaystyle q^{'}(x_{1})=k_{1}}$
${\displaystyle q^{'}(x_{2})=k_{2}}$

can be written in the symmetrical form

${\displaystyle q\ =\ (1-t)\ y_{1}+\ t\ y_{2}\ +\ t\ (1-t)\ (a\ (1-t)+b\ t)}$

(1)

where

${\displaystyle t={\frac {x-x_{1}}{x_{2}-x_{1}}}}$

(2)

and

${\displaystyle a=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})}$

(3)

${\displaystyle b=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})}$

(4)

Computing the derivatives one finds that

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

${\displaystyle q^{''}=2{\frac {b-2a+(a-b)3t}{{(x_{2}-x_{1})}^{2}}}}$

(6)

Setting ${\displaystyle x=x_{1}}$ and ${\displaystyle x=x_{2}}$ in (6) one gets that

${\displaystyle q^{''}(x_{1})=2{\frac {b-2a}{{(x_{2}-x_{1})}^{2}}}}$

(7)

${\displaystyle q^{''}(x_{2})=2{\frac {a-2b}{{(x_{2}-x_{1})}^{2}}}}$

(8)

If now

${\displaystyle (x_{i},y_{i})\quad i=0,1,\cdots ,n}$

are n+1 points and

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

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

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

${\displaystyle q_{i}^{'}(x_{i})=q_{i+1}^{'}(x_{i})}$

for ${\displaystyle i=1,\cdots ,n-1}$

then the n polynomials together define a derivable function in the interval ${\displaystyle x_{0}\leq x\leq x_{n}}$ and

${\displaystyle a_{i}=k_{i-1}(x_{i}-x_{i-1})-(y_{i}-y_{i-1})}$

(10)

${\displaystyle b_{i}=-k_{i}(x_{i}-x_{i-1})+(y_{i}-y_{i-1})}$

(11)

for ${\displaystyle i=1,\cdots ,n}$ where

${\displaystyle k_{0}=q_{1}^{'}(x_{0})}$

(12)

${\displaystyle k_{i}=q_{i}^{'}(x_{i})=q_{i+1}^{'}(x_{i})\quad i=1,\cdots ,n-1}$

(13)

${\displaystyle k_{n}=q_{n}^{'}(x_{n})}$

(14)

If the sequence ${\displaystyle k_{0},k_{1},\cdots ,k_{n}}$ is such that in addition

${\displaystyle q_{i}^{''}(x_{i})=q_{i+1}^{''}(x_{i})}$

for ${\displaystyle 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

${\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 ${\displaystyle i=1,\cdots ,n-1}$

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

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

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

${\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) together with (16) and (17) constitute n+1 linear equations that uniquely define the n+1 parameters ${\displaystyle k_{0},k_{1},\cdots ,k_{n}}$

Example:

In case of three points the values for ${\displaystyle k_{0},k_{1},k_{2}}$ are found by solving the linear equation system

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

${\displaystyle a_{11}={\frac {2}{x_{1}-x_{0}}}}$
${\displaystyle a_{12}={\frac {1}{x_{1}-x_{0}}}}$
${\displaystyle a_{21}={\frac {1}{x_{1}-x_{0}}}}$
${\displaystyle a_{22}=2\ \left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\right)}$
${\displaystyle a_{23}={\frac {1}{x_{2}-x_{1}}}}$
${\displaystyle a_{32}={\frac {1}{x_{2}-x_{1}}}}$
${\displaystyle a_{33}={\frac {2}{x_{2}-x_{1}}}}$
${\displaystyle b_{1}=3\ {\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{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)}$
${\displaystyle b_{3}=3\ {\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}}$

For the three points

${\displaystyle (-1,0.5)\ ,\ (0,0)\ ,\ (3,3)}$

one gets that

${\displaystyle k_{0}=-0.6875\ ,\ k_{1}=-0.1250\ ,\ k_{2}=1.5625}$

and from (10) and (11) that

${\displaystyle a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0.1875}$
${\displaystyle b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750}$
${\displaystyle a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750}$
${\displaystyle b_{2}=-k_{2}(x_{2}-x_{1})+(y_{2}-y_{1})=-1.6875}$

In the following figure the spline function consisting of the two cubic polynomials ${\displaystyle q_{1}(x)}$ and ${\displaystyle q_{2}(x)}$ given by (9) is displayed

Interpolation with cubic "natural" splines between three points.

Stamcose (talk) 11:20, 26 January 2011 (UTC)

I am not a pro when it comes to splines, but it seems to me that equation 17 is wrong when I compare it to equation 16. -Nic — Preceding unsigned comment added by 142.41.247.10 (talk) 20:52, 10 January 2013 (UTC)

## Completely wrong!

Section "Spline interpolant" says:

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.

But it is not the question of using a spline of degree n to interpolate n points, that would be nonsense! It is about using splines of degree 3 for which there are two additional degrees of freedom because there are n-1 linear equations! Using splines of degree 2 there is one additional degrees of freedom but spline interpolation with splines of degree 2 is anyway not really an option! But a radical re-write of the article is also for other reasons required!

Stamcose (talk) 10:21, 30 January 2011 (UTC)