1

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?

Neurax
  • 1,005
  • 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? – John Alexiou Dec 11 '13 at 16:27
  • @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. – Neurax Dec 11 '13 at 16:42
  • See http://www.physics.utah.edu/~detar/phys6720/handouts/cubic_spline/cubic_spline/node1.html – John Alexiou Dec 11 '13 at 19:19
  • 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). – bubba Dec 13 '13 at 06:58
  • 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. – bubba Dec 13 '13 at 09:54
  • @bubba I think I have an understanding of what you mean, but I'm not entirely sure. How do I adjust the equations that I'm using to Hermite form? and then what's the relationship that make the derivatives unknown. – Neurax Dec 16 '13 at 17:26

1 Answers1

4

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 endpoints, 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

The general equation for a cubic spline is an interpolation using the values $Y_i$ and the 2nd derivatives $Y''_i$ at each node. Once the 2nd derivatives are known, then the spline is solved for and the following equation can be used for interpolation between nodes $i$ and $i+1$.

This is done with a parameter $t=0\ldots 1$ that spans the interval

$$\begin{aligned} x_i & = X_i + t\,h \\ y_i & = (1-t) Y_i + y\,Y_{i+1} + \tfrac{h^2}{6} \left( (1-t) (t^2-2 t) Y''_i + t (t^2-1) Y''_{i+1} \right) \end{aligned} $$

The system of equations to find a spline is formed using the following procedure:

  • Start Point Either the spline in a natural spline with $Y''_1 = 0$ or it has a specified slope $Y'_1$ at which point the following equation must be used

    $$ Y''_2 + 2 Y''_1 = \tfrac{6}{h^2} \left( Y_2 - Y_1 - h Y'_1 \right) \tag{i = 1}$$

  • Internal Points Here the slope needs to match at nodes and this is ensured with the following equation for $i=2 \ldots n-1$

    $$ Y''_{i-1} + Y''_{i+1} + 4 Y''_i = \tfrac{6}{h^2} \left( Y_{i-1} + Y_{i+1} - 2 Y_i \right) \tag{i = 2 to n-1}$$

  • End Point Again the spline is either natural with $Y''_n = 0$ or with the specified slope $Y'_n$, and the following equation must be used.

    $$ Y''_{n-1} +2 Y''_n = \tfrac{6}{h^2} \left( Y_{n-1} - Y_n + h Y'_n \right) \tag{i = n}$$

For your example, I assume you want a natural spline so only the interior points are considered, resulting in these two equations

$$\begin{aligned} 4 Y''_2 + Y''_3 & = \tfrac{6}{h^2} \left( Y_3 - 2 Y_2 + Y_1 \right) \\ Y''_2 + 4 Y''_3 & = \tfrac{6}{h^2} \left( Y_4 - 2 Y_3 + Y_1 \right) \end{aligned}$$

Using $h=1$ and $Y=[0,2,1,0]$ and solved for $Y''_2$ and $Y''_3$.

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

John Alexiou
  • 13,816
  • 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? – Neurax Dec 12 '13 at 02:04
  • 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. – John Alexiou Dec 13 '13 at 01:32
  • Ok, I have added the details on what the equations look like. – John Alexiou Dec 13 '13 at 02:09
  • @JohnAlexiou sorry, but can you explain how did u get $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)$ . – kebiri5 Oct 20 '21 at 11:41
  • 1
    @kebiri5 - The $C_i$ and $D_i$ are not the same as above it. They are new coefficients, which only contribute between an interval, and not at the nodes. This post was 9 years ago, and now I have an easier way to develop the equations. – John Alexiou Oct 20 '21 at 12:33
  • @JohnAlexiou thank you !! – kebiri5 Oct 20 '21 at 12:38