5.1: Polynomial Interpolation

The $n+1$ points $\left(x_{0}, y_{0}\right),\left(x_{1}, y_{1}\right), \ldots,\left(x_{n}, y_{n}\right)$ can be interpolated by a unique polynomial of degree $n .$ When $n=1$, the polynomial is a linear function; when $n=2$, the polynomial is a quadratic function. There are three standard algorithms that can be used to construct this unique interpolating polynomial, and we will present all three here, not so much because they are all useful, but because it is interesting to learn how these three algorithms are constructed.

When discussing each algorithm, we define $P_{n}(x)$ to be the unique $n$th degree polynomial that passes through the given $n+1$ data points.

5.1.1. Vandermonde polynomial

This Vandermonde polynomial is the most straightforward construction of the interpolating polynomial $P_{n}(x)$. We simply write

$$P_{n}(x)=c_{0} x^{n}+c_{1} x^{n-1}+\cdots+c_{n} . \nonumber$$

Then we can immediately form $n+1$ linear equations for the $n+1$ unknown coefficients $c_{0}, c_{1}, \ldots, c_{n}$ using the $n+1$ known points:

$$\begin{gathered} y_{0}=c_{0} x_{0}^{n}+c_{1} x_{0}^{n-1}+\cdots+c_{n-1} x_{0}+c_{n} \\ y_{2}=c_{0} x_{1}^{n}+c_{1} x_{1}^{n-1}+\cdots+c_{n-1} x_{1}+c_{n} \\ \vdots \\ y_{n}=c_{0} x_{n}^{n}+c_{1} x_{n}^{n-1}+\cdots+c_{n-1} x_{n}+c_{n} \end{gathered} \nonumber$$

The system of equations in matrix form is

$$\left(\begin{array}{ccccc} x_{0}^{n} & x_{0}^{n-1} & \cdots & x_{0} & 1 \\ x_{1}^{n} & x_{1}^{n-1} & \cdots & x_{1} & 1 \\ \vdots & \vdots & \ddots & \vdots & \\ x_{n}^{n} & x_{n}^{n-1} & \cdots & x_{n} & 1 \end{array}\right)\left(\begin{array}{c} c_{0} \\ c_{1} \\ \vdots \\ c_{n} \end{array}\right)=\left(\begin{array}{c} y_{0} \\ y_{1} \\ \vdots \\ y_{n} \end{array}\right) \nonumber$$

The matrix is called the Vandermonde matrix, and can be constructed using the MATLAB function vander.m. The system of linear equations can be solved in MATLAB using the \operator, and the MATLAB function polyval.m can used to interpolate using the $c$ coefficients. I will illustrate this in class and place the code on the website.

5.1.2. Lagrange polynomial

The Lagrange polynomial is the most clever construction of the interpolating polynomial $P_{n}(x)$, and leads directly to an analytical formula. The Lagrange polynomial is the sum of $n+1$ terms and each term is itself a polynomial of degree $n$. The full polynomial is therefore of degree $n$. Counting from 0 , the $i$ th term of the Lagrange polynomial is constructed by requiring it to be zero at $x_{j}$ with $j \neq i$, and equal to $y_{i}$ when $j=i$. The polynomial can be written as

$$\begin{array}{r} P_{n}(x)=\dfrac{\left(x-x_{1}\right)\left(x-x_{2}\right) \cdots\left(x-x_{n}\right) y_{0}}{\left(x_{0}-x_{1}\right)\left(x_{0}-x_{2}\right) \cdots\left(x_{0}-x_{n}\right)}+\dfrac{\left(x-x_{0}\right)\left(x-x_{2}\right) \cdots\left(x-x_{n}\right) y_{1}}{\left(x_{1}-x_{0}\right)\left(x_{1}-x_{2}\right) \cdots\left(x_{1}-x_{n}\right)} \\ +\cdots+\dfrac{\left(x-x_{0}\right)\left(x-x_{1}\right) \cdots\left(x-x_{n-1}\right) y_{n}}{\left(x_{n}-x_{0}\right)\left(x_{n}-x_{1}\right) \cdots\left(x_{n}-x_{n-1}\right)} . \end{array} \nonumber$$

It can be clearly seen that the first term is equal to zero when $x=x_{1}, x_{2}, \ldots, x_{n}$ and equal to $y_{0}$ when $x=x_{0}$; the second term is equal to zero when $x=x_{0}, x_{2}, \ldots x_{n}$ and equal to $y_{1}$ when $x=x_{1}$; and the last term is equal to zero when $x=x_{0}, x_{1}, \ldots x_{n-1}$ and equal to $y_{n}$ when $x=x_{n}$. The uniqueness of the interpolating polynomial implies that the Lagrange polynomial must be the interpolating polynomial.

5.1.3. Newton polynomial

The Newton polynomial is somewhat more clever than the Vandermonde polynomial because it results in a system of linear equations that is lower triangular, and therefore can be solved by forward substitution. The interpolating polynomial is written in the form

$$P_{n}(x)=c_{0}+c_{1}\left(x-x_{0}\right)+c_{2}\left(x-x_{0}\right)\left(x-x_{1}\right)+\cdots+c_{n}\left(x-x_{0}\right) \cdots\left(x-x_{n-1}\right) \nonumber$$

which is clearly a polynomial of degree $n$. The $n+1$ unknown coefficients given by the $c^{\prime}$ s can be found by substituting the points $\left(x_{i}, y_{i}\right)$ for $i=0, \ldots, n$ :

$$\begin{aligned} y_{0} &=c_{0} \\ y_{1} &=c_{0}+c_{1}\left(x_{1}-x_{0}\right) \\ y_{2} &=c_{0}+c_{1}\left(x_{2}-x_{0}\right)+c_{2}\left(x_{2}-x_{0}\right)\left(x_{2}-x_{1}\right) \\ \vdots & \vdots \\ y_{n} &=c_{0}+c_{1}\left(x_{n}-x_{0}\right)+c_{2}\left(x_{n}-x_{0}\right)\left(x_{n}-x_{1}\right)+\cdots+c_{n}\left(x_{n}-x_{0}\right) \cdots\left(x_{n}-x_{n-1}\right) \end{aligned} \nonumber$$

This system of linear equations is lower triangular as can be seen from the matrix form

$$\left(\begin{array}{ccccc} 1 & 0 & 0 & \cdots & 0 \\ 1 & \left(x_{1}-x_{0}\right) & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \left(x_{n}-x_{0}\right) & \left(x_{n}-x_{0}\right)\left(x_{n}-x_{1}\right) & \cdots & \left(x_{n}-x_{0}\right) \cdots\left(x_{n}-x_{n-1}\right) \end{array}\right)\left(\begin{array}{c} c_{0} \\ c_{1} \\ \vdots \\ c_{n} \end{array}\right) \nonumber$$

and so theoretically can be solved faster than the Vandermonde polynomial. In practice, however, there is little difference because polynomial interpolation is only useful when the number of points to be interpolated is small.