lecture notes on polynomial interpolation

1 Summary of notation and terminonlogy

•

multi-evaluation mapping: $\operatorname{ev}_{\mathbf{x}}:\mathcal{P}_{m}\to\mathbb{R}^{n},\;\mathbf{x}% \in\mathbb{R}^{n}$ . Here $\mathcal{P}_{m}$ is the vector space of polynomials of degree $m$ or less.
•

interpolation mapping: $\operatorname{pol}_{\mathbf{x}}:\mathbb{R}^{n}\to\mathcal{P}_{n-1},\;\mathbf{x% }\in\mathbb{R}^{n}$ where $x_{1},\ldots,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 $\mathbf{x}\in\mathbb{R}^{n}$ be given. Define $\operatorname{ev}_{\mathbf{x}}:\mathcal{P}_{m}\to\mathbb{R}^{n}$ , the multi-evaluation mapping, to be the linear transformation given by

\operatorname{ev}_{\mathbf{x}}:p\to\begin{bmatrix}p(x_{1})\\ \vdots\\ p(x_{n})\end{bmatrix},\quad p\in\mathcal{P}_{m}.

Problem 2 (Polynomial interpolation).

Given $(x_{1},y_{1}),\ldots,(x_{n},y_{n})\in\mathbb{R}^{2}$ to find a polynomial $p\in\mathcal{P}_{m}$ such that $p(x_{i})=y_{i},\;i=1,\ldots,n$ . Equivalently, given $\mathbf{x},\mathbf{y}\in\mathbb{R}^{n}$ to find the preimage $\operatorname{ev}_{\mathbf{x}}^{-1}(\mathbf{y})$ .

Theorem 3.

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

3 Vandermonde matrix, polynomial, and determinant

Definition 4.

For a given $\mathbf{x}\in\mathbb{R}^{n}$ , the following matrix

\mathsf{VM}(\mathbf{x})=\mathsf{VM}(x_{1},\ldots,x_{n})=\begin{bmatrix}1&x_{1}% &x_{1}^{2}&\ldots&x_{1}^{n-1}\\ 1&x_{2}&x_{2}^{2}&\ldots&x_{2}^{n-1}\\ 1&x_{3}&x_{3}^{2}&\ldots&x_{3}^{n-1}\\ \vdots&\vdots&\vdots&\ddots&\vdots\\ 1&x_{n}&x_{n}^{2}&\ldots&x_{n}^{n-1}\end{bmatrix}

is called the Vandermonde matrix. The expression,

\mathsf{V}(\mathbf{x})=\mathsf{V}(x_{1},\ldots,x_{n})=\prod_{1\leq i<j\leq n}(% x_{j}-x_{i})

is called the Vandermonde polynomial. Note: we define $\mathsf{V}(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 $\operatorname{ev}_{\mathbf{x}}$ with the monomial basis $[1,x,\ldots,x^{n}]$ as the input basis and the standard basis $[\mathbf{e}_{1},\ldots,\mathbf{e}_{n+1}]$ as the output basis.

Theorem 6.

The Vandermonde polynomial gives the determinant of the Vandermonde matrix:

\left|\begin{matrix}1&x_{1}&\ldots&x_{1}^{n-1}\\ 1&x_{2}&\ldots&x_{2}^{n-1}\\ \vdots&\vdots&\ddots&\vdots\\ 1&x_{n}&\ldots&x_{n}^{n-1}\end{matrix}\right|=\prod_{1\leq i<j\leq n+1}(x_{j}-% x_{i}),

(1)

or more succinctly,

\det\mathsf{VM}(\mathbf{x})=\mathsf{V}(\mathbf{x}).

Proof.

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

\mathsf{VM}(x_{1})=\begin{bmatrix}1\end{bmatrix},\quad\mathsf{V}(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},\ldots,x_{n}\in\mathbb{R}$ and a variable $x$ , and consider the $n^{\text{th}}$ degree polynomial

p(x)=\det\mathsf{VM}(x_{1},\ldots,x_{n},x)=\left|\begin{matrix}1&x_{1}&\ldots&% x_{1}^{n-1}&x_{1}^{n}\\ 1&x_{2}&\ldots&x_{2}^{n-1}&x_{2}^{n}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1&x_{n}&\ldots&x_{n}^{n-1}&x_{n}^{n}\\ 1&x&\ldots&x^{n-1}&x^{n}\end{matrix}\right|

By the properties of determinants, $x_{1},\ldots,x_{n}$ are roots of $p(x)$ . Taking the cofactor expansion along the bottom row, we see that the coefficient of $x^{n}$ is $\mathsf{V}(x_{1},\ldots,x_{n})$ . Therefore,

p(x)=\mathsf{V}(x_{1},\ldots,x_{n})(x-x_{1})\cdots(x-x_{n})=\mathsf{V}(x_{1},% \ldots,x_{n},x),

as was to be shown. ∎

4 Lagrange interpolation formula

Let $x_{1},\ldots,x_{n}\in\mathbb{R}$ be distinct. We know that $\operatorname{ev}_{\mathbf{x}}:\mathcal{P}_{n-1}\to\mathbb{R}^{n}$ is invertible. Let $\operatorname{pol}_{\mathbf{x}}:\mathbb{R}^{n}\to\mathcal{P}_{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,\ldots,n$ let us define the polynomial

p_{i}(x)=\prod_{j\neq 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\neq j$

Theorem 7 (Lagrange interpolation formula).

Let $x_{1},\ldots,x_{n}\in\mathbb{R}$ be distinct. Then,

\operatorname{pol}_{\mathbf{x}}(\mathbf{y})=y_{1}p_{1}+\cdots+y_{n}p_{n}.

5 Underdetermined and overdetermined interpolation

Definition 8.

Let $T:\mathcal{U}\to\mathcal{V}$ be a linear transformation of finite dimensional vector spaces. A linear problem is an equation of the form

T(\mathbf{u})=\mathbf{v},

where $\mathbf{v}\in\mathcal{V}$ is given, and $\mathbf{u}\in\mathcal{U}$ is the unknown. To be more precise, the problem is to determine the preimage $T^{-1}(\mathbf{v})$ for a given $\mathbf{v}\in\mathcal{V}$ . We say that the problem is overdetermined if $\dim\mathcal{V}>\dim\mathcal{U}$ , i.e. if there are more equations than unknowns. The linear problem is said to be underdetermined if $\dim\mathcal{V}<\dim\mathcal{U}$ , 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 $\mathbf{v}$ satisfies a number linear compatibility constraints, equations that describe the image $\operatorname{Im}(T)$ . To put it another way, an overdetermined system arises when $T$ is not onto.

Definition 10.

Let $x_{1},\ldots,x_{n}\in\mathbb{R}$ be distinct and let $\operatorname{ev}_{\mathbf{x}}:\mathcal{P}_{m}\to\mathbb{R}^{n}$ be the corresponding multi-evaluation mapping. Let $\mathbf{y}\in\mathbb{R}^{n}$ be given. The linear equation

\operatorname{ev}_{\mathbf{x}}(p)=\mathbf{y},\quad p\in\mathcal{P}_{m}

is called an underdetermined interpolation problem if $m\geq n$ . If $m\leq 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 $\operatorname{pol}_{\mathbf{x}}(\mathbf{y})$ given by the Lagrange interpolation formula.

Proposition 11 (Underdetermined interpolation).

Let $x_{1},\ldots,x_{n}\in\mathbb{R}$ be distinct. Define

q(x)=(x-x_{1})\cdots(x-x_{n})

to be the $n^{\text{th}}$ degree polynomial with the $x_{i}$ as its roots. Suppose that $m\geq n$ . Then, the multi-evaluation mapping $\operatorname{ev}_{\mathbf{x}}:\mathcal{P}_{m}\to\mathbb{R}^{n}$ is not one-to-one. A basis for the kernel is given by $q(x),xq(x),\ldots,x^{m-n}q(x)$ . Let $y_{1},\ldots,y_{n}\in\mathbb{R}$ be given. The solution set to the interpolation problem $\operatorname{ev}_{\mathbf{x}}(p)=\mathbf{y}$ , is given by

\operatorname{ev}_{\mathbf{x}}^{-1}(\mathbf{y})=\{r+sq:s\in\mathcal{P}_{m-n}\},

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

\operatorname{ev}_{\mathbf{x}}(p)=\mathbf{y}

is given by

p=r+sq,\quad s\in\mathcal{P}_{n-m}\text{ free.}

Proposition 12 (Overdetermined interpolation).

Let $x_{1},\ldots,x_{n}\in\mathbb{R}$ be distinct. Suppose that $m\leq n-2$ . Then, the multi-evaluation mapping $\operatorname{ev}_{\mathbf{x}}:\mathcal{P}_{m}\to\mathbb{R}^{n}$ is not onto. If $m=n-2$ , then $\mathbf{y}\in\mathbb{R}^{4}$ belongs to $\operatorname{Im}(\operatorname{ev}_{\mathbf{x}})$ if and only if

\left|\begin{matrix}1&x_{1}&\ldots&x_{1}^{m}&y_{1}\\ 1&x_{2}&\ldots&x_{2}^{m}&y_{2}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1&x_{n-1}&\ldots&x_{n-1}^{m}&y_{n-1}\\ 1&x_{n}&\ldots&x_{n}^{m}&y_{n}\end{matrix}\right|=0

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

M(\mathbf{x},\mathbf{y})=\begin{bmatrix}1&x_{1}&\ldots&x_{1}^{m}&y_{1}\\ 1&x_{2}&\ldots&x_{2}^{m}&y_{2}\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 1&x_{m+1}&\ldots&x_{m+1}^{m}&y_{m+1}\\ \vdots&\vdots&\vdots&\vdots&\vdots\\ 1&x_{n}&\ldots&x_{n}^{m}&y_{n}\end{bmatrix}

Remark 13.

The compatibility constraints on $y_{1},\ldots,y_{n}$ for an overdetermined system amount to the condition that $\mathbf{y}$ lie in the image of $\operatorname{ev}_{\mathbf{x}}$ , 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(\mathbf{x},\mathbf{y})$ 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}),\ldots,(x_{m},y_{m})$ to obtain a $p=y_{1}p_{1}+y_{m+1}p_{m+1}\in\mathcal{P}_{m}$ . The additional equations

y_{i}=y_{1}p_{1}(x_{i})+\cdots+y_{m+1}p_{m+1}(x_{i}),\;i=m+2,\ldots,n

are the desired compatibility constraints on $y_{1},\ldots,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