Natural cubic splines vs. Piecewise Hermite Splines

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.

Solution 1:

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.)