INTERPOLATING POLYNOMIAL

Definition

Given a set of n + 1 data points (xi, yi) where no two xi are the same, one is looking for a polynomial p of degree at most n with the property

 p(x_i) = y_i, \qquad i=0,\ldots,n.

The unisolvence theorem states that such a polynomial p exists and is unique, and can be proved by the Vandermode matrix, as described below.

The theorem states that for n + 1 interpolation nodes (xi), polynomial interpolation defines a linear bijection

 L_n:\mathbb{K}^{n+1} \to \Pi_n

where Πn is the vector space of polynomials (defined on any interval containing the nodes) of degree at most n.

 

Constructing the interpolation polynomial

The red dots denote the data points (xk, yk), while the blue curve shows the interpolation polynomial.

Suppose that the interpolation polynomial is in the form

p(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_2 x^2 + a_1 x + a_0. \qquad (1)

The statement that p interpolates the data points means that

p(x_i) = y_i \qquad\mbox{for all } i \in \left\{ 0, 1, \dots, n\right\}.

using equation (1)  here, we get a system of linear equations in the coefficients ak. The system in matrix-vector form reads

\begin{bmatrix} x_0^n & x_0^{n-1} & x_0^{n-2} & \ldots & x_0 & 1 \\ x_1^n & x_1^{n-1} & x_1^{n-2} & \ldots & x_1 & 1 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ x_n^n & x_n^{n-1} & x_n^{n-2} & \ldots & x_n & 1 \end{bmatrix} \begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_0 \end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix}.

We have to solve this system for ak to construct the interpolant p(x). The matrix on the left is commonly referred to as a Vandermode matrix The condition number of the Vandermonde matrix may be large, causing large errors when computing the coefficients ai if the system of equations is solved using Gaussian elimination

Several authors have therefore proposed algorithms which exploit the structure of the Vandermonde matrix to compute numerically stable solutions in O(n2) operations instead of the O(n3) required by Gaussian elimination. These methods rely on constructing first a Newton interpolation of the polynomial and then converting it to the monomial form above.

Alternatively, we may write down the polynomial immediately in terms of Langrage Polynomial

\begin{align} p(x) &= \frac{(x-x_1)(x-x_2)\cdots(x-x_n)}{(x_0-x_1)(x_0-x_2)\cdots(x_0-x_n)} y_0 + \frac{(x-x_0)(x-x_2)\cdots(x-x_n)}{(x_1-x_0)(x_1-x_2)\cdots(x_1-x_n)}y_1 +\ldots+\frac{(x-x_0)(x-x_1)\cdots(x-x_{n-1})}{(x_n-x_0)(x_n-x_1)\cdots(x_n-x_{n-1})}y_n \\ &=\sum_{i=0}^{n}\left ( \prod_{\stackrel{\!0\leq j\leq n}{j\neq i}}\frac{x-x_j}{x_i-x_j}\right ) y_i \end{align}