Birkhoff interpolation

In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial ${\displaystyle P(x)}$ of degree ${\displaystyle d}$ such that only 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 ${\displaystyle 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.^[1]

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 P(x)}$ such that ${\displaystyle P(-1)=P(1)=0}$ and ${\displaystyle P^{(1)}(0)=1}$. On the other hand, the Birkhoff interpolation problem where the values of ${\displaystyle P^{(1)}(-1),P(0)}$ and ${\displaystyle P^{(1)}(1)}$ are given always has a unique solution.^[2]

An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. Schoenberg^[3] formulates the problem as follows. Let ${\displaystyle d}$ denote the number of conditions (as above) and let ${\displaystyle k}$ be the number of interpolation points. Given a ${\displaystyle d\times k}$ matrix ${\displaystyle E}$, all of whose entries are either ${\displaystyle 0}$ or ${\displaystyle 1}$, such that exactly ${\displaystyle d}$ entries are ${\displaystyle 1}$, then the corresponding problem is to determine ${\displaystyle P(x)}$ such that

${\displaystyle P^{(j)}(x_{i})=y_{i,j}\qquad \forall (i,j)/e_{ij}=1}$

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

${\displaystyle {\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 ${\displaystyle E}$ have a unique solution for any choice of the interpolation points?

The case with ${\displaystyle k=2}$ interpolation points was tackled by George Pólya in 1931.^[4] Let ${\displaystyle S_{m}}$ denote the sum of the entries in the first ${\displaystyle 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 ${\displaystyle k=2}$ has a unique solution if and only if ${\displaystyle S_{m}\geqslant m\quad \forall m}$. Schoenberg showed that this is a necessary condition for all values of ${\displaystyle k}$.

Some examples

Consider a differentiable function ${\displaystyle f(x)}$ on ${\displaystyle [a,b]}$, such that ${\displaystyle f(a)=f(b)}$. Let us see that there is no Birkhoff interpolation quadratic polynomial such that ${\displaystyle P^{(1)}(c)=f^{(1)}(c)}$ where ${\displaystyle c={\frac {a+b}{2}}}$: Since ${\displaystyle f(a)=f(b)}$, one may write the polynomial as ${\displaystyle P(x)=A(x-c)^{2}+B}$ (by completing the square) where ${\displaystyle A,B}$ are merely the interpolation coefficients. The derivative of the interpolation polynomial is given by ${\displaystyle P^{(1)}(x)=2A(x-c)^{2}}$. This implies ${\displaystyle P^{(1)}(c)=0}$, however this is absurd, since ${\displaystyle f^{(1)}(c)}$ is not necessarily ${\displaystyle 0}$. The incidence matrix is given by:

${\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\1&0&0\end{pmatrix}}_{3\times 3}}$

Consider a differentiable function ${\displaystyle f(x)}$ on ${\displaystyle [a,b]}$, and denote ${\displaystyle x_{0}=a,x_{2}=b}$ with ${\displaystyle x_{1}\in [a,b]}$. Let us see that there is indeed Birkhoff interpolation quadratic polynomial such that ${\displaystyle P(x_{1})=f(x_{1})}$ and ${\displaystyle P^{(1)}(x_{0})=f^{(1)}(x_{0}),P^{(1)}(x_{2})=f^{(1)}(x_{2})}$. Construct the interpolating polynomial of ${\displaystyle f^{(1)}(x)}$ at the nodes ${\displaystyle x_{0},x_{2}}$, such that ${\displaystyle \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 \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:

${\displaystyle {\begin{pmatrix}0&1&0\\1&0&0\\0&1&0\end{pmatrix}}_{3\times 3}}$

Given a natural number ${\displaystyle N}$, and a differentiable function ${\displaystyle f(x)}$ on ${\displaystyle [a,b]}$, is there a polynomial such that: ${\displaystyle P(x_{0})=f(x_{0})}$ and ${\displaystyle P^{(1)}(x_{i})=f^{(1)}(x_{i})}$ for ${\displaystyle i=1,\cdots ,N}$ with ${\displaystyle 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) ${\displaystyle P_{N-1}(x)}$ that satisfies ${\displaystyle P_{N-1}(x_{i})=f^{(1)}(x_{i})}$ for ${\displaystyle i=1,\cdots ,N}$, then the polynomial ${\displaystyle \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:

${\displaystyle {\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 ${\displaystyle N}$, and a ${\displaystyle 2N}$ differentiable function ${\displaystyle f(x)}$ on ${\displaystyle [a,b]}$, is there a polynomial such that: ${\displaystyle P^{(k)}(a)=f^{(k)}(a)}$ and ${\displaystyle P^{(k)}(b)=f^{(k)}(b)}$ for ${\displaystyle k=0,2,\cdots ,2N}$? Construct ${\displaystyle P_{1}(x)}$ as the interpolating polynomial of ${\displaystyle f(x)}$ at ${\displaystyle x=a}$ and ${\displaystyle x=b}$, such that ${\displaystyle P_{1}(x)={\frac {f^{(2N)}(b)-f^{(2N)}(a)}{b-a}}(x-a)+f^{(2N)}(a)}$. Define then the iterates ${\displaystyle \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 ${\displaystyle P_{2N+1}(x)}$ is the Birkhoff interpolating polynomial. The incidence matrix is given by:

${\displaystyle {\begin{pmatrix}1&0&1&0\cdots \\1&0&1&0\cdots \\\end{pmatrix}}_{2\times N}}$

References