Interpolation

From Algorithmist
Jump to: navigation, search

Interpolation is a method of constructing new data points from a discrete set of known data points.

The most important type of interpolation is polynomial interpolation. Given a set of n+1 data points (x_{i},y_{i}) (for i=0..n), where no two x_{i} are the same, one is looking for a polynomial P(x) of degree at most n, satisfying P(x_{i})=y_{i} for i=0..n. It is known, that such a polynomial always exists and is unique.

There are several methods to find this polynomial, the simplest one is Lagrange form of interpolating polynomial:

P(x)=\sum _{{i=0}}^{n}y_{i}\prod _{{j=0,j\neq i}}^{n}{\frac  {x-x_{j}}{x_{i}-x_{j}}}

When you know, that a certain function is a polynomial (as, for example, is the case in many counting problems), you can reconstruct it from known values by the interpolating polynomial.