In a previous entry, we had a look at linear interpolation and concluded that we should prefer some kind of smooth interpolation, maybe a polynomial.

However, we must use a polynomial of sufficient degree so that neighboring patches do not exhibit very different slopes on either side of known points. This pretty much rules out quadratic polynomials, because polynomials of the form are only capable of expressing (strictly) convex (or concave) patches. A quadratic piece-wise function would look something like:

Here, the solid lines represent the part of the patch used for interpolation, while the dashed line show the extent of the quadratic patch. We see that this yields a saw-tooth pattern, clearly something we do not want for “smooth” interpolation.

Since a cubic polynomial is capable of (slightly more) expressiveness, namely it can have two bumps (in opposing directions), and uses four points (instead of just three as with the quadratic patches), it captures possibly better the oscillations in the (unknown) underlying function. On the same points, maybe cubic patches would yield the following interpolation:

Maybe the slope doesn’t quite match on either side of the points, but at least, it doesn’t change as wildly than the quadratic patches.

Let again be a series of known points between which we wish to interpolate. So between any two points and , we will use a cubic polynomial to interpolate. However, a degree polynomial needs points to be uniquely defined (that’s the *unisolvence theorem*), and we will need, in addition to and , the points and . We need to find the parameters to the equation

that passes through *all* four points. That gives us four equations, four unknowns that we must solve:

But writing equations this way is cumbersome, and not propitious to fast and efficient solution. Noticing that

can be rewritten as

That is, as a dot product. We can rewrite the four equations as a matrix/vector system of the form :

and we solve for . Fortunately, it’s not too hard:

Matrix inverses are really painful to compute in general (not even when using pen-and-paper computation) but if we have the special case where , , , and , then the matrix simplifies to

with the inverse

and solving for the parameters are obtained by

*

* *

We can compute the product in much less than (scalar) products. First, some entries are zero, are are and therefore reduce to simple addition/subtraction; then we notice that some are similar except for sign. With constant folding, we can get something efficient.

*

* *

So we have a rather efficient way of fitting a cubic through four points, but the cubic patches still do not quite fit together as nicely as they should. In particular, the derivative around is not the same whether we consider the patch interpolating between and and the patch interpolating between and . So how do we force them to match?

Well, we can add the constraints explicitly in the equation system and solve for different parameters. One simple way of doing so is to use the Hermite splines.

[…] To be continued… Share this:StumbleUponDiggRedditTwitterMoreFacebookEmailLike this:LikeBe the first to like this post. […]

[…] previous posts, we discussed linear and cubic interpolation. So let us continue where we left the last entry: […]

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