In numerical analysis, polynomial interpolation is the interpolation of a given bivariate data set by the polynomial of lowest possible degree that passes through the points of the dataset.
Given a set of data points , with no two the same, a polynomial function is said to interpolate the data if for each .
There is always a unique such polynomial, commonly given by two explicit formulas, the Lagrange polynomials and Newton polynomials.
Applications
The original use of interpolation polynomials was to approximate values of important transcendental functions such as natural logarithm and trigonometric functions. Starting with a few accurately computed data points, the corresponding interpolation polynomial will approximate the function at an arbitrary nearby point. Polynomial interpolation also forms the basis for algorithms in numerical quadrature (Simpson's rule) and numerical ordinary differential equations (multigrid methods).
In computer graphics, polynomials can be used to approximate complicated plane curves given a few specified points, for example the shapes of letters in typography. This is usually done with Bézier curves, which are a simple generalization of interpolation polynomials (having specified tangents as well as specified points).
In numerical analysis, polynomial interpolation is essential to perform sub-quadratic multiplication and squaring, such as Karatsuba multiplication and Toom–Cook multiplication, where interpolation through points on a product polynomial yields the specific product required. For example, given a = f(x) = a0x0 + a1x1 + ··· and b = g(x) = b0x0 + b1x1 + ···, the product ab is a specific value of W(x) = f(x)g(x). One may easily find points along W(x) at small values of x, and interpolation based on those points will yield the terms of W(x) and the specific product ab. As fomulated in Karatsuba multiplication, this technique is substantially faster than quadratic multiplication, even for modest-sized inputs, especially on parallel hardware.
In computer science, polynomial interpolation also leads to algorithms for secure multi party computation and secret sharing.
Interpolation theorem
For any bivariate data points , where no two are the same, there exists a unique polynomial of degree at most that interpolates these points, i.e. .
Equivalently, for a fixed choice of interpolation nodes , polynomial interpolation defines a linear bijection between the (n+1)-tuples of real-number values and the vector space of real polynomials of degree at most n:
This is a type of unisolvence theorem. The theorem is also valid over any infinite field in place of the real numbers , for example the rational or complex numbers.
First proof
Consider the Lagrange basis functions given by:
Notice that is a polynomial of degree , and we have for each , while . It follows that the linear combination:
has , so is an interpolating polynomial of degree .
To prove uniqueness, assume that there exists another interpolating polynomial of degree at most , so that for all . Then is a polynomial of degree at most which has distinct zeros (the ). But a non-zero polynomial of degree at most can have at most zeros, so must be the zero polynomial, i.e. .
Second proof
Write out the interpolation polynomial in the form
Substituting this into the interpolation equations , we get a system of linear equations in the coefficients , which reads in matrix-vector form as the following multiplication:
An interpolant corresponds to a solution of the above matrix equation . The matrix X on the left is a Vandermonde matrix, whose determinant is known to be which is non-zero since the nodes are all distinct. This ensures that the matrix is invertible and the equation has the unique solution ; that is, exists and is unique.
Corollary
If is a polynomial of degree at most , then the interpolating polynomial of at distinct points is itself.
Constructing the interpolation polynomial
The Vandermonde matrix in the second proof above may have large condition number, causing large errors when computing the coefficients 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 Lagrange polynomials: