lecture notes on polynomial interpolation
1 Summary of notation and terminonlogy
2 The polynomial interpolation problem
Let be given. Define , the multi-evaluation mapping, to be the linear transformation given by
Problem 2 (Polynomial interpolation).
Given to find a polynomial such that . Equivalently, given to find the preimage .
3 Vandermonde matrix, polynomial, and determinant
For a given , the following matrix
is called the Vandermonde matrix. The expression,
is called the Vandermonde polynomial. Note: we define ; the usual convention is that the empty product is equal to .
The Vandermonde matrix is the transformation matrix of with the monomial basis as the input basis and the standard basis as the output basis.
The Vandermonde polynomial gives the determinant of the Vandermonde matrix:
or more succinctly,
Evidently then, the formula works for . Next, suppose that we believe the formula for a given . We show that the formula is valid for . For and a variable , and consider the degree polynomial
By the properties of determinants, are roots of . Taking the cofactor expansion along the bottom row, we see that the coefficient of is . Therefore,
as was to be shown. ∎
4 Lagrange interpolation formula
Let be distinct. We know that is invertible. Let denote the inverse. In principle, this inverse is described by the inverse of the Vandermonde matrix. Is there another way to solve the interpolation problem? For let us define the polynomial
These degree polynomials have been “engineered” so that and so that for
Theorem 7 (Lagrange interpolation formula).
Let be distinct. Then,
5 Underdetermined and overdetermined interpolation
Let be a linear transformation of finite dimensional vector spaces. A linear problem is an equation of the form
where is given, and is the unknown. To be more precise, the problem is to determine the preimage for a given . We say that the problem is overdetermined if , i.e. if there are more equations than unknowns. The linear problem is said to be underdetermined if , i.e., if there are more variables than equations.
By the rank-nullity theorem, an underdetermined linear problem will either be inconsistent, or will have multiple solutions. Thus, an underdetermined system arises when is not one-to-one; i.e., the kernel is non-trivial. An overdetermined linear system is inconsistent, unless satisfies a number linear compatibility constraints, equations that describe the image . To put it another way, an overdetermined system arises when is not onto.
Let be distinct and let be the corresponding multi-evaluation mapping. Let be given. The linear equation
is called an underdetermined interpolation problem if . If , we call the above equation an overdetermined interpolation problem. Note that if , the interpolation problem is “just right”; there is exactly one solution, namely the polynomial given by the Lagrange interpolation formula.
Proposition 11 (Underdetermined interpolation).
Let be distinct. Define
to be the degree polynomial with the as its roots. Suppose that . Then, the multi-evaluation mapping is not one-to-one. A basis for the kernel is given by . Let be given. The solution set to the interpolation problem , is given by
where is the degree polynomial given by the Lagrange interpolation formula. To put it another way, the general solution of the equation
is given by
Proposition 12 (Overdetermined interpolation).
Let be distinct. Suppose that . Then, the multi-evaluation mapping is not onto. If , then belongs to if and only if
More generally, for any , the interpolation problem has a solution if and only if where
The compatibility constraints on for an overdetermined system amount to the condition that lie in the image of , or what is equivalent, belong to the column space of the corresponding transformation matrix. We can therefore obtain the constraint equations by row reducing the augmented matrix to echelon form. The back entries of the last rows will hold the constraint equations. Equivalently, we can solve the interpolation problem for to obtain a . The additional equations
are the desired compatibility constraints on .
|Title||lecture notes on polynomial interpolation|
|Date of creation||2013-03-22 16:51:59|
|Last modified on||2013-03-22 16:51:59|
|Last modified by||rmilson (146)|