In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. In other words, given some data points (such as obtained by sampling), the aim is to find a polynomial which goes exactly through these points. Euclid, detail from The School of Athens by Raphael. ... Numerical analysis is the study of algorithms for the problems of continuous mathematics (as distinguished from discrete mathematics). ... In the mathematical subfield of numerical analysis, interpolation is a method of constructing new data points from a discrete set of known data points. ... In mathematics, a polynomial is an expression in which constants and powers of variables are combined using (only) addition, subtraction, and multiplication. ... Sampling is that part of statistical practice concerned with the selection of individual observations intended to yield some knowledge about a population of concern, especially for the purposes of statistical inference. ...

Applications

Polynomials can be used to approximate more complicated curves, for example, the shapes of letters in typography, given a few points. A related application is the evaluation of the natural logarithm and trigonometric functions: pick a few known data points, create a lookup table, and interpolate between those data points. This results in significantly faster computations. Polynomial interpolation also forms the basis for algorithms in numerical quadrature and numerical ordinary differential equations. This article or section is in need of attention from an expert on the subject. ... The natural logarithm is the logarithm to the base e, where e is equal to 2. ... In mathematics, the trigonometric functions are functions of an angle, important when studying triangles and modeling periodic phenomena. ... In computer science, a lookup table is a data structure, usually an array or associative array, used to replace a runtime computation with a simpler lookup operation. ... In numerical analysis, numerical integration constitutes a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also sometimes used to describe the numerical solution of differential equations. ... Numerical ordinary differential equations is the part of numerical analysis which studies the numerical solution of ordinary differential equations (ODEs). ...

Polynomial interpolation is also essential to perform sub-quadratic multiplication and squaring such as the Karatsuba multiplication where an interpolation through points on a polynomial which defines the product yields the product itself. For example, given a = f(x) = a₀x⁰ + a₁x¹ + ... and b = g(x) = b₀x⁰ + b₁x¹ + ... then the product ab is equivalent to W(x) = f(x)g(x). Finding points along W(x) by substituting x for small values in f(x) and g(x) yields points on the curve. Interpolation based on those points will yield the terms of W(x) and subsequently the product ab. In the case of Karatsuba multiplication this technique is substantially faster than quadratic multiplication for modest sized inputs. This is especially true when implemented in parallel hardware. A multiplication algorithm is an algorithm (or method) to multiply two numbers. ...

Definition

Given a set of n+1 data points (x_i,y_i) where no two x_i are the same, one is looking for a polynomial p of degree at most n with the property

The unisolvence theorem states that such a polynomial p exists and is unique.

To phrase it in terms of linear algebra: For n+1 interpolation nodes there exists a vector space isomorphism Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear transformations, and systems of linear equations in finite dimensions. ... Vector spaces (or linear spaces) are spaces whose elements, known as vectors, can be scaled and added; all linear combinations can be formed. ... In mathematics, an isomorphism (in Greek isos = equal and morphe = shape) is a kind of mapping between objects, devised by Eilhard Mitscherlich, which shows a relation between two properties or operations. ...

where Π_n is the vector space of polynomials with degree n.

Constructing the interpolation polynomial

The red dots denote the data points (x_k,y_k), while the blue curve shows the interpolation polynomial.

Suppose that the interpolation polynomial is in the form This plot illustrates polynomial interpolation. ...

The statement that p interpolates the data points means that

If we substitute equation (1) in here, we get a system of linear equations in the coefficients a_k. The system in matrix-vector form reads In mathematics and linear algebra, a system of linear equations is a set of linear equations such as 3x1 + 2x2 − x3 = 1 2x1 − 2x2 + 4x3 = −2 −x1 + ½x2 − x3 = 0. ...

We have to solve this system for a_k to construct the interpolant p(x).

The matrix on the left is commonly referred to as a Vandermonde matrix. Its determinant is nonzero, which proves the unisolvence theorem: there exists a unique interpolating polynomial. In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with a geometric progression in each row, i. ... In algebra, a determinant is a function depending on n that associates a scalar det(A) to every n×n square matrix A. The fundamental geometric meaning of a determinant is as the scale factor for volume when A is regarded as a linear transformation. ...

Non-Vandermonde solutions

We are trying to construct our unique interpolation polynomial in the vector space Π_n that is the vector space of polynomials of degree n. When using a monomial basis for Π_n we have to solve the Vandermonde matrix to construct the coefficients a_k for the interpolation polynomial. This can be a very costly operation (as counted in clock cycles of a computer trying to do the job). By choosing another basis for Π_n we can simplify the calculation of the coefficients but then of course we have to do additional calculations when we want to express the interpolation polynomial in terms of a monomial basis. this article has been removed from wikipedia because it was useless. ... this article has been removed from wikipedia because it was useless. ...

One method is to write the interpolation polynomial in the Newton form and use the method of divided differences to construct the coefficients. The cost is O(n²) operations, while Gaussian elimination costs O(n³) operations. Furthermore, you only need to do a bit of extra work if an extra point is added to the data set, while for the other methods, you have to redo the whole computation. In the mathematical subfield of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is the interpolation polynomial for a given set of data points in the Newton form. ... In mathematics divided differences is a recursive division process. ... It has been suggested that Landau notation be merged into this article or section. ...

Another method is to use the Lagrange form of the interpolation polynomial. The resulting formula immediately shows that the interpolation polynomial exists under the conditions stated in the above theorem. In numerical analysis, a Lagrange polynomial, named after Joseph Louis Lagrange, is the interpolation polynomial for a given set of data points in the Lagrange form. ...

The Bernstein form was used in a constructive proof of the Weierstrass approximation theorem by Bernstein and has nowadays gained great importance in computer graphics in the form of Bezier curves. In the mathematical subfield of numerical analysis, a Bernstein polynomial, named after Sergei Natanovich Bernstein, is a polynomial in the Bernstein form, that is a linear combination of Bernstein basis polynomials. ... In mathematical analysis, the Weierstrass approximation theorem states that every continuous function defined on an interval [a,b] can be uniformly approximated as closely as desired by a polynomial function. ... Sergei Natanovich Bernstein (Russian: Сергей Натанович Бернштейн, sometimes Romanized as Bernshtein) (March 5, 1880 - October 26, 1968) was a Ukrainian mathematician who was born in Odessa, Ukraine and died in Moscow, USSR. His doctoral dissertation, submitted in 1904 to the Sorbonne, solved Hilberts nineteenth problem on the analytic solution of elliptic differential... In the mathematical subfield of numerical analysis a Bézier curve is a parametric curve important in computer graphics. ...

Interpolation error

When interpolating a given function f by a polynomial of degree n at the nodes x₀,...,x_n we get the error

where

is the notation for divided differences. When f is n+1 times continuously differentiable on the smallest interval I which contains the nodes x_i then we can write the error in the Lagrange form as In mathematics divided differences is a recursive division process. ...

for some ξ in I. Thus the remainder term in the Lagrange form of the Taylor theorem is a special case of interpolation error when all interpolation nodes x_i are identical. In calculus, Taylors theorem, named after the mathematician Brook Taylor, who stated it in 1712, gives the approximation of a differentiable function near a point by a polynomial whose coefficients depend only on the derivatives of the function at that point. ...

In the case of equally spaced interpolation nodes x_i = x₀ + ih, it follows that the interpolation error is O(hⁿ). However, this does not necessarily mean that the error goes to zero as n → ∞. In fact, the error may increase without bound near the ends of the interval [x₀,x_n]. This is called Runge's phenomenon. The red curve is the Runge function, the blue curve is a 5th-degree polynomial, while the green curve is a 9th-degree polynomial. ...

The above error bound suggests choosing the interpolation points x_i such that the product | ∏ (x − x_i) | is as small as possible. The Chebyshev nodes achieve this. In mathematics the Chebyshev polynomials, named after Pafnuty Chebyshev, are a sequence of orthogonal polynomials which are related to de Moivres formula and which are easily defined recursively, like Fibonacci or Lucas numbers. ...

Lebesgue constants

See the main article: Lebesgue constant.

We fix the interpolation nodes x₀, ..., x_n and an interval [a, b] containing all the interpolation nodes. The process of interpolation maps the function f to a polynomial p. This defines a mapping X from the space C([a, b]) of all continuous functions on [a, b] to itself. The map X is linear and it is a projection on the subspace Π_n of polynomials of degree n or less. In mathematics, the Lebesgue constants (depending on a set of nodes and of its size) give an idea of how good the interpolant of a function (at the given nodes) is in comparison with the best polynomial approximation of the function (the degree of the polynomials are obviously fixed). ... In linear algebra, a projection is a linear transformation P such that P2 = P, i. ...

The Lebesgue constant L is defined as the operator norm of X. One has (a special case of Lebesgue's lemma): In mathematics, the operator norm is a norm defined on the space of bounded operators between two Banach spaces. ... In mathematics, Lebesgues lemma is an important statement in approximation theory. ...

In other words, the interpolation polynomial is at most a factor (L+1) worse than the best possible approximation. This suggests that we look for a set of interpolation nodes that L small. In particular, we have for Chebyshev nodes:

We conclude again that Chebyshev nodes are a very good choice for polynomial interpolation, as the growth in n is exponential for equidistant nodes. However, those nodes are not optimal.

Convergence properties

It is natural to ask, for which classes of functions and for which interpolation nodes the sequence of interpolating polynomials converges to the interpolated function? Convergence may be understood in different ways, e.g. pointwise, uniform or in some integral norm. The aspects of uniform convergence are discussed below.

The following theorem seems to be a rather encouraging answer:

For any function f(x) continuous on an interval [a,b] there exists a table of nodes for which the sequence of interpolating polynomials p_n(x) converges to f(x) uniformly on [a,b].

Proof. It's clear that the sequence of polynomials of best approximation converges to f(x) uniformly (due to Weierstrass approximation theorem). Now we have only to show that each may be obtained by means of interpolation on certain nodes. But this is true due to a special property of polynomials of best approximation known from the Chebyshev alternation theorem. Specifically, we know that such polynomials should intersect f(x) at least n+1 times. Choosing the points of intersection as interpolation nodes we obtain the interpolating polynomial coinciding with the best approximation polynomial. In mathematical analysis, the Weierstrass approximation theorem states that every continuous function defined on an interval [a,b] can be uniformly approximated as closely as desired by a polynomial function. ...

The defect of this method, however, is that interpolation nodes should be calculated anew for each new function f(x), but the algorithm is hard to be implemented numerically. Does there exist a single table of nodes for which the sequence of interpolating polynomials converge to any continuous function f(x)? The answer is unfortunately negative as it is stated by the following theorem:

For any table of nodes there is a continuous function f(x) on an interval [a,b] for which the sequence of interpolating polynomials diverges on [a,b].

The proof essentially uses the lower bound estimation of the Lebesgue constant, which we defined above to be the operator norm of X_n (where X_n is the projection operator on Π_n). Now we seek a table of nodes for which

for any

Due to the Banach-Steinhaus theorem, this is only possible when norms of X_n are uniformly bounded, which cannot be true since we know that In mathematics, the uniform boundedness principle (sometimes known as the Banach-Steinhaus Theorem) is one of the fundamental results of functional analysis. ...

For example, if equidistant points are chosen as interpolation nodes, the function from Runge's phenomenon demonstrates divergence of such interpolation. Note that this function is not only continuous but even infinitely times differentiable on [−1, 1]. For better Chebyshev nodes, however, such an example is much harder to find because of the theorem: The red curve is the Runge function, the blue curve is a 5th-degree polynomial, while the green curve is a 9th-degree polynomial. ... In the mathematical subfield of numerical analysis Chebyshev nodes are the roots of the Chebyshev polynomial of the first kind. ...

For every absolutely continuous function on [−1, 1] the sequence of interpolating polynomials constructed on Chebyshev nodes converges to f(x) uniformly.

Absolute continuity of real functions In mathematics, a real-valued function f of a real variable is absolutely continuous if for every positive number ε, no matter how small, there is a positive number δ small enough so that whenever a sequence of pairwise disjoint intervals [xk, yk], k = 1, ..., n satisfies...

Related concepts

Runge's phenomenon shows that for high values of n, the interpolation polynomial may oscillate wildly between the data points. This problem is commonly resolved by the use of spline interpolation. Here, the interpolant is not a polynomial but a spline: a chain of several polynomials of a lower degree. In the mathematical subfield of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. ... In the mathematical subfield of numerical analysis a spline is a special function defined piecewise by polynomials. ...

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, see trigonometric interpolation and trigonometric polynomial. Harmonic analysis is the branch of mathematics which studies the representation of functions or signals as the superposition of basic waves. ... In mathematics, a periodic function is a function that repeats its values after some definite period has been added to its independent variable. ... Fourier series are a mathematical technique for analyzing an arbitrary periodic function by decomposing the function into a sum of much simpler sinusoidal component functions, which differ from each other only in amplitude and frequency. ... In mathematics, the discrete Fourier transform (DFT), sometimes called the finite Fourier transform, is a Fourier transform widely employed in signal processing and related fields to analyze the frequencies contained in a sampled signal, solve partial differential equations, and to perform other operations such as convolutions. ... In the mathematical subfield of numerical analysis, trigonometric interpolation is a special form of interpolation on the unit circle in the complex plane using trigonometric polynomials. ... In the mathematical subfield of numerical analysis, a trigonometric polynomial is a finite linear linear combination of sin(nx) and cos(nx) with n a natural number. ...

Hermite interpolation problems are those where not only the values of the polynomial p are given, but also some derivatives. Birkhoff interpolation is the generalization which allows for some derivatives to be given, without specifying the values of p themselves. Hermite interpolation is a method closely related to the Newton divided difference method of interpolation in numerical analysis, that allows us to consider given derivatives at data points, as well as the data points themselves. ... In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. ...

References

• Kendell A. Atkinson (1988). An Introduction to Numerical Analysis (2nd ed.), Chapter 3. John Wiley and Sons. ISBN 0-471-50023-2
• L. Brutman (1997), Lebesgue functions for polynomial interpolation — a survey, Ann. Numer. Math. 4, 111–127.
• M.J.D. Powell (1981). Approximation Theory and Method, Chapter 4. Cambridge University Press. ISBN 0-521-29514-9.
• Michelle Schatzman (2002). Numerical Analysis: A Mathematical Introduction, Chapter 4. Clarendon Press, Oxford. ISBN 0-19-850279-6.
• Endre Süli and David Mayers (2003). An Introduction to Numerical Analysis, Chapter 6. Cambridge University Press. ISBN 0-521-00794-1.