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 form
The coefficients A j can be found directly:
which gives:
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 properties,
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! */