Talk:Spline interpolation/Archive 1

Archive 1

Definition

i have some questions about this phrase:

Given n+1 distinct knots x_i such that

$x_{0}<x_{1}<...<x_{n-1}<x_{n},\,\!$

with n+1 knot values y_i 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_{k-1}(x)&x\in [x_{k-1},x_{k}]\end{matrix}}\right.$

with each S_i(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 $z_{i}$ by $6z_{i}$, enabling one to cancel 6s and obtain

$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

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

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:

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.

There seems to be no link or explanation remaining about quadratic splines. Those seem pretty important. — Preceding unsigned comment added by 2603:8000:D100:9226:E016:6348:4EBB:6B71 (talk) 17:32, 12 April 2024 (UTC)

—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

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

over the functions in the Sobolev space $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?

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

$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

This article has together with Spline (mathematics) been given the tag

{{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" $(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 $q''_{i}(x_{i})=q''_{i+1}(x_{i})$ for all i , $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 $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)

Computing the derivatives one finds 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 (6) one gets 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}\leq x<x_{i}\leq$, 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 derivable function in the interval $x_{0}\leq x\leq 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}$

Example:

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

with

$a_{11}={\frac {2}{x_{1}-x_{0}}}$

$a_{12}={\frac {1}{x_{1}-x_{0}}}$

$a_{21}={\frac {1}{x_{1}-x_{0}}}$

$a_{22}=2\ \left({\frac {1}{x_{1}-x_{0}}}+{\frac {1}{x_{2}-x_{1}}}\right)$

$a_{23}={\frac {1}{x_{2}-x_{1}}}$

$a_{32}={\frac {1}{x_{2}-x_{1}}}$

$a_{33}={\frac {2}{x_{2}-x_{1}}}$

$b_{1}=3\ {\frac {y_{1}-y_{0}}{(x_{1}-x_{0})^{2}}}$

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

$b_{3}=3\ {\frac {y_{2}-y_{1}}{(x_{2}-x_{1})^{2}}}$

For the three points

$(-1,0.5)\ ,\ (0,0)\ ,\ (3,3)$

one gets that

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

and from (10) and (11) that

$a_{1}=k_{0}(x_{1}-x_{0})-(y_{1}-y_{0})=-0.1875$

$b_{1}=-k_{1}(x_{1}-x_{0})+(y_{1}-y_{0})=-0.3750$

$a_{2}=k_{1}(x_{2}-x_{1})-(y_{2}-y_{1})=-3.3750$

$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 $q_{1}(x)$ and $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)

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)

External Links

I added the external link to my free Web e-book. It is a more complete treatment of piecewise interpolation for those new to the subject and aimed at graphics. I'll add references to other related Wiki pages in the future.

My e-book is both a study of the fundamentals described in simple terms as well as a reference showing many types of Polynomial Interpolation -both common types and some developed by the author. It also shows some techniques not seen elsewhere. Linear interpolation is looked at carefully and shown is as the basis for all more advanced types using only Algebra. Only after understanding how adding squared and cubed terms cause smooth curves, are the more advanced curves examined such as Bezier, Catmul-Rom, b-spline, and Hermite. More advanced mathematical concepts and notations are kept to a minimum. Some additional techniques that are suggested by the mathematics and that the author has not seen elsewhere are examined. A reference is also included with all the most common curve drawing methods and includes drawings to allow comparison with other types.

WHY: I had hoped, but failed to find a book explaining polynomial interpolation basics and thought that one must certainly exist with a collection of interpolation types. I found either purely mathematical tests or advanced graphics texts. Several years later, I started reading the original Internet Usenet "groups", comp.graphics.algorithms, and did lots of searching on the net. I saved whatever I found related to splines and curves, but did not look at it or try to understand any of it until early in 1996, I decided to look at what I had collected, and started to figure things out. I begin recording my thoughts for future reference and this is the result. The very book I wanted originally is now freely available for others.

I do not believe this has any issues with the Wiki self cite guidelines. -- Steve -- (talk) 22:53, 28 August 2011 (UTC)

Regression to the highest common demoninator

See this [2] permalink for a useful 'Algorithm for computing natural cubic splines'. The current 'Algorithm to find the interpolating cubic spline' is absolutely perfect and utterly useless. Doug (talk) 19:51, 28 March 2012 (UTC)

Consider using matrix to describe the conclusion

I mean write the tridiagonal matrix at the end of the description of algorithm. — Preceding unsigned comment added by 137.132.3.10 (talk) 05:22, 22 March 2014 (UTC)