In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, polynomial interpolation is the
interpolation of a given
data set A data set (or dataset) is a collection of data. In the case of tabular data, a data set corresponds to one or more database tables, where every column of a table represents a particular variable, and each row corresponds to a given record of the ...
by the
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
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
.
Two common explicit formulas for this polynomial are the
Lagrange polynomials and
Newton polynomials In the mathematical field of numerical analysis, a Newton polynomial, named after its inventor Isaac Newton, is an interpolation polynomial for a given set of data points. The Newton polynomial is sometimes called Newton's divided differences inter ...
.
Applications
Polynomials can be used to approximate complicated curves, for example, the shapes of letters in
typography
Typography is the art and technique of arranging type to make written language legible, readable and appealing when displayed. The arrangement of type involves selecting typefaces, point sizes, line lengths, line-spacing ( leading), and ...
, given a few points. A relevant application is the evaluation of the
natural logarithm
The natural logarithm of a number is its logarithm to the base of the mathematical constant , which is an irrational and transcendental number approximately equal to . The natural logarithm of is generally written as , , or sometimes, if ...
and
trigonometric function
In mathematics, the trigonometric functions (also called circular functions, angle functions or goniometric functions) are real functions which relate an angle of a right-angled triangle to ratios of two side lengths. They are widely used in all ...
s: 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
In analysis, numerical integration comprises 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 ...
and
numerical ordinary differential equations and
Secure Multi Party Computation,
Secret Sharing
Secret sharing (also called secret splitting) refers to methods for distributing a secret among a group, in such a way that no individual holds any intelligible information about the secret, but when a sufficient number of individuals combine t ...
schemes.
Polynomial interpolation is also essential to perform sub-quadratic multiplication and squaring such as
Karatsuba multiplication
The Karatsuba algorithm is a fast multiplication algorithm. It was discovered by Anatoly Karatsuba in 1960 and published in 1962.
Knuth D.E. (1969) ''The Art of Computer Programming. v.2.'' Addison-Wesley Publ.Co., 724 pp.
It is a divi ...
and
Toom–Cook multiplication Toom–Cook, sometimes known as Toom-3, named after Andrei Toom, who introduced the new algorithm with its low complexity, and Stephen Cook, who cleaned the description of it, is a multiplication algorithm for large integers.
Given two large integ ...
, where an interpolation through points on a polynomial which defines the product yields the product itself. For example, given ''a'' = ''f''(''x'') = ''a''
0''x''
0 + ''a''
1''x''
1 + ... and ''b'' = ''g''(''x'') = ''b''
0''x''
0 + ''b''
1''x''
1 + ..., 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, even for modest-sized inputs. This is especially true when implemented in parallel hardware.
Interpolation theorem
There exists a unique polynomial of degree at most
that interpolates the
data points
, where no two
are the same.
Equivalently, for a fixed choice of interpolation nodes
, polynomial interpolation defines a linear
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
between the n-tuples of real-number values
and the
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called ''vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but can ...
of real polynomials of degree at most :
:
This is a type of
unisolvence theorem. The theorem is also valid over any infinite
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
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
. Furthermore, for each
we have
, where
is the
Kronecker delta
In mathematics, the Kronecker delta (named after Leopold Kronecker) is a function of two variables, usually just non-negative integers. The function is 1 if the variables are equal, and 0 otherwise:
\delta_ = \begin
0 &\text i \neq j, \\
1 &\ ...
. It follows that the linear combination
:
is an interpolating polynomial of degree
.
To prove uniqueness, assume that there exists another interpolating polynomial
of degree at most
. Since
for all
, it follows that the polynomial
has
distinct zeros. However,
is of degree at most
and, by the
fundamental theorem of algebra
The fundamental theorem of algebra, also known as d'Alembert's theorem, or the d'Alembert–Gauss theorem, states that every non- constant single-variable polynomial with complex coefficients has at least one complex root. This includes polynomia ...
, can have at most
zeros; therefore,
.
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
Multiplication (often denoted by the cross symbol , by the mid-line dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four elementary mathematical operations of arithmetic, with the other ones being additi ...
:
:
An interpollant
corresponds to a solution
of the above matrix equation
. The matrix ''X'' on the left is a
Vandermonde matrix
In linear algebra, a Vandermonde matrix, named after Alexandre-Théophile Vandermonde, is a matrix with the terms of a geometric progression in each row: an matrix
:V=\begin
1 & x_1 & x_1^2 & \dots & x_1^\\
1 & x_2 & x_2^2 & \dots & x_2^\\
1 & x_3 ...
, whose determinant is known to be
which is non-zero since the nodes
are all distinct. This ensures that the matrix is
invertible
In mathematics, the concept of an inverse element generalises the concepts of opposite () and reciprocal () of numbers.
Given an operation denoted here , and an identity element denoted , if , one says that is a left inverse of , and that is ...
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
![Interpolation example polynomial](https://upload.wikimedia.org/wikipedia/commons/4/41/Interpolation_example_polynomial.svg)
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
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of operations performed on the corresponding matrix of coefficients. This method can also be used ...
.
Several authors have therefore proposed algorithms which exploit the structure of the Vandermonde matrix to compute numerically stable solutions in O(''n''
2) operations instead of the O(''n''
3) required by Gaussian elimination. These methods rely on constructing first a
Newton interpolation of the polynomial and then converting it to the
monomial form
In mathematics the monomial basis of a polynomial ring is its basis (as a vector space or free module over the field or ring of coefficients) that consists of all monomials. The monomials form a basis because every polynomial may be uniquely wr ...
above.
Alternatively, we may write down the polynomial immediately in terms of
Lagrange polynomial
In numerical analysis, the Lagrange interpolating polynomial is the unique polynomial of lowest degree of a polynomial, degree that polynomial interpolation, interpolates a given set of data.
Given a data set of graph of a function, coordinate p ...
s:
:
For matrix arguments, this formula is called
Sylvester's formula In matrix theory, Sylvester's formula or Sylvester's matrix theorem (named after J. J. Sylvester) or Lagrange−Sylvester interpolation expresses an analytic function of a matrix as a polynomial in , in terms of the eigenvalues and eigenvectors ...
and the matrix-valued Lagrange polynomials are the
Frobenius covariant In matrix theory, the Frobenius covariants of a square matrix are special polynomials of it, namely projection matrices ''A'i'' associated with the eigenvalues and eigenvectors of .Roger A. Horn and Charles R. Johnson (1991), ''Topics in Ma ...
s.
Non-Vandermonde solutions
We are trying to construct our unique interpolation polynomial in the vector space Π
''n'' of polynomials of degree . When using a
monomial basis for Π
''n'' we have to solve the Vandermonde matrix to construct the coefficients 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 we have to do additional calculations when we want to express the interpolation polynomial in terms of a
monomial basis.
One method is to write the interpolation polynomial in the
Newton form and use the method of
divided differences
In mathematics, divided differences is an algorithm, historically used for computing tables of logarithms and trigonometric functions. Charles Babbage's difference engine, an early mechanical calculator, was designed to use this algorithm in its o ...
to construct the coefficients, e.g.
Neville's algorithm In mathematics, Neville's algorithm is an algorithm used for polynomial interpolation that was derived by the mathematician Eric Harold Neville in 1934. Given ''n'' + 1 points, there is a unique polynomial of degree ''≤ n'' which goes through the ...
. The cost is
O(''n''2) operations, while Gaussian elimination costs O(''n''
3) operations. Furthermore, you only need to do O(''n'') extra work if an extra point is added to the data set, while for the other methods, you have to redo the whole computation.
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. Lagrange formula is to be preferred to Vandermonde formula when we are not interested in computing the coefficients of the polynomial, but in computing the value of ''p''(''x'') in a given ''x'' not in the original data set. In this case, we can reduce complexity to O(''n''
2).
The
Bernstein form was used in a constructive proof of the
Weierstrass approximation theorem
Karl Theodor Wilhelm Weierstrass (german: link=no, Weierstraß ; 31 October 1815 – 19 February 1897) was a German mathematician often cited as the "father of modern analysis". Despite leaving university without a degree, he studied mathematics ...
by
Bernstein
Bernstein is a common surname in the German language, meaning "amber" (literally "burn stone"). The name is used by both Germans and Jews, although it is most common among people of Ashkenazi Jewish heritage. The German pronunciation is , but in E ...
and has gained great importance in computer graphics in the form of
Bézier curves.
Linear combination of the given values
The
Lagrange form of the interpolating polynomial is a linear combination of the given values. In many scenarios, an efficient and convenient polynomial interpolation is a linear combination of the given values, using previously known coefficients. Given a set of
data points
where each data point is a (position, value) pair and where no two positions
are the same, the interpolation polynomial in the Lagrange form is a
linear combination
:
of the given values
with each coefficient
given by evaluating the corresponding Lagrange basis polynomial using the given
positions
.
:
Each coefficient
in the linear combination depends on the given positions
and the desired position
, but not on the given values
. For each coefficient, inserting the values of the given positions
and simplifying yields an expression
, which depends only on
. Thus the same coefficient expressions
can be used in a polynomial interpolation of a given second set of
data points
at the same given positions
, where the second given values
differ from the first given values
. Using the same coefficient expressions
as for the first set of data points, the interpolation polynomial of the second set of data points is the linear combination
:
For each coefficient
in the linear combination, the expression resulting from the Lagrange basis polynomial
only depends on the relative spaces between the given positions, not on the individual value of any position. Thus the same coefficient expressions
can be used in a polynomial interpolation of a given third set of
data points
:
where each position
is related to the corresponding position
in the first set by
and the desired positions are related by
, for a constant scaling factor ''a'' and a constant shift ''b'' for all positions. Using the same coefficient expressions
as for the first set of data points, the interpolation polynomial of the third set of data points is the linear combination
:
In many applications of polynomial interpolation, the given set of
data points is at equally spaced positions. In this case, it can be convenient to define the ''x''-axis of the positions such that
. For example, a given set of 3 equally-spaced data points
is then
.
The interpolation polynomial in the Lagrange form is the
linear combination
:
This quadratic interpolation is valid for any position ''x'', near or far from the given positions. So, given 3 equally-spaced data points at
defining a quadratic polynomial, at an example desired position
, the interpolated value after simplification is given by
This is a quadratic interpolation typically used in the Multigrid method. Again given 3 equally-spaced data points at
defining a quadratic polynomial, at the next equally spaced position
, the interpolated value after simplification is given by
:
In the above polynomial interpolations using a linear combination of the given values, the coefficients were determined using the Lagrange method. In some scenarios, the coefficients can be more easily determined using other methods. Examples follow.
According to the
method of finite differences, for any polynomial of degree ''d'' or less, any sequence of
values at equally spaced positions has a
th difference exactly equal to 0. The element ''s''
''d+1'' of the
Binomial transform In combinatorics, the binomial transform is a sequence transformation (i.e., a transform of a sequence) that computes its forward differences. It is closely related to the Euler transform, which is the result of applying the binomial transform to t ...
is such a
th difference. This area is surveyed here. The
binomial transform In combinatorics, the binomial transform is a sequence transformation (i.e., a transform of a sequence) that computes its forward differences. It is closely related to the Euler transform, which is the result of applying the binomial transform to t ...
, ''T'', of a sequence of values , is the sequence defined by
:
Ignoring the sign term
, the
coefficients of the element ''s''
''n'' are the respective
elements of the row ''n'' of Pascal's Triangle. The
triangle of binomial transform coefficients is like Pascal's triangle. The entry in the ''n''th row and ''k''th column of the BTC triangle is
for any non-negative integer ''n'' and any integer ''k'' between 0 and ''n''. This results in the following example rows ''n'' =
0 through ''n'' = 7, top to bottom, for the BTC triangle:
For convenience, each row ''n'' of the above example BTC triangle also has a label
. Thus for any polynomial of degree ''d'' or less, any sequence of
values at equally spaced positions has a
linear combination result of 0, when using the
elements of row ''d'' as the corresponding linear coefficients.
For example, 4 equally spaced data points of a quadratic polynomial obey the
linear equation given by row
of the BTC triangle.
This is the same linear equation as obtained above using the Lagrange method.
The BTC triangle can also be used to derive other polynomial interpolations. For example, the above quadratic interpolation
:
can be derived in 3 simple steps as follows. The equally spaced points of a quadratic polynomial obey the rows of the BTC triangle with
or higher. First, the row
spans the given and desired data points
with the linear equation
:
Second, the unwanted data point
is replaced by an expression in terms of wanted data points. The row
provides a linear equation with a term
, which results in a term
by multiplying both sides of the linear equation by 4.
Third, the above two linear equations are added to yield a linear equation equivalent to the above quadratic interpolation for
.
Similar to other uses of linear equations, the above derivation scales and adds vectors of coefficients. In polynomial interpolation as a linear combination of values, the elements of a vector correspond to a contiguous sequence of regularly spaced positions. The ''p'' non-zero elements of a vector are the ''p'' coefficients in a linear equation obeyed by any sequence of ''p'' data points from any degree ''d'' polynomial on any regularly spaced grid, where ''d'' is noted by the subscript of the vector. For any vector of coefficients, the subscript obeys
. When adding vectors with various subscript values, the lowest subscript applies for the resulting vector. So, starting with the vector of row
and the vector of row
of the BTC triangle, the above quadratic interpolation for
is derived by the vector calculation
:
Similarly, the cubic interpolation typical in the
Multigrid method In numerical analysis, a multigrid method (MG method) is an algorithm for solving differential equations using a hierarchy of discretizations. They are an example of a class of techniques called multiresolution methods, very useful in problems exhi ...
,
:
can be derived by a vector calculation starting with the vector of row
and the vector of row
of the BTC triangle.
:
Interpolation error
When interpolating a given function ''f'' by a polynomial of degree at the nodes ''x''
0,...,''x''
''n'' we get the error
:
where
: