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

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


is called the Vandermonde matrix. The expression,


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,


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


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


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,


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


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,


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


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


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


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


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


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


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

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


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