5.1: Polynomial Interpolation
- Last updated
- May 31, 2022
- Save as PDF
( \newcommand{\kernel}{\mathrm{null}\,}\)
The n+1 points (x0,y0),(x1,y1),…,(xn,yn) 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 Pn(x) to be the unique nth 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 Pn(x). We simply write
Pn(x)=c0xn+c1xn−1+⋯+cn.
Then we can immediately form n+1 linear equations for the n+1 unknown coefficients c0,c1,…,cn using the n+1 known points:
y0=c0xn0+c1xn−10+⋯+cn−1x0+cny2=c0xn1+c1xn−11+⋯+cn−1x1+cn⋮yn=c0xnn+c1xn−1n+⋯+cn−1xn+cn
The system of equations in matrix form is
(xn0xn−10⋯x01xn1xn−11⋯x11⋮⋮⋱⋮xnnxn−1n⋯xn1)(c0c1⋮cn)=(y0y1⋮yn)
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 Pn(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 xj with j≠i, and equal to yi when j=i. The polynomial can be written as
Pn(x)=(x−x1)(x−x2)⋯(x−xn)y0(x0−x1)(x0−x2)⋯(x0−xn)+(x−x0)(x−x2)⋯(x−xn)y1(x1−x0)(x1−x2)⋯(x1−xn)+⋯+(x−x0)(x−x1)⋯(x−xn−1)yn(xn−x0)(xn−x1)⋯(xn−xn−1).
It can be clearly seen that the first term is equal to zero when x=x1,x2,…,xn and equal to y0 when x=x0; the second term is equal to zero when x=x0,x2,…xn and equal to y1 when x=x1; and the last term is equal to zero when x=x0,x1,…xn−1 and equal to yn when x=xn. 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
Pn(x)=c0+c1(x−x0)+c2(x−x0)(x−x1)+⋯+cn(x−x0)⋯(x−xn−1)
which is clearly a polynomial of degree n. The n+1 unknown coefficients given by the c′ s can be found by substituting the points (xi,yi) for i=0,…,n :
y0=c0y1=c0+c1(x1−x0)y2=c0+c1(x2−x0)+c2(x2−x0)(x2−x1)⋮⋮yn=c0+c1(xn−x0)+c2(xn−x0)(xn−x1)+⋯+cn(xn−x0)⋯(xn−xn−1)
This system of linear equations is lower triangular as can be seen from the matrix form
(100⋯01(x1−x0)0⋯0⋮⋮⋮⋱⋮1(xn−x0)(xn−x0)(xn−x1)⋯(xn−x0)⋯(xn−xn−1))(c0c1⋮cn)
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.
