The Polynomial interpolation reference article from the English Wikipedia on 24-Apr-2004 (provided by Fixed Reference: snapshots of Wikipedia from wikipedia.org)

Polynomial interpolation

Polynomial interpolation is the act of fitting a polynomial to a given function with defined values in certain discrete data points. This "function" may actually be any discrete data (such as obtained by sampling), but it is generally assumed that such data may be described by a function. Polynomial interpolation is an area of inquiry in numerical analysis.

Table of contents

1 Fitting a polynomial to given data points 2 Non-Vandermonde solutions 3 The Error of polynomial interpolation 4 Disadvantages of polynomial interpolation 5 Related concepts

Fitting a polynomial to given data points

We want to determine a ploynomial of degree n that interpolates some given data set

From the amount of information obtained from the data set, we see that we cannot fit a polynomial of greater degree than j, so we assume that n = j and:

If we put all these conditions in a matrix-vector combination, with the coefficients n_j as unknowns, we obtain the system:

where the leftmost matrix is commonly referred to as a vandermonde matrix, so named after the mathematician Alexandre-Théophile Vandermonde. This equation may be solved either by hand or by machine using for example Gaussian elimination. It can be proved that given n + 1 mutually different (i.e. no two the same) t_i:s, there is only one unique nth-degree polynomial p that solves this interpolation task. This is called the unisolvence theorem.

Non-Vandermonde solutions

Solving the vandermonde matrix is (mostly) a costly operation (as counted in clock cycles of a computer trying to do the job). Therefore, several other clever ways of constructing the unique polynomial have been devised:

• Newton polynomials
• Lagrange polynomials
• Bernstein polynomials

The Error of polynomial interpolation

To be written

Disadvantages of polynomial interpolation

When the interpolation polynomial reaches a certain degree, it will tend to oscillate wildly in the undetermined areas. This is called Runge's phenomenon. Even though these problems can be partially avoided by using for example Chebyshev polynomials, the solution that is generally preferred in practice is to use several polynomials of a lower degree, connected in chains. These are called splines.

Related concepts

Using harmonic functions to interpolate a periodic function is usually done using Fourier series, for example in discrete Fourier transform. This can be seen as a form of polynomial interpolation with harmonic base functions.

This is the "Polynomial interpolation" reference article from the English Wikipedia. All text is available under the terms of the GNU Free Documentation License. See also our Disclaimer.