Polynomial Interpolation

Vandermonde System

Learned in CS370.

So Vandermonde matrix is one of the ways to do Polynomial Interpolation using a monomial basis.

A vandermonde system is a linear system characterized by a Vandermonde matrix used for polynomial interpolation.

Using a vandermonde system, we compute the interpolating polynomial by reducing it down to solving a linear system of equations.

Monomial Basis

The familiar form $p(x)=c_1+c_{2}x+c_3{x}^2+c_4{x}^3+...+c_n{x}^{n-1}$ is called the monomial form, and can also be written $p(x)={\sum }_{i=1}^n{c}_i{x}^{i-1}$ The sequence $1,x,x^2,...$ is called the monomial basis.

Monomial form is a sum of coefficients $c_i$ times basis functions x^i$.

This is in contrast with the Lagrange Basis.

In general, if we had a set of data $(x_1,y_1),...,(x_n,y_n)$, and want a polynomial of the form (2.1.1) then we can set up the linear system V · c = y where

Matrices of the form V are called Vandermonde matrices. All of the data required for creating one is contained in its second column, i.e., Vi,2 = x_i.

These facts have both practical and theoretical implications.

• The theoretical implication is that we can prove the basic theorem by showing that $V$ is non-singular
• The practical implication is that we have reduced computing the interpolating polynomial to solving a linear system of equations.