Birkhoff interpolation

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:

${\displaystyle p^{(n_{i})}(x_{i})=y_{i}\qquad {\mbox{for }}i=1,\ldots ,d,}$

where the data points ${\displaystyle (x_{i},y_{i})}$ and the nonnegative integers ${\displaystyle n_{i}}$ are given. It differs from Hermite interpolation in that it is possible to specify derivatives of p at some points without specifying the lower derivatives or the polynomial itself. The name refers to George David Birkhoff, who first studied the problem in Birkhoff (1906).

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 ${\displaystyle \textstyle p}$ such that ${\displaystyle \textstyle p(-1)=p(1)=0}$ and ${\displaystyle \textstyle p'(0)=1}$. On the other hand, the Birkhoff interpolation problem where the values of ${\displaystyle \textstyle p'(-1)}$, ${\displaystyle \textstyle p(0)}$ and ${\displaystyle \textstyle p'(1)}$ are given always has a unique solution (Passow 1983).

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

${\displaystyle p^{(j)}(x_{i})=y_{i,j}\qquad {\text{for all }}(i,j){\text{ with }}e_{ij}=1.}$

The matrix E is called the incidence matrix. For example, the incidence matrices for the interpolation problems mentioned in the previous paragraph are:

${\displaystyle {\begin{bmatrix}1&0&0\\0&1&0\\1&0&0\end{bmatrix}}\quad {\text{and}}\quad {\begin{bmatrix}0&1&0\\1&0&0\\0&1&0\end{bmatrix}}.}$

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 S_m denote the sum of the entries in the first m columns of the incidence matrix:

${\displaystyle S_{m}=\sum _{i=1}^{k}\sum _{j=1}^{m}e_{ij}.}$

Then the Birkhoff interpolation problem with k = 2 has a unique solution if and only if S_m ≥ m for all m. Schoenberg (1966) showed that this is a necessary condition for all values of k.

References

• Birkhoff, George David (1906), "General mean value and remainder theorems with applications to mechanical differentiation and quadrature", Transactions of the American Mathematical Society, American Mathematical Society, 7 (1): 107–136, doi:10.2307/1986339, ISSN 0002-9947, JSTOR 1986339.
• Passow, Eli (1983), "Book Review: Birkhoff interpolation by G. G. Lorentz, K. Jetter and S. D. Riemenschneider", American Mathematical Society. Bulletin. New Series, 9 (3): 348–351, doi:10.1090/S0273-0979-1983-15204-7, ISSN 0002-9904.
• Pólya, George (1931), "Bemerkung zur Interpolation und zur Naherungstheorie der Balkenbiegung", Journal of Applied Mathematics and Mechanics, 11: 445–449, doi:10.1002/zamm.19310110620, ISSN 0044-2267.
• Schoenberg, Isaac Jacob (1966), "On Hermite-Birkhoff interpolation", Journal of Mathematical Analysis and Applications, 16: 538–543, doi:10.1016/0022-247X(66)90160-0, ISSN 0022-247X.