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 ofdegree $m$ or less.

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

• 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 lineartransformation 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 thepreimage ${\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 onlyif 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 calledthe Vandermonde matrix. Theexpression,

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 themonomial basis $\mathrm{[}\mathrm{1}\mathrm{,}x\mathrm{,}\mathrm{\dots }\mathrm{,}{x}^n\mathrm{]}$ as the input basis and thestandard 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 Vandermondematrix:

(1)

or more succinctly,

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

Proof.

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

$$\mathrm{𝖵𝖬}(x_1)=\left[\begin{array}{c}\hfill 1\hfill \end{array}\right],𝖵(x_1)=1.$$

Evidently then, theformula works for $n=1$. Next, suppose that we believe the formulafor 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, wesee 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$ andso 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 dimensionalvector spaces. A linear problem is an equation of the form

$$T(𝐮)=𝐯,$$

where $𝐯\in 𝒱$ is given, and $𝐮\in 𝒰$ isthe unknown. To be more precise, the problem is to determinethe preimage $T^{-1}(𝐯)$ for a given $𝐯\in 𝒱$. We say that theproblem is overdetermined if $dim𝒱>dim𝒰$, i.e. if thereare more equations than unknowns. The linear problem is said to beunderdetermined if , i.e., if there are morevariables than equations.

Remark 9.

By the rank-nullity theorem, anunderdetermined linear problem will either be inconsistent, or willhave multiple solutions. Thus, an underdetermined system arises when$T$ is not one-to-one; i.e., the kernel $\ker (T)$ is non-trivial. Anoverdetermined linear system is inconsistent, unless $𝐯$ satisfies anumber linear compatibility constraints, equations that describe the image$\mathrm{Im}(T)$. To put it another way, an overdetermined system ariseswhen $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-evaluationmapping. 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 overdeterminedinterpolation problem. Note that if $m=n-1$, the interpolationproblem is “just right”; there is exactly one solution, namely thepolynomial${\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 thekernel 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 solutionset 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 Lagrangeinterpolation formula. To put it another way, the general solutionof 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 onlyif $\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 conditionthat $𝐲$ 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 theaugmented matrix $M(𝐱,𝐲)$ to echelon form. The back entries ofthe 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$.