Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Recently, I was reading about a "Natural Piecewise Hermite Spline" in Game Programming Gems 5 (under the Spline-Based Time Control for Animation). This particular spline is used for generating a C2 Hermite spline to fit some given data. I kinda understand how natural cubic spline interpolation works (ie: setup a tridiagonal matrix, solve Ax=b where x is the vector of 2nd derivatives). However, I don't quite understand how this book calculates the slopes for a spline.

Here's what their system of equations looks like: $$ \begin{multline} \begin{bmatrix} 2 & 1 & 0 &\ldots & 0\\ \Delta t_0 & 2(\Delta t_0 + \Delta t_1) & \Delta t_1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & \ldots & \Delta t_{n-2} & 2(\Delta t_{n-2} + \Delta t_{n-1}) & \Delta t_{n-1} \\ 0 & \ldots & 0 & 1 & 2 \end{bmatrix} \begin{bmatrix} y{\prime}_0 \\ y{\prime}_1\\ \vdots\\ y{\prime}_{n-1}\\ y{\prime}_n \end{bmatrix} = \\ \begin{bmatrix} \frac{3}{\Delta t_0}(y_1-y_0)\\ \frac{3}{\Delta t_0 \Delta t_1}[\Delta t_0^{2} (y_2-y_1) + \Delta t_1^{2} (y_1-y_0)] \\ \vdots \\ \frac{3}{\Delta t_{n-2} \Delta t_{n-1}}[\Delta t_{n-2}^{2} (y_n-y_{n-1}) + \Delta t_{n-1}^{2} (y_{n-1}-y_{n-2})] \\ \frac{3}{\Delta t_{n-1}}(y_n-y_{n-1}) \end{bmatrix} \end{multline} $$

given data input $(x_i,y_i)$ where $ \Delta t_i = x_{i+1}-x_i$.

What confuses me is that normally the unknown is a set of 2nd derivatives, but here, they're solving for the first derivatives. The tridiagonal that I've normally seen for natural splines also has the first row equal to $\begin{bmatrix} 1, & 0, & \ldots \end{bmatrix}$ and the last equal to $\begin{bmatrix} 0, & \ldots, & 1\end{bmatrix}$.

Does anyone understand how this equation might've been derived? Additionally, is there much advantage to using a natural piecewise Hermite with C2 continuity over just a cubic spline? I could find next to nothing online piecewise Hermite curves with C2.

Thanks.

PS: I'm not a math guru, so apologies if my wording or equations seem off.

share|improve this question
    
P.S. Nowadays, it's usually a better idea to use "not-a-knot" conditions instead of the "natural" conditions. –  J. M. Sep 7 '11 at 6:19
    
I only used "natural" since that just simplified the conditions for demonstrating my problem. I will take note of using "not-a-knot", though. –  lhumongous Sep 8 '11 at 18:16
add comment

1 Answer

up vote 4 down vote accepted

A $C^2$ piecewise Hermite interpolant and a cubic spline are one and the same!

Remember what's done to derive the tridiagonal system: we require that at a joining point, the second left derivative and the second right derivative should be equal.

To that end, consider the usual form of a cubic Hermite interpolant over the interval $(x_i,x_{i+1})$:

$$y_i+y_i^{\prime}\left(x-x_i\right)+c_i\left(x-x_i\right)^2+d_i\left(x-x_i\right)^3$$

where

$$\begin{align*}c_i&=\frac{3s_i-2y_i^\prime-y_{i+1}^\prime}{x_{i+1}-x_i}\\ d_i&=\frac{y_i^\prime+y_{i+1}^\prime-2s_i}{\left(x_{i+1}-x_i\right)^2}\\ s_i&=\frac{y_{i+1}-y_i}{x_{i+1}-x_i}\end{align*}$$

and $\{y_i^\prime,y_{i+1}^\prime\}$ are the slopes (derivative values) of your interpolant at the corresponding points $(x_i,y_i)$, $(x_{i+1},y_{i+1})$.

Take the second derivative of the interpolant over $(x_{i-1},x_i)$ evaluated at $x=x_i$ and the second derivative of the interpolant over $(x_i,x_{i+1})$ evaluated at $x=x_i$ and equate them to yield (letting $h_i=x_{i+1}-x_i$):

$$c_{i-1}-c_i+3d_{i-1}h_{i-1}=0$$

Replacing $c$ and $d$ with their explicit expressions and rearranging yields:

$$h_i y_{i-1}^{\prime}+2(h_{i-1}+h_i)y_i^{\prime}+h_{i-1} y_{i+1}^{\prime}=3(h_i s_{i-1}+h_{i-1} s_i)$$

which can be shown to be equivalent to one of the equations of your tridiagonal system when $h$ and $s$ are replaced with expressions in terms of $x$ and $y$.

Of course, one could instead consider the cubic interpolant in the following form:

$$y_i+\beta_i\left(x-x_i\right)+\frac{y_i^{\prime\prime}}{2}\left(x-x_i\right)^2+\delta_i\left(x-x_i\right)^3$$

where

$$\begin{align*}\beta_i&=s_i-\frac{h_i(2y_i^{\prime\prime}+y_{i+1}^{\prime\prime})}{6}\\\delta_i&=\frac{y_{i+1}^{\prime\prime}-y_i^{\prime\prime}}{6h_i}\end{align*}$$

Doing a similar operation as was done for the Hermite interpolant to this form (except here, one equates first derivatives instead of second derivatives) yields

$$h_{i-1} y_{i-1}^{\prime\prime}+2(h_{i-1}+h_i)y_i^{\prime\prime}+h_i y_{i+1}^{\prime\prime}=6(s_i-s_{i-1})$$

which may be the form you're accustomed to.


To complete this answer, let's consider the boundary condition of the "natural" spline, $y_1^{\prime\prime}=0$ (and similarly for the other end): for the formulation where you solve the tridiagonal for the second derivatives, the replacement is straightforward.

For the Hermite case, one needs a bit of work to impose this condition for the second derivative. Taking the second derivative of the interpolant at $(x_1,x_2)$ evaluated at $x_1$ and equating that to 0 yields the condition $c_1=0$; this expands to

$$\frac{3s_1-2y_1^\prime-y_2^\prime}{x_2-x_1}=0$$

which simplifies to

$$2y_1^\prime+y_2^\prime=3s_1$$

which is the first equation in the tridiagonal system you gave. (The derivation for the other end is similar.)

share|improve this answer
    
Thanks! It took me a while, but I think I understand how the math works now. Glad to know that C2 Hermite == Cubic; that clears things up a lot. I also suspect that the matrix from the Gems book might have an incorrect tridiagonal. If I were to swap the sub/super diags for every row (except the ends), I get sensible slopes. In its current form, the slopes seem a little screwy when I plot the interpolated data. –  lhumongous Sep 8 '11 at 18:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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