From Algorithmist
Jump to navigation Jump to 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 data points (for i=0..n), where no two are the same, one is looking for a polynomial of degree at most , satisfying 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:

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.