lecture notes on polynomial interpolation

1 Summary of notation and terminonlogy

• multi-evaluation mapping: ${\mathrm{ev}}_{𝐱}:{𝒫}_m\to {ℝ}^n,𝐱\in {ℝ}^n$. Here ${𝒫}_m$ is the vector space of polynomials of degree $m$ or less.

• interpolation mapping: ${\mathrm{pol}}_{𝐱}:{ℝ}^n\to {𝒫}_{n-1},𝐱\in {ℝ}^n$ where $x_1,\mathrm{\dots },x_n$ are distinct;

• Vandermonde matrix and polynomial;

• overdetermined and underdetermined linear system;

• overdetermined and underdetermined interpolation problem

2 The polynomial interpolation problem

Definition 1.

Let $𝐱\in {ℝ}^n$ be given. Define ${\mathrm{ev}}_{𝐱}:{𝒫}_m\to {ℝ}^n$, the multi-evaluation mapping, to be the linear transformation given by

$${\mathrm{ev}}_{𝐱}:p\to \left[\begin{array}{c}\hfill p(x_1)\hfill \\ \hfill \mathrm{⋮}\hfill \\ \hfill p(x_n)\hfill \end{array}\right],p\in {𝒫}_m.$$

Problem 2 (Polynomial interpolation).

Given $(x_1,y_1),\mathrm{\dots },(x_n,y_n)\in {ℝ}^2$ to find a polynomial $p\in {𝒫}_m$ such that $p(x_i)=y_i,i=1,\mathrm{\dots },n$. Equivalently, given $𝐱,𝐲\in {ℝ}^n$ to find the preimage ${\mathrm{ev}}_{𝐱}^{-1}(𝐲)$.

Theorem 3.

Fix $\mathrm{x}\mathrm{\in }{\mathrm{R}}^n$. The multi-evaluation mapping ${\mathrm{ev}}_{\mathrm{x}}\mathrm{:}{\mathrm{P}}_{n\mathrm{-}\mathrm{1}}\mathrm{\to }{\mathrm{R}}^n$ is an isomorphism if and only if the components $x_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{x}_n$ are distinct.

3 Vandermonde matrix, polynomial, and determinant

Definition 4.

For a given $𝐱\in {ℝ}^n$, the following matrix

is called the Vandermonde matrix. The expression,

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

Proposition 5.

The Vandermonde matrix is the transformation matrix of ${\mathrm{ev}}_{\mathrm{x}}$ with the monomial basis $\mathrm{[}\mathrm{1}\mathrm{,}x\mathrm{,}\mathrm{\dots }\mathrm{,}{x}^n\mathrm{]}$ as the input basis and the standard basis $\mathrm{[}{\mathrm{e}}_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{\mathrm{e}}_{n\mathrm{+}\mathrm{1}}\mathrm{]}$ as the output basis.

Theorem 6.

The Vandermonde polynomial gives the determinant of the Vandermonde matrix:

(1)

or more succinctly,

$$det\mathrm{𝖵𝖬}(𝐱)=𝖵(𝐱).$$

Proof.

We will prove formula (1) by induction on $n$. Note that

$$\mathrm{𝖵𝖬}(x_1)=\left[\begin{array}{c}\hfill 1\hfill \end{array}\right],𝖵(x_1)=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 $x_1,\mathrm{\dots },x_n\in ℝ$ and a variable $x$, and consider the $n^{\text{th}}$ degree polynomial

By the properties of determinants, $x_1,\mathrm{\dots },x_n$ are roots of $p(x)$. Taking the cofactor expansion along the bottom row, we see that the coefficient of $x^n$ is $𝖵(x_1,\mathrm{\dots },x_n)$. Therefore,

$$p(x)=𝖵(x_1,\mathrm{\dots },x_n)(x-x_1)\mathrm{\cdots }(x-x_n)=𝖵(x_1,\mathrm{\dots },x_n,x),$$

as was to be shown. ∎

4 Lagrange interpolation formula

Let $x_1,\mathrm{\dots },x_n\in ℝ$ be distinct. We know that ${\mathrm{ev}}_{𝐱}:{𝒫}_{n-1}\to {ℝ}^n$ is invertible. Let ${\mathrm{pol}}_{𝐱}:{ℝ}^n\to {𝒫}_{n-1}$ 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 $i=1,\mathrm{\dots },n$ let us define the polynomial

$$p_i(x)=\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}.$$

These $n-1$ degree polynomials have been “engineered” so that $p_i(x_i)=1$ and so that $p_i(x_j)=0$ for $i\ne j$

Theorem 7 (Lagrange interpolation formula).

Let $x_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{x}_n\mathrm{\in }\mathrm{R}$ be distinct. Then,

$${\mathrm{pol}}_{𝐱}(𝐲)=y_1{p}_1+\mathrm{\cdots }+y_n{p}_n.$$

5 Underdetermined and overdetermined interpolation

Definition 8.

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

$$T(𝐮)=𝐯,$$

where $𝐯\in 𝒱$ is given, and $𝐮\in 𝒰$ is the unknown. To be more precise, the problem is to determine the preimage $T^{-1}(𝐯)$ for a given $𝐯\in 𝒱$. 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 , i.e., if there are more variables than equations.

Remark 9.

By the rank-nullity theorem, 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 $\mathrm{Im}(T)$. To put it another way, an overdetermined system arises when $T$ is not onto.

Definition 10.

Let $x_1,\mathrm{\dots },x_n\in ℝ$ be distinct and let ${\mathrm{ev}}_{𝐱}:{𝒫}_m\to {ℝ}^n$ be the corresponding multi-evaluation mapping. Let $𝐲\in {ℝ}^n$ be given. The linear equation

$${\mathrm{ev}}_{𝐱}(p)=𝐲,p\in {𝒫}_m$$

is called an underdetermined interpolation problem if $m\ge n$. If $m\le 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 ${\mathrm{pol}}_{𝐱}(𝐲)$ given by the Lagrange interpolation formula.

Proposition 11 (Underdetermined interpolation).

Let $x_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{x}_n\mathrm{\in }\mathrm{R}$ be distinct. Define

$$q(x)=(x-x_1)\mathrm{\cdots }(x-x_n)$$

to be the $n^{\text{𝑡ℎ}}$ degree polynomial with the $x_i$ as its roots. Suppose that $m\mathrm{\ge }n$. Then, the multi-evaluation mapping ${\mathrm{ev}}_{\mathrm{x}}\mathrm{:}{\mathrm{P}}_m\mathrm{\to }{\mathrm{R}}^n$ is not one-to-one. A basis for the kernel is given by $q\mathit{}\mathrm{(}x\mathrm{)}\mathrm{,}x\mathit{}q\mathit{}\mathrm{(}x\mathrm{)}\mathrm{,}\mathrm{\dots }\mathrm{,}{x}^{m\mathrm{-}n}\mathit{}q\mathit{}\mathrm{(}x\mathrm{)}$. Let $y_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{y}_n\mathrm{\in }\mathrm{R}$ be given. The solution set to the interpolation problem ${\mathrm{ev}}_{\mathrm{x}}\mathit{}\mathrm{(}p\mathrm{)}\mathrm{=}\mathrm{y}$, is given by

$${\mathrm{ev}}_{𝐱}^{-1}(𝐲)=\{r+sq:s\in {𝒫}_{m-n}\},$$

where $r\mathrm{=}{\mathrm{pol}}_{\mathrm{x}}\mathit{}\mathrm{(}\mathrm{y}\mathrm{)}$ is the $n\mathrm{-}{\mathrm{1}}^{\text{𝑠𝑡}}$ degree polynomial given by the Lagrange interpolation formula. To put it another way, the general solution of the equation

$${\mathrm{ev}}_{𝐱}(p)=𝐲$$

is given by

$$p=r+sq,s\in {𝒫}_{n-m}\mathit{\text{ free.}}$$

Proposition 12 (Overdetermined interpolation).

Let $x_{\mathrm{1}}\mathrm{,}\mathrm{\dots }\mathrm{,}{x}_n\mathrm{\in }\mathrm{R}$ be distinct. Suppose that $m\mathrm{\le }n\mathrm{-}\mathrm{2}$. Then, the multi-evaluation mapping ${\mathrm{ev}}_{\mathrm{x}}\mathrm{:}{\mathrm{P}}_m\mathrm{\to }{\mathrm{R}}^n$ is not onto. If $m\mathrm{=}n\mathrm{-}\mathrm{2}$, then $\mathrm{y}\mathrm{\in }{\mathrm{R}}^{\mathrm{4}}$ belongs to $\mathrm{Im}\mathit{}\mathrm{(}{\mathrm{ev}}_{\mathrm{x}}\mathrm{)}$ if and only if

More generally, for any $m\mathrm{\le }n\mathrm{-}\mathrm{2}$, the interpolation problem ${\mathrm{ev}}_{\mathrm{x}}\mathit{}\mathrm{(}p\mathrm{)}\mathrm{=}\mathrm{y}\mathrm{,}\mathrm{y}\mathrm{\in }{\mathrm{R}}^n$ has a solution if and only if $\mathrm{rank}\mathit{}M\mathit{}\mathrm{(}\mathrm{x}\mathrm{,}\mathrm{y}\mathrm{)}\mathrm{=}m\mathrm{+}\mathrm{1}$ where

Remark 13.

The compatibility constraints on $y_1,\mathrm{\dots },y_n$ for an overdetermined system amount to the condition that $𝐲$ lie in the image of ${\mathrm{ev}}_{𝐱}$, 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 $M(𝐱,𝐲)$ to echelon form. The back entries of the last $n-m-1$ rows will hold the constraint equations. Equivalently, we can solve the interpolation problem for $(x_1,y_1),\mathrm{\dots },(x_m,y_m)$ to obtain a $p=y_1{p}_1+y_{m+1}{p}_{m+1}\in {𝒫}_m$. The additional equations

$$y_i=y_1{p}_1(x_i)+\mathrm{\cdots }+y_{m+1}{p}_{m+1}(x_i),i=m+2,\mathrm{\dots },n$$

are the desired compatibility constraints on $y_1,\mathrm{\dots },y_n$.

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