Polynomial Interpolations by Various Approaches
Cubic and Quintic Hermite Interpolation
A common problem in curve design is point data interpolation: from
data points pi with corresponding parameter values ti , find a curve
that passes through pi . One of the oldest techniques to solve this
problem is to find an interpolating polynomial through the given points.
This technique is usually called polynomial interpolation. Several algorithms
exist for this problem-any textbook on numerical analysis will discuss
several of them. We will also discuss several approaches, which will
include Aitken's approach, Lagrange's method and the Vandermonde approach.
Polynomial Interpolations by Various Approaches --
Aitken's Approach --
The Aitken recursion computes a point on the interpolating polynomial
through a sequence of repeated linear interpolations, starting with
Let us now suppose (as one does in recursive techniques) that we have
already solved the problem for the case n-1. To be more precise, assume
that we have found a polynomial that interpolates to the n first data
points p0,..., pn-1, and also a polynomial that interpolates to the
n last data points p1,..., pn. Under these assumptions, it is easy
to write down the form of the final interpolant, now called :
Aitken's Algorithm -- (*junk*)
The Vandermonde Approach --
Suppose we want the interpolating polynomial in the monomial basis:
The standard approach to finding the unknown coefficients from the
known data is simply to write down everything one knows about the
problem: In matrix form: We can shorten this to We already know that
a solution a to this linear system exists, but one can show independently
that the determinant det T is non-zero (for distinct parameter values
ti). This determinant is known as the Vandermonde of the interpolation
problem. The solution, i.e. the vector a containing the coefficients
aj , can be found from
Interpolation of Curves with Lagrange Polynomials --
In terms of the Lagrange polynomials, the solution of the interpolation
problem is given by with the given interpolation points. For example,
suppose we want to interpolate the points given in the following table:
The associated Lagrange polynomials are then and the Lagrange formula
for the solution is given by
Disadvantage: There remains, however, one disadvantage in using Lagrange
polynomials to solve the interpolation problem: if we add one additional
knot, then all of the basis functions have to be recomputed. This
disadvantage can be eliminated if we use the Newton interpolation
method discussed in the following section.
Interpolation of Curves with Newton Polynomials --
Now suppose we look for a solution of the interpolation problem in
The coefficients A j can be found directly:
etc. To make this computation systematic, we introduce the idea of
a divided difference:
Then the coefficients can be written as
It is clear that if we add a new point , then we simply have to carry
out one more step in this divided difference scheme.
Cubic Hermite Interpolation --
Polynomial interpolation is not restricted to interpolation to point
data: one can also interpolate to other information, such as derivative
data. This leads to an interpolation scheme that is more useful than
Lagrange interpolation: it is called Hermite interpolation. We treat
the cubic case first, in which one is given two points p0, p1 and two
tangent vectors m0, m1. The objective is to find a cubic polynomial
curve p that interpolates to these data: p(0) = p0, p'(0) = m0, p'(1)
= m1, p(1) = p1, where the prime denotes differentiation. Let be in
cubic Bezier form. We wish to determine the coefficients bi , i=0,1,2,3.
Claim: Now plugging the obtained bi into p(t) we get
Cardinal Form of the interpolating polynomial To obtain the cardinal
form, we simply rearrange: where we have set The are called "cubic Hermite
polynomials." Note: The cubic Hermite polynomials satisfy the cardinal
Peculiarity of Cubic Hermite Interpolation Cubic Hermite interpolation
has one annoying peculiarity: it is not invariant under affine domain
transformations. Let a cubic Hermite interpolant given as i.e. having
the interval [0,1] as its domain. Now apply an affine domain transformation
to it by changing t to , thereby changing [0,1] to some [a,b]. The interpolant
then becomes where the are defined through their cardinal properties:
To satisfy these requirements, the new must differ from the original
. We obtain where t ‘ [0,1] is the local parameter of the interval [a,b].
Quintic Hermite Interpolation --
Instead of prescribing only position and first derivative information
at two points, one might add information for second-order derivatives.
Then our data are p0, m0, s0 and p1, m1, s1, where s0 and s1 denote
second derivatives. The lowest order polynomial to interpolate to these
data is of degree five. Its Bezier points are easily obtained following
the approach used earlier for cubic polynomials. If we rearrange the
Bezier form to obtain a cardinal form of the interpolant, we find where
It is easy to verify the cardinal properties of the : they are the straighforward
generalization of the cardinal properties for cubic Hermite polynomials.
The code for Aitken's algorithm is very similar to that for the de
Castlejau algorithm. Here is its header:
float aitken(degree, coeff, t)
/* uses Aitken to compute one coordinate value of a
Lagrange interpolating polynomial. Has to be called
for each coordinate (x, y, and/or z) of data points.
Input: degree: degree of curve.
coeff: array with coordinates to be interpolated.
t: parameter value.
Output: coordinate value.
Note: we assume a uniform knot sequence! */