1
$\begingroup$

Going over practice problems for our final exam. I'm stuck on a problem involving cubic splines. In fact, I don't even know where to begin.

I need to find the natural cubic spline $S(t)$ at $t_0=0, t_1=1, t_2=2, t_3=3$ where $$S(t_0)=0\\ S(t_1)=2\\ S(t_2)=1\\ S(t_3)=0$$

As @ja72 has pointed out, there are 3 intervals, thus 3 splines. There are conditions we impose on these splines so that we get the desired curve.

$$ \begin{align} S_1(t_0) &= 0\\ S_1(t_1) &= 2\\ S_2(t_2) &= 1\\ S_3(t_3) &= 0\\ S_1(t_1) &= S_2(t_1)\\ S_2(t_2) &= S_3(t_2)\\ S_1'(t_1) &= S_2'(t_1)\\ S_2'(t_2) &= S_3'(t_2)\\ S_1''(t_1) &= S_2''(t_1)\\ S_2''(t_2) &= S_3''(t_2)\\ S_1''(t_0) &= 0\\ S_3''(t_3) &= 0 \end{align} $$

Now, I can plug in the exact $t_j$ values and $S_i(t_j)$ values directly into these 12 equations and should wind up with a linear system, 12 coeffs (4 from each spline).

So I went ahead and plugged all of the $t$ values into the condition equations. I was left with a 12 x 12 matrix. I used MatLab to solve the system and got the coefficients that @ja72 got in their final solution. My professor said we'll have to solve the matrices by hand. What is the best way to solve a 12 x 12 matrix this way?

$\endgroup$
  • $\begingroup$ Don't you have a book on the subject? The details are very involved, but the concept is simple. What level of detail are you looking for? $\endgroup$ – ja72 Dec 11 '13 at 16:27
  • $\begingroup$ @ja72, yes I have a book. It's written in such a manner that is very difficult to understand. I've tried to use other books and the wiki page. I started by graphing the points and trying to inspect a curve that might fit to my graph. I don't necessarily need a full detailed answer, but some points on how to derive an answer from the information given. $\endgroup$ – Neurax Dec 11 '13 at 16:42
  • $\begingroup$ See physics.utah.edu/~detar/phys6720/handouts/cubic_spline/… $\endgroup$ – ja72 Dec 11 '13 at 19:19
  • $\begingroup$ It's pretty silly to try to solve a general system of 12 linear equations "by hand". You'd spend a very long time working through all the calculations, and you wouldn't learn very much from the experience. Maybe your teacher's point is this ... if you write out those 12 equations you will see that the system is banded -- in other words, each equation has only a few non-zero coefficients. By writing the equations in the right order, you get a matrix that only has non-zero entries in a "band" near the main diagonal. Systems like this can be solved by hand (though it's still tedious). $\endgroup$ – bubba Dec 13 '13 at 6:58
  • $\begingroup$ Another comment. The usual way to compute splines (in my experience) is to write each cubic segment in Hermite form, using the positions and derivatives at each end of the segment. If you do that, the derivatives are the unknowns. So, in your example, there will only be 4 unknowns, not 12. That helps a lot. $\endgroup$ – bubba Dec 13 '13 at 9:54
3
$\begingroup$

Typically a cubic spline is given for a set of points such that for each interval a cubic function is fitted to the points, with matching slopes and curvature, as well as the end points have zero curvature (2nd derivative). This is the definition of a natural spline.

In your case you have 4 points and 3 intervals. The number of unknowns is 12, as for each interval there are 4 unknowns (the cubic part).

Your constraints are:

  • Points on given nodes (4 equations)
  • Interval end points match (2 equations)
  • Interval end slopes match (2 equations)
  • Interval end curvature match (2 equations)
  • End point cuvature zero (2 equations)

In total you have 12 equations with 12 unknowns.

See http://www.physics.utah.edu/~detar/phys6720/handouts/cubic_spline/cubic_spline/node1.html for more details. Also wikipedia has a nice write-up.

For your case the solution is

$$ y(x)=\begin{cases} \frac{2x(7-2x^{2})}{5} & x=0\ldots1\\ \frac{5x^{3}-27x^{2}+41x-9}{5} & x=1\ldots2\\ \frac{-x^{3}+9x^{2}-31x+39}{5} & x=2\ldots3 \end{cases} $$

Details

To find the splines, for each interval you have a function like

$$ y_i(x) = y_i + B_i (x-x_i) + C_i (x-x_i)^2 + D_i (x-x_i)^3 $$

where $(x_i,y_i)$ are the coordinate pairs the spline. Actually, if you define the next pair as $(x_i+h,y_{i+1})$ where $h=x_{i+1}-x_i$ then

$$ y_i(x) = y_i + \frac{y_{i+1}-y_i}{h} (x-x_i) + C_i (x-x_i) (x-x_i-h) + D_i (x-x_i) \left((x-x_i)^2-h^2\right) $$ which of course has $y(x_{i+1}=x_i+h) = y_{i+1}$

This leads to the expressions

$$ y'(x) = \frac{y_{i+1}-y_i}{h} + C_i \left( 2 (x-x_i)-h\right) +D_i \left( 3 (x-x_i)^2-h^2 \right) \\ y''(x) = 2 C_i + 6 D_i (x-x_i) $$

Now at the end-points of the $i$th interval

$$ \begin{aligned} {y'}_i & = \frac{y_{i+1}-y_i}{h} - C_i h - D_i h^2 & {y'}_{i+1} &= \frac{y_{i+1}-y_i}{h} + C_i h + 2 D_i h^2 \\ {y''}_i & = 2 C_i & {y''}_{i+1} & = 2 C_i + 6 D_i h \end{aligned} $$

Our curves already pass through the points, and constraints need to be developed for continuity.

A natural spline has the first and last point with zero curvature. If there are $n+1$ points, with $n$ intervals, then the ends points have

$$ \begin{aligned} 2 C_1 & = 0 & 2 C_n + 6 D_n h & = 0 \end{aligned} $$

Between each interval with $i=2\ldots n$ the slope and curvature match are

$$ \begin{aligned} \frac{y_i-y_{i-1}}{h} + C_{i-1} h + 2 D_{i-1} h^2 &= \frac{y_{i+1}-y_i}{h} - C_i h - D_i h^2 \\ 2 C_{i-1} + 6 D_{i-1} h & = 2 C_i \end{aligned} $$

These are $2 + 2 (n-1) = 2 n$ equations and there are $n$ unknowns of $C_i$ and $n$ unknowns of $D_i$ for a total of $2n$ unknowns. The problem is well defined at this point and solvable. Someone please check my math because I might have made a mistake somewhere.

NOTE: I have assumed constant interval with $h = x_{i}-x_{i-1}$, but that above can be adapted to a varying grid also.

$\endgroup$
  • $\begingroup$ Okay, @ja72 this all looks like it makes sense. I see the difference between the answer above and your response. You are correct that the Natural Cubic Spline is whats desired. You say that there's 12 equations, what do they look like? Is it a system I can solve using other methods? $\endgroup$ – Neurax Dec 12 '13 at 2:04
  • $\begingroup$ If you have access to a computer programming environment there are numerous cubic spline routines available. If you want to solve by hand, then be ready for some fun algebra. $\endgroup$ – ja72 Dec 13 '13 at 1:32
  • $\begingroup$ Ok, I have added the details on what the equations look like. $\endgroup$ – ja72 Dec 13 '13 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.