How Do You Set Up Matrices for Cubic Spline Interpolation?

[gfd43tg]

Hello,

I am trying to understand the slides in the PDF I posted. I am looking particularly at slides 20-24. I am so confused how the matrices are set up with two separate coefficient conditions. The context of these slides is that we are learning how to interpolate with cubic splines.

What is going on with these slides? The professor is incomprehensible to me in the lecture videos due to being overly mathematically rigourous, so I can't figure out what is happening. It's like he is putting a matrix within a matrix. How am I supposed to do that multiplication? Is it like the matrix within the matrix times each vector, or an element of the vector within the inner matrix? So confused...

And how is that going to help me with doing cubic polynomial fits within the context of an interpolation?

 

[SteamKing]

Hello,

I am trying to understand the slides in the PDF I posted. I am looking particularly at slides 20-24. I am so confused how the matrices are set up with two separate coefficient conditions. The context of these slides is that we are learning how to interpolate with cubic splines.

What is going on with these slides? The professor is incomprehensible to me in the lecture videos due to being overly mathematically rigourous, so I can't figure out what is happening. It's like he is putting a matrix within a matrix. How am I supposed to do that multiplication? Is it like the matrix within the matrix times each vector, or an element of the vector within the inner matrix? So confused...

And how is that going to help me with doing cubic polynomial fits within the context of an interpolation?

Your professor may be overly mathematically rigorous, or he could be completely disorganized; it's hard to tell from the slide presentation. There's probably a lecture which goes along with these slides.

However, the subject matter at hand need not be cast in a form only savants can understand.

This article explains the subject in a clearer fashion without an extra helping of gobbledegook to impress and awe the undergrads:

http://online.redwoods.edu/instruct/darnold/laproj/fall98/skymeg/proj.pdf

PF also has a Math Learning Material forum:

https://www.physicsforums.com/forumdisplay.php?f=178

from which the following article on the math of cubic splines was obtained:

https://www.physicsforums.com/attachment.php?attachmentid=16883&d=1229560291

 

[AlephZero]

Your professor may be overly mathematically rigorous, or he could be completely disorganized; it's hard to tell from the slide presentation. There's probably a lecture which goes along with these slides.

However, the subject matter at hand need not be cast in a form only savants can understand.

This article explains the subject in a clearer fashion without an extra helping of gobbledegook to impress and awe the undergrads:

I don't see any of the those "anti-math" criticisms looking at the PDF. It looks about the usual level for presenting that sort of algorithm in matrix form.

A good way to figure out what is going in these situations is to write out a simple case with one or two spline segments in full - and that's what the PF link seems to do. But the learning comes from going through the process yourself, not just looking at a page of equations that somebody on PF wrote out earlier.

If one of the exercises in your course is to program this yourself in Matlab, then doing it using partitions of matrices will be much neater than setting up the equations one term at a time. (Of course the purpose of writing your own code for this is to learn Matlab programming - if you just want to do spline fitting, use the functions that are in Matlab already).

 

[SteamKing]

The point is, if you don't understand one person's presentation of the material, don't let that impede your progress. The web is full of alternate presentations of cubic spline interpolation. One of these is bound to click with the OP, but a lot of people will not take the time to look. That is something I personally don't understand.

 

[AlephZero]

The point is, if you don't understand one person's presentation of the material, don't let that impede your progress.

Agreed, but the OP also needs to learn how to understand the way the material is presented on the slides. Over the years, I've accumulated a shelf full of books and copies of papers on computational methods etc that are written using that type of notation.

 

[SteamKing]

That's why I made the comment that there was probably a lecture which accompanied the slides. Not every slideshow is a standalone presentation.

 

[gfd43tg]

Yeah, there are videos that go with these slides. It's just him talking really fast and repeating the words on the slides. Thanks for the resources, I need a more ''gentle'' approach to the problem before jumping right into this. It is kind of over my head. I watched some videos on youtube explaining splines, but when I went back to the lecture videos, I couldn't make the connection between the two. They were like two completely different animals.

This was the video I watched
https://www.youtube.com/watch?v=BJc0bQNRSo4

 

[gfd43tg]

I am confused at equation 15 in the redwoods PDF you uploaded. Why is it once they get to the 2nd derivative, they begin checking $s''_{i}(x_{i}) = s''_{i+1}(x_{i})$. For the other two comparisons, it was always evaluated at $i-1$ and $i$, but all the sudden it changes to a comparison of $i+1$ and $i$ as the subscripts. For the function and its first derivative, where the comparison is that $s_{i-1}(x_{i}) = s_{i}(x_{i})$ and $s'_{i-1}(x_{i}) = s'_{i}(x_{i})$ where $i = 2,3,\dots,n-1$.

As an example, for $i=1$, how could you even evaluate $s''_{i+2}(x_{1})$? That spline doesn't even touch the first point. I uploaded my work to show you what I mean.

Wouldn't the equality rather be $s''_{i}(x_{i}) = s''_{i-1}(x_{i})$ for $i = 2,3,\dots,n-1$??

At equation 15 and 16 that's where I start not believing what this PDF is saying.

In equation 16,
$s''_{i+1}(x_{i+1}) = 6a_{i+1}(x_{i+1}-x_{i}) + 2b_{i}$ doesn't make sense to me. The way that they have been doing it, it seems to me that the convention is as follows

$s''_{A}(x_{B}) = 6a_{A}(x_{B}-x_{A}) + 2b_{A}$

In the PF tutorial, I wish they did this part
because they say ''Also, if the above expression for y is expanded and terms collected, it is easy to show that:''
$a = a'$
$b = b' – 3a'x_{0}$
$c = c' + 3a'x_{0}^2 – 2b'x_{0}$
$d = d' – c'x_{0} + b'x_{0}^2 – a'x_{0}^3$

I expanded the equation
$y = a'(x-x_{0})^3 + b'(x-x_{0})^2 + c'(x-x_{0}) + d'$

and got
y = a'(x^3 - 3x^2x_{0} + 3xx_{0}^2 - x_{0}^3) + b'(x^2 - 2xx_{0} + x_{0}^2) + c'(x-x_{0}) + d'
y = a'x^3 - 3a'x^2x_{0} + 3a'xx_{0}^2 - 3a'x_{0}^3 + b'x^2 - 2xx_{0}b' + b'x_{0}^2 + c'x - c'x_{0} + d'

and I don't see how they group anything to call a, b, c, and d. Those aren't even in the equation for y.

 

[gfd43tg]

I also can't figure out the part where they say

$y'' = (x-x{1})(y_{2}''-y_{1}'')/(x_{2}-x_{1}) + y_{1}''$ in the development of splines section of the PF tutorial. I wish algebra steps weren't skipped, because I don't know how to get that result.

Also, my lecture slides and those 2 sources all use different notation and different approaches to solving this thing, so they all have some compatibility, but I can't piece them all together. I can understand aspects of certain presentations, then I get stuck and go to the other source and fill in some of that void. But no cohesive source where I can follow all the way through for this stupid spline interpolation.

 

[AlephZero]

Why is it once they get to the 2nd derivative, they begin checking $s''_{i}(x_{i}) = s''_{i+1}(x_{i})$.

I think that's a typo. It should be $s''_{i}(x_{i+1}) = s''_{i+1}(x_{i+1})$ for $i = 1, \dots, n-1$.

Or, similar to equations 7 and 11, $s''_i(x_i)=s''_{i-1}(x_i)$ for $i = 2, \dots, n$.

 

[AlephZero]

I also can't figure out the part where they say

$y'' = (x-x{1})(y_{2}''-y_{1}'')/(x_{2}-x_{1}) + y_{1}''$ in the development of splines section of the PF tutorial. I wish algebra steps weren't skipped, because I don't know how to get that result.

$y$ is a cubic function of $x$, so $y''$ is a linear function. (You can see that from the expressions for $y$, $y'$, and $y''$ for splines #1 and #2).

So going back to somewhere in high school math, the equation of a line with slope $m$ through a point $(x_1, y_1)$ is $y = m(x - x_1) + y_1$. Also, if you know two points $(x_1, y_1)$ and $(x_2, y_2)$ on a line, the slope is $m = \dfrac{ y_2 - y_1}{x_2 - x_1}$.

Now you should be able to see where the equation comes from. The equation of the "line" for the 2nd derivative goes through $(x_1, y''_1)$ and its slope is $\dfrac { y''_2 - y''_1 } { x_2 - x_1}$.

I agree that is not very obvious, compared with the amount of detail in the rest of the PF document.

 

[AlephZero]

In the PF tutorial, I wish they did this part
because they say ''Also, if the above expression for y is expanded and terms collected, it is easy to show that:''
$a = a'$
$b = b' – 3a'x_{0}$
$c = c' + 3a'x_{0}^2 – 2b'x_{0}$
$d = d' – c'x_{0} + b'x_{0}^2 – a'x_{0}^3$

Which document is that from?

 

[gfd43tg]

The PF tutorial

 

[AlephZero]

OK, I found it now.

Read the whole paragraph starting "Alternate Cubic Polynomial formulation".

The "previous case" is from the first section, $y = ax^3 + bx^2 + cx + d$.
The "more general form" is $y = a'(x-x_0)^3 + b'(x-x_0)^2 + c'(x-x_0) + d'$.

If you equate the coefficients of the powers of $x$, you get the equations given.