In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial p of degree d such that certain derivatives have specified values at specified points:
where the data points
Existence and uniqueness of solutions
In contrast to Lagrange interpolation and Hermite interpolation, a Birkhoff interpolation problem does not always have a unique solution. For instance, there is no quadratic polynomial
An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. Schoenberg (1966) formulates the problem as follows. Let d denote the number of conditions (as above) and let k be the number of interpolation points. Given a d-by-k matrix E, all of whose entries are either 0 or 1, such that exactly d entries are 1, then the corresponding problem is to determine p such that
The matrix E is called the incidence matrix. For example, the incidence matrices for the interpolation problems mentioned in the previous paragraph are:
Now the question is: does a Birkhoff interpolation problem with a given incidence matrix have a unique solution for any choice of the interpolation points?
The case with k = 2 interpolation points was tackled by Pólya (1931). Let Sm denote the sum of the entries in the first m columns of the incidence matrix:
Then the Birkhoff interpolation problem with k = 2 has a unique solution if and only if Sm ≥ m for all m. Schoenberg (1966) showed that this is a necessary condition for all values of k.