Hermite Splines (Interpolation, part III)

In previous posts, we discussed linear and cubic interpolation. So let us continue where we left the last entry: Cubic interpolation does not guaranty that neighboring patches join with the same derivative and that may introduce unwanted artifacts.

Well, the importance of those artifacts may vary; but we seem to be rather sensitive to curves that change too abruptly, or in unexpected ways. One way to ensure that cubic patches meet gracefully is to add the constraints that the derivative should be equal on both side of a joint. Hermite splines do just that.

The system of equation for a cubic polynomial has four equations and four unknowns, all concerned with fitting the four support points (read back the last entry in the series, if need be). But Hermite splines will have some of the equations to describe derivatives, i.e., the slope at the end points.

A cubic polynomial is given by

$ax^3+bx^2+cx+d$

and its derivative relative to $x$ by

$3ax^2+2bx+c$

So we rewrite the cubic equation system by replacing the last two equations by the derivatives, which will constrain the solution:

$\left[\begin{array}{cccc}x_{i}^3 & x_{i}^2 & x_{i} & 1\\x_{i+1}^3 & x_{i+1}^2 & x_{i+1} & 1\\3x_{i}^2 & 2x_{i} & 1 & 0\\3x_{i+1}^2 & 2x_{i+1} & 1 & 0\end{array}\right]\left[\begin{array}{c} a\\ b\\ c\\ d\end{array}\right]=\left[\begin{array}{c} y_{i}\\ y_{i+1}\\ y_{i}^\prime\\ y_{i+1}^\prime\end{array}\right]$

where $y_{i}^\prime$ and $y_{i+1}^\prime$ are the wanted derivatives at $y_i$ and $y_{i+1}$ , respectively. We then solve for $\left[~a~b~c~d~\right]$ . Again, with special cases $x_i=0$ and $x_{i+1}=1$ , the system simplifies a lot:

$M=\left[\begin{array}{cccc}0 & 0 & 0 & 1\\1 & 1 & 1 & 1\\ 0 & 0 & 1 & 0\\3 & 2 & 1 & 0\end{array}\right]$ ,

and the inverse is:

$M^{-1}=\left[\begin{array}{cccc}2 & -2 & 1 & 1\\-3 & 3 & -2 & -1\\ 0 & 0 & 1 & 0\\1 & 0 & 0 & 0\end{array}\right]$ ,

and we solve, finally, with

$\left[\begin{array}{c} a\\ b\\ c\\ d\end{array}\right]=M^{-1}~\left[\begin{array}{c} y_{i}\\ y_{i+1}\\ y_{i}^\prime\\ y_{i+1}^\prime\end{array}\right]$

*
* *

Now remains to decide how we choose $y_{i}^\prime$ and $y_{i+1}^\prime$ , the derivatives at $y_i$ and $y_{i+1}$ , respectively. One way is to set them as zero, so that each point is surrounded by a flat region, but that doesn’t seem to have all the naturalness one could want.

One other way, is to look at the neighbors, a bit further, $(x_{i-1},y_{i-1})$ and $(x_{i+2},y_{i+2})$ , and guess sensible slopes. That’s what cardinal splines do, and quite simply, at that.

To be continued…

This entry was posted on Tuesday, June 12th, 2012 at 9:44 am and is filed under algorithms, Mathematics, programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

3 Responses to Hermite Splines (Interpolation, part III)

Cubic Interpolation (Interpolation, part II) « Harder, Better, Faster, Stronger says:

12/06/2012 at 9:44 am

[…] Hermite Splines (Interpolation, part III) […]

Reply
Cardinal Splines (Interpolation, part IV) « Harder, Better, Faster, Stronger says:

26/06/2012 at 10:24 am

[…] the last installment of this series, we left off Hermite splines asking how we should choose the derivatives at end […]

Reply
Fast Interpolation (Interpolation, part V) « Harder, Better, Faster, Stronger says:

03/07/2012 at 9:29 am

[…] the last four installments of this series, we have seen linear interpolation, cubic interpolation, Hermite […]

Reply

Harder, Better, Faster, Stronger