Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

lecture notes on polynomial interpolation

(Topic)

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 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

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

$\displaystyle \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.

Vandermonde matrix, polynomial, and determinant

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

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

is called the Vandermonde matrix. The expression,

$\displaystyle \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

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:

$\displaystyle \left\vert \begin{matrix}1 & x_1 & \ldots & x_1^{n-1} \\ 1 & x_2 ... ... & x_{n}^{n-1} \end{matrix} \right\vert = \prod_{1\leq i< j\leq n+1} (x_j-x_i),$

(1)

or more succinctly,

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

Proof. We will prove formula (1) by induction on

. Note that

$\displaystyle \mathsf{VM}(x_1) = \begin{bmatrix}1\end{bmatrix},\quad \mathsf{V}(x_1) = 1 .$

Evidently then, the formula works for

. Next, suppose that we believe the formula for a given

. We show that the formula is valid for

. For $x_1,\ldots, x_{n}\in \mathbb{R}$ and a variable

, and consider the $n^{\text{th}}$ degree polynomial

$\displaystyle p(x)=\det \mathsf{VM}(x_1,\ldots, x_n,x) = \left\vert \begin{matr... ...ts & x_n^{n-1} & x_n^n\ 1 & x & \ldots & x^{n-1}& x^n \end{matrix}\right\vert$

By the properties of determinants, $x_1,\ldots, x_n$ are roots of

. Taking the cofactor expansion along the bottom row, we see that the coefficient of

is $\mathsf{V}(x_1,\ldots, x_n)$ . Therefore,

$\displaystyle 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. $\qedsymbol$

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

$\displaystyle p_i(x) = \prod_{j\neq i} \frac{x-x_j}{x_i- x_j} .$

These

degree polynomials have been “engineered” so that

and so that

for $i\neq j$

Theorem 7 (Lagrange interpolation formula) Let $x_1,\ldots, x_n\in \mathbb{R}$ be distinct. Then,

$\displaystyle \operatorname{pol}_\mathbf{x}(\mathbf{y}) = y_1 p_1 + \cdots + y_n p_n.$

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

$\displaystyle 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

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

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

$\displaystyle \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

, 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

$\displaystyle q(x) = (x-x_1)\cdots (x-x_n)$

to be the $n^{\text{th}}$ degree polynomial with the 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), x q(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

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

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

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

is given by

$\displaystyle p = r + s q,\quad s\in \mathcal{P}_{n-m}$ 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 , then $\mathbf{y}\in\mathbb{R}^4$ belongs to $\operatorname{Im}(\operatorname{ev}_\mathbf{x})$ if and only if

$\displaystyle \left\vert \begin{matrix} 1 & x_1 & \ldots & x_1^{m}& y_1 \ 1 &... ...{n-1}^{m}&y_{n-1} \ 1& x_n & \ldots & x_n^{m} & y_n \end{matrix}\right\vert=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

$\displaystyle M(\mathbf{x},\mathbf{y})= \begin{bmatrix} 1 & x_1 & \ldots & x_1^... ...ots & \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

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

$\displaystyle y_i = y_1 p_1(x_i)+\cdots + y_{m+1} p_{m+1}(x_i),\; i=m+2,\ldots, n$