lecture notes on polynomial interpolation


1 Summary of notation and terminonlogy

2 The polynomial interpolation problem

Definition 1.

Let 𝐱∈ℝn be given. Define ev𝐱:𝒫m→ℝn, the multi-evaluation mapping, to be the linear transformation given by

ev𝐱:p→[p⁢(x1)⋮p⁢(xn)],p∈𝒫m.
Problem 2 (Polynomial interpolation).

Given (x1,y1),…,(xn,yn)∈ℝ2 to find a polynomial p∈𝒫m such that p⁢(xi)=yi,i=1,…,n. Equivalently, given 𝐱,𝐲∈ℝn to find the preimageMathworldPlanetmath ev𝐱-1⁡(𝐲).

Theorem 3.

Fix x∈Rn. The multi-evaluation mapping evx:Pn-1→Rn is an isomorphismPlanetmathPlanetmathPlanetmathPlanetmath if and only if the componentsPlanetmathPlanetmath x1,…,xn are distinct.

3 Vandermonde matrix, polynomial, and determinant

Definition 4.

For a given 𝐱∈ℝn, the following matrix

𝖵𝖬⁢(𝐱)=𝖵𝖬⁢(x1,…,xn)=[1x1x12…x1n-11x2x22…x2n-11x3x32…x3n-1⋮⋮⋮⋱⋮1xnxn2…xnn-1]

is called the Vandermonde matrix. The expression,

𝖵⁢(𝐱)=𝖵⁢(x1,…,xn)=∏1≤i<j≤n(xj-xi)

is called the Vandermonde polynomial. Note: we define 𝖵⁢(x1)=1; the usual convention is that the empty product is equal to 1.

Proposition 5.

The Vandermonde matrix is the transformation matrix of evx with the monomial basis [1,x,…,xn] as the input basis and the standard basis [e1,…,en+1] as the output basis.

Theorem 6.

The Vandermonde polynomial gives the determinantMathworldPlanetmath of the Vandermonde matrix:

|1x1…x1n-11x2…x2n-1⋮⋮⋱⋮1xn…xnn-1|=∏1≤i<j≤n+1(xj-xi), (1)

or more succinctly,

det⁡𝖵𝖬⁢(𝐱)=𝖵⁢(𝐱).
Proof.

We will prove formulaMathworldPlanetmathPlanetmath (1) by inductionMathworldPlanetmath on n. Note that

𝖵𝖬⁢(x1)=[1],𝖵⁢(x1)=1.

Evidently then, the formula works for n=1. Next, suppose that we believe the formula for a given n. We show that the formula is valid for n+1. For x1,…,xn∈ℝ and a variable x, and consider the nth degree polynomial

p⁢(x)=det⁡𝖵𝖬⁢(x1,…,xn,x)=|1x1…x1n-1x1n1x2…x2n-1x2n⋮⋮⋱⋮⋮1xn…xnn-1xnn1x…xn-1xn|

By the properties of determinants, x1,…,xn are roots of p⁢(x). Taking the cofactor expansion along the bottom row, we see that the coefficient of xn is 𝖵⁢(x1,…,xn). Therefore,

p⁢(x)=𝖵⁢(x1,…,xn)⁢(x-x1)⁢⋯⁢(x-xn)=𝖵⁢(x1,…,xn,x),

as was to be shown. ∎

4 Lagrange interpolation formula

Let x1,…,xn∈ℝ be distinct. We know that ev𝐱:𝒫n-1→ℝn is invertiblePlanetmathPlanetmathPlanetmath. Let pol𝐱:ℝn→𝒫n-1 denote the inversePlanetmathPlanetmathPlanetmath. In principle, this inverse is described by the inverse of the Vandermonde matrix. Is there another way to solve the interpolation problem? For i=1,…,n let us define the polynomial

pi⁢(x)=∏j≠ix-xjxi-xj.

These n-1 degree polynomials have been “engineered” so that pi⁢(xi)=1 and so that pi⁢(xj)=0 for i≠j

Theorem 7 (Lagrange interpolation formula).

Let x1,…,xn∈R be distinct. Then,

pol𝐱⁡(𝐲)=y1⁢p1+⋯+yn⁢pn.

5 Underdetermined and overdetermined interpolation

Definition 8.

Let T:𝒰→𝒱 be a linear transformation of finite dimensional vector spaces. A linear problem is an equation of the form

T⁢(𝐮)=𝐯,

where 𝐯∈𝒱 is given, and 𝐮∈𝒰 is the unknown. To be more precise, the problem is to determine the preimage T-1⁢(𝐯) for a given 𝐯∈𝒱. We say that the problem is overdetermined if dim⁡𝒱>dim⁡𝒰, i.e. if there are more equations than unknowns. The linear problem is said to be underdetermined if dim⁡𝒱<dim⁡𝒰, i.e., if there are more variables than equations.

Remark 9.

By the rank-nullity theoremMathworldPlanetmath, an underdetermined linear problem will either be inconsistent, or will have multiple solutions. Thus, an underdetermined system arises when T is not one-to-one; i.e., the kernel ker⁡(T) is non-trivial. An overdetermined linear system is inconsistent, unless 𝐯 satisfies a number linear compatibility constraints, equations that describe the image Im⁡(T). To put it another way, an overdetermined system arises when T is not onto.

Definition 10.

Let x1,…,xn∈ℝ be distinct and let ev𝐱:𝒫m→ℝn be the corresponding multi-evaluation mapping. Let 𝐲∈ℝn be given. The linear equation

ev𝐱⁡(p)=𝐲,p∈𝒫m

is called an underdetermined interpolation problem if m≥n. If m≤n-2, we call the above equation an overdetermined interpolation problem. Note that if m=n-1, the interpolation problem is “just right”; there is exactly one solution, namely the polynomial pol𝐱⁡(𝐲) given by the Lagrange interpolation formula.

Proposition 11 (Underdetermined interpolation).

Let x1,…,xn∈R be distinct. Define

q⁢(x)=(x-x1)⁢⋯⁢(x-xn)

to be the n𝑡ℎ degree polynomial with the xi as its roots. Suppose that m≥n. Then, the multi-evaluation mapping evx:Pm→Rn is not one-to-one. A basis for the kernel is given by q⁢(x),x⁢q⁢(x),…,xm-n⁢q⁢(x). Let y1,…,yn∈R be given. The solution set to the interpolation problem evx⁡(p)=y, is given by

ev𝐱-1⁡(𝐲)={r+s⁢q:s∈𝒫m-n},

where r=polx⁡(y) is the n-1𝑠𝑡 degree polynomial given by the Lagrange interpolation formula. To put it another way, the general solution of the equation

ev𝐱⁡(p)=𝐲

is given by

p=r+s⁢q,s∈𝒫n-m⁢ free.
Proposition 12 (Overdetermined interpolation).

Let x1,…,xn∈R be distinct. Suppose that m≤n-2. Then, the multi-evaluation mapping evx:Pm→Rn is not onto. If m=n-2, then y∈R4 belongs to Im⁡(evx) if and only if

|1x1…x1my11x2…x2my2⋮⋮⋱⋮⋮1xn-1…xn-1myn-11xn…xnmyn|=0

More generally, for any m≤n-2, the interpolation problem evx⁡(p)=y,y∈Rn has a solution if and only if rank⁡M⁢(x,y)=m+1 where

M⁢(𝐱,𝐲)=[1x1…x1my11x2…x2my2⋮⋮⋱⋮⋮1xm+1…xm+1mym+1⋮⋮⋮⋮⋮1xn…xnmyn]
Remark 13.

The compatibility constraints on y1,…,yn for an overdetermined system amount to the condition that 𝐲 lie in the image of ev𝐱, or what is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath, belong to the column space of the corresponding transformation matrix. We can therefore obtain the constraint equations by row reducing the augmented matrix M⁢(𝐱,𝐲) to echelon formMathworldPlanetmath. The back entries of the last n-m-1 rows will hold the constraint equations. Equivalently, we can solve the interpolation problem for (x1,y1),…,(xm,ym) to obtain a p=y1⁢p1+ym+1⁢pm+1∈𝒫m. The additional equations

yi=y1⁢p1⁢(xi)+⋯+ym+1⁢pm+1⁢(xi),i=m+2,…,n

are the desired compatibility constraints on y1,…,yn.

Title lecture notes on polynomial interpolation
Canonical name LectureNotesOnPolynomialInterpolation
Date of creation 2013-03-22 16:51:59
Last modified on 2013-03-22 16:51:59
Owner rmilson (146)
Last modified by rmilson (146)
Numerical id 7
Author rmilson (146)
Entry type Topic
Classification msc 41A05
Related topic EvaluationHomomorphism
Related topic LagrangeInterpolationFormula
Related topic VanderMondeMatrix
Defines multi-evaluation mapping
Defines interpolation mapping
Defines polynomial interpolation