# Birkhoff interpolation

In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial $P(x)$ of degree $d$ such that only certain derivatives have specified values at specified points:
    $P^{(n_{i})}(x_{i})=y_{i}\qquad {\mbox{for }}i=1,\ldots ,d,$
where the data points $(x_{i},y_{i})$ and the nonnegative integers $n_{i}$ are given. It differs from Hermite interpolation in that it is possible to specify derivatives of $P(x)$ 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 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 $P(x)$ such that $P(-1)=P(1)=0$ and $P^{(1)}(0)=1$. On the other hand, the Birkhoff interpolation problem where the values of $P^{(1)}(-1),P(0)$ and $P^{(1)}(1)$ are given always has a unique solution.
An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. Schoenberg 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\times 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(x)$ such that
    $P^{(j)}(x_{i})=y_{i,j}\qquad \forall (i,j)/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:
    ${\begin{pmatrix}1&0&0\\0&1&0\\1&0&0\end{pmatrix}}\qquad \mathrm {and} \qquad {\begin{pmatrix}0&1&0\\1&0&0\\0&1&0\end{pmatrix}}.$
Now the question is: Does a Birkhoff interpolation problem with a given incidence matrix $E$ have a unique solution for any choice of the interpolation points?
The case with $k=2$ interpolation points was tackled by George Pólya in 1931. Let $S_{m}$ denote the sum of the entries in the first $m$ columns of the incidence matrix:
    $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}\geqslant m\quad \forall m$. Schoenberg showed that this is a necessary condition for all values of $k$.

## Some examples

Consider a differentiable function $f(x)$ on $[a,b]$, such that $f(a)=f(b)$. Let us see that there is no Birkhoff interpolation quadratic polynomial such that $P^{(1)}(c)=f^{(1)}(c)$ where $c={\frac {a+b}{2}}$: Since $f(a)=f(b)$, one may write the polynomial as $P(x)=A(x-c)^{2}+B$ (by completing the square) where $A,B$ are merely the interpolation coefficients. The derivative of the interpolation polynomial is given by $P^{(1)}(x)=2A(x-c)^{2}$. This implies $P^{(1)}(c)=0$, however this is absurd, since $f^{(1)}(c)$ is not necessarily $0$. The incidence matrix is given by:
    ${\begin{pmatrix}1&0&0\\0&1&0\\1&0&0\end{pmatrix}}_{3\times 3}$
Consider a differentiable function $f(x)$ on $[a,b]$, and denote $x_{0}=a,x_{2}=b$ with $x_{1}\in [a,b]$. Let us see that there is indeed Birkhoff interpolation quadratic polynomial such that $P(x_{1})=f(x_{1})$ and $P^{(1)}(x_{0})=f^{(1)}(x_{0}),P^{(1)}(x_{2})=f^{(1)}(x_{2})$. Construct the interpolating polynomial of $f^{(1)}(x)$ at the nodes $x_{0},x_{2}$, such that $\displaystyle P_{1}(x)={\frac {f^{(1)}(x_{2})-f^{(1)}(x_{0})}{x_{2}-x_{0}}}(x-x_{0})+f^{(1)}(x_{0})$. Thus the polynomial : $\displaystyle P_{2}(x)=f(x_{1})+\int _{x_{1}}^{x}\!P_{1}(t)\;\mathrm {d} t$ is the Birkhoff interpolating polynomial. The incidence matrix is given by:
    ${\begin{pmatrix}0&1&0\\1&0&0\\0&1&0\end{pmatrix}}_{3\times 3}$
Given a natural number $N$, and a differentiable function $f(x)$ on $[a,b]$, is there a polynomial such that: $P(x_{0})=f(x_{0})$ and $P^{(1)}(x_{i})=f^{(1)}(x_{i})$ for $i=1,\cdots ,N$ with $x_{0},x_{1},\cdots ,x_{N}\in [a,b]$? Construct the Lagrange/Newton polynomial (same interpolating polynomial, different form to calculate and express them) $P_{N-1}(x)$ that satisfies $P_{N-1}(x_{i})=f^{(1)}(x_{i})$ for $i=1,\cdots ,N$, then the polynomial $\displaystyle P_{N}(x)=f(x_{0})+\int _{x_{0}}^{x}\!P_{N-1}(t)\;\mathrm {d} t$ is the Birkhoff interpolating polynomial satisfying the above conditions. The incidence matrix is given by:
    ${\begin{pmatrix}1&0&0&\cdots &0\\0&1&0&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\vdots \\0&1&0&\cdots &0\\\end{pmatrix}}_{N\times N}$
Given a natural number $N$, and a $2N$ differentiable function $f(x)$ on $[a,b]$, is there a polynomial such that: $P^{(k)}(a)=f^{(k)}(a)$ and $P^{(k)}(b)=f^{(k)}(b)$ for $k=0,2,\cdots ,2N$? Construct $P_{1}(x)$ as the interpolating polynomial of $f(x)$ at $x=a$ and $x=b$, such that $P_{1}(x)={\frac {f^{(2N)}(b)-f^{(2N)}(a)}{b-a}}(x-a)+f^{(2N)}(a)$. Define then the iterates $\displaystyle P_{k+2}(x)={\frac {f^{(2N-2k)}(b)-f^{(2N-2k)}(a)}{b-a}}(x-a)+f^{(2N-2k)}(a)+\int _{a}^{x}\!\int _{a}^{t}\!P_{k}(s)\;\mathrm {d} s\;\mathrm {d} t$ . Then $P_{2N+1}(x)$ is the Birkhoff interpolating polynomial. The incidence matrix is given by:
    ${\begin{pmatrix}1&0&1&0\cdots \\1&0&1&0\cdots \\\end{pmatrix}}_{2\times N}$