Spline Interpolation and cubic interpolation

Hi

How many data points does Spline and Cubic interpolation take to
calculate a point?

for 3rd order polynomial interpolation, it's usually 4 data points (and
you're interpolating between the inner two data points).  there are
many different interpolation polynomials, even for a given order (such
as 3).

Lagrange interpolation will fit an Nth order polynomial through N+1
adjacent data points, and assuming that N+1 is even and we start
counting the data points from "0" to "N", the interpolation is used for
the space between data points (N-1)/2 to (N+1)/2.

Hermite polynomial interpolation will fit an Nth order polynomial only
to the two adjacent data points at indices (N-1)/2 to (N+1)/2, but will
also match as many derivatives as possible at those two adjacent data
points with the interpolation polynomials that go through those
neighbors and *their* neighbors. that means that these derivatives of
the Nth order Hermite at the (N-1)/2 point can only depend on data
points 0 to N-1 and the derivatives at the (N+1)/2 point can only
depend on data points 1 to N (and must be the same function of those N
points).

a 3rd order Hermite interpolation polynomial will match the 0th and 1st
derivative at the 1st and 2nd point.  the value of the polynomial (the
"0th derivative") at x[1] *is* x[1] and the value of the 1st derivative
at x[1] is (x[2]-x[0])/2 (assuming uniform spacing).  similarly, the
value of the polynomial (the "0th derivative") at x[2] is x[2] and the
value of the 1st derivative at x[2] is (x[3]-x[1])/2.  that way, both
the polynomial value *and* slope matches the polynomial and slope of
the neighboring interpolations.

there are more (such as B-splines), but, for the most part, you need 4
points for 3rd order polynomial interpolation.

r b-j

robert bristow-johnson wrote:
> for 3rd order polynomial interpolation, it's usually 4 data points (and
> you're interpolating between the inner two data points).
...
> a 3rd order Hermite interpolation polynomial will match the 0th and 1st
> derivative at the 1st and 2nd point.

This is for symmetric interpolation.  At or beyond the ends
of data sets, one could also try asymmetric or single ended
interpolation polynomials: for instance, matching the 0th
derivative at the left end and the 0th, 1st and 2nd at the right
end of a segment; or even matching nothing at the left end,
and the 0th thru 3rd derivative at the right end.

I find this possibly useful at the ends of data sets instead
of symmetric (linear phase windowed sinc, etc.) interpolation,
especially when the assumption that the "real" phenomena is
approximately continuous in several derivatives at or around
the ends of the data set to be a more realistic assumption than
that the phenomena is zero, reflected, repeated or cyclic.


IMHO. YMMV.
-- 
rhn A.T nicholson d.O.t C-o-M

Ron N. wrote:
> robert bristow-johnson wrote:
> > for 3rd order polynomial interpolation, it's usually 4 data points (and
> > you're interpolating between the inner two data points).
> ...
> > a 3rd order Hermite interpolation polynomial will match the 0th and 1st
> > derivative at the 1st and 2nd point.
>
> This is for symmetric interpolation.
...
yes, true.

my preconceptions stem from doing this on audio signals and normally i
expect this symmetry (or reversibility - the interpolation should work
just the same if you played the audio backwards) to be sorta normative.

but, you're right, it doesn't have to be.

r b-j