Interpolation

What is it?

There are many cases where we have discrete data points and we want to estimate or predict the values at other points.  Interpolation constructs a polynomial from the data points provided, which passes through all data points and attempts to describe the behavior in between data points (and beyond them).  From two points we can construct a unique line, and from three points a unique parabola.  In general, the polynomial constructed from N+1 points will have degree N.  The polynomial created from these points is unique (to polynomial interpolation), such that all polynomial interpolation methods will output the same function.

What do we use it for?

Interpolation, especially polynomial interpolation, is useful when we have discrete data points and want to say something about a behavior or property where the data is not defined.  Polynomial interpolation is one of multiple forms of interpolation.  Spline interpolation is piecewise polynomial interpolation using small power polynomials, to reduce errors found using high order polynomials.

What’s this about a unique interpolating polynomial?

All methods that generate a single polynomial that interpolates n+1 data points must be the same.  This is important, because the Vandermonde matrix method, the Lagrange method, and Newton’s divided difference method will all solve the same polynomial.  The difference then is in their implementations and format constraints (ie. inverting larger and larger matrices with Vandermonde, etc).  A succinct proof of the interpolating polynomial’s uniqueness can be found at this Wikipedia page, whose shortened argument is presented below:

For n+1 data points, let p(x) and q(x) be different polynomials, both of degree n, which interpolate the n+1 data points.  Say r(x) = p(x)-q(x) .  Then:

r(x_i) = p(x_i)-q(x_i) \text{ } \forall_{i \in 0,1,...,n}

But then r(x) has n+1 roots, so has degree n+1, not degree n.  Thus for r(x) = p(x)-q(x) to hold, r(x) = 0 .  So p(x) = q(x) and the polynomial is unique.

What are some methods we use?

Vandermonde Matrices

By expressing the data points as functions, we can create a coefficient matrix A with corresponding B values, and solve Ax = B for x.  The data point (x_n, f(x_n)) is represented by the nth row of A.  Vandermonde matrices can easily be ill conditioned, allowing instability.  Matrix inversion is a rather costly operation, restrictively so as A grows large.

\begin{bmatrix}1 & x_0 & x_0^2 & x_0^3 \\ 1 & x_1 & x_1^2 & x_1^3 \\1 & x_2 & x_2^2 & x_2^3 \\1 & x_3 & x_3^2 & x_3^3 \\ \end{bmatrix} \begin{bmatrix}c_0 \\ c_1 \\ c_2 \\ c_3 \\ \end{bmatrix} = \begin{bmatrix}f(x_0) \\ f(x_1) \\ f(x_2) \\ f(x_3) \\ \end{bmatrix}

Lagrange Interpolation

Because of how we construct Lagrange basis polynomials, they are always well-defined.  Remember, though, that any polynomial interpolation method must result in the same equation.  The advantage of the Lagrange interpolation method is its non-reliance on matrix inversion (which can fail due to vanishing determinants).

Newton’s Divided Differences

Newton’s Divided Differences method creates a lower triangular matrix by using the Newton basis, allowing us to solve the triangle very quickly.  (This again results in the same interpolation polynomial)  A recursive solver can be applied to each row of the triangle, by recognizing the relationship of the divided differences f[x_0,x_1,...,x_n] in the equation below.

N(x) = \begin{array}{l}f[x_0] + f[x_0,x_1](x-x_0) + ... + f[x_0,x_1,...,x_n](x-x_0)(x-x_1)\cdots(x-x_n) \end{array}

Cubic Splines

Spline interpolation uses piecewise polynomial interpolation over a set of data points.  The error seen with higher order polynomial interpolation can be reduced by using multiple low-order polynomial interpolations, provided that those pieces fit well together.

Leave a comment