Talk:Spline interpolation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer graphics (Rated Start-class)
WikiProject icon 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-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

Where is equation 2?[edit]

Where is equation 2?

Interpolation using natural cubic spline[edit]

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

i have some questions about this phrase:

Given n+1 distinct knots xi such that
x_0 < x_1 < ... < 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_{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[edit]

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

In the formulas for interpolation using natural cubic spline, it seems that one could replace each z_i by 6 z_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[edit]

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

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

Quadraticspline jaredwf.png


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

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

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

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

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 \le i \le 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[edit]

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} \le x<x_i \le , 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 \le x \le 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![edit]

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)

External Links[edit]

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

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

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)


Terrible article[edit]

This article shows everything that is wrong with mathematical articles on Wikipedia. First, it has a short, semi-technical introduction that doesn't really give a good introduction to subject. Then it dives headfirst into a very long winded page of math, with an "algorithm" that provides little clarity on what the spline does. To me, an algorithm should provide enough clarity to code something. You basically have to know what ordinary differential equations are just to start. Finally it has an example that is just as technical as the "algorithm". If you can understand anything on this page, you probably already know what spline interpolation is anyway, rendering it pointless to the target audience.

If you ask me Wikipedia is not an appropriate place for mathematical proofs, which are generally not of interest to non-mathematicians. And I also think it is also not the place for algorithms - this is where external links should come into place. It would be much better if a lay explanation of what spline interpolation is used for, why it is important, and the history behind how it came to be derived. 153.176.151.122 (talk) 10:21, 18 March 2015 (UTC)