Birkhoff interpolation

In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial ${\displaystyle P(x)}${\displaystyle P(x)} of degree ${\displaystyle d}${\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,}${\displaystyle P^{(n_{i})}(x_{i})=y_{i}\qquad {\mbox{for }}i=1,\ldots ,d,}

where the data points ${\displaystyle (x_{i},y_{i})}${\displaystyle (x_{i},y_{i})} and the nonnegative integers ${\displaystyle n_{i}}${\displaystyle n_{i}} are given. It differs from Hermite interpolation in that it is possible to specify derivatives of ${\displaystyle P(x)}${\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]

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)}${\displaystyle P(x)} such that ${\displaystyle P(-1)=P(1)=0}${\displaystyle P(-1)=P(1)=0} and ${\displaystyle P^{(1)}(0)=1}${\displaystyle P^{(1)}(0)=1}. On the other hand, the Birkhoff interpolation problem where the values of ${\displaystyle P^{(1)}(-1),P(0)}${\displaystyle P^{(1)}(-1),P(0)} and ${\displaystyle P^{(1)}(1)}${\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}${\displaystyle d} denote the number of conditions (as above) and let ${\displaystyle k}${\displaystyle k} be the number of interpolation points. Given a ${\displaystyle d\times k}${\displaystyle d\times k} matrix ${\displaystyle E}${\displaystyle E}, all of whose entries are either ${\displaystyle 0}${\displaystyle 0} or ${\displaystyle 1}${\displaystyle 1}, such that exactly ${\displaystyle d}${\displaystyle d} entries are ${\displaystyle 1}${\displaystyle 1}, then the corresponding problem is to determine ${\displaystyle P(x)}${\displaystyle P(x)} such that

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

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

The case with ${\displaystyle k=2}${\displaystyle k=2} interpolation points was tackled by George Pólya in 1931.^[4] Let ${\displaystyle S_{m}}${\displaystyle S_{m}} denote the sum of the entries in the first ${\displaystyle m}${\displaystyle m} columns of the incidence matrix:

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

Then the Birkhoff interpolation problem with ${\displaystyle k=2}${\displaystyle k=2} has a unique solution if and only if ${\displaystyle S_{m}\geqslant m\quad \forall m}${\displaystyle S_{m}\geqslant m\quad \forall m}. Schoenberg showed that this is a necessary condition for all values of ${\displaystyle k}${\displaystyle k}.

Consider a differentiable function ${\displaystyle f(x)}${\displaystyle f(x)} on ${\displaystyle [a,b]}${\displaystyle [a,b]}, such that ${\displaystyle f(a)=f(b)}${\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)}${\displaystyle P^{(1)}(c)=f^{(1)}(c)} where ${\displaystyle c={\frac {a+b}{2}}}${\displaystyle c={\frac {a+b}{2}}}: Since ${\displaystyle f(a)=f(b)}${\displaystyle f(a)=f(b)}, one may write the polynomial as ${\displaystyle P(x)=A(x-c)^{2}+B}${\displaystyle P(x)=A(x-c)^{2}+B} (by completing the square) where ${\displaystyle A,B}${\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}}${\displaystyle P^{(1)}(x)=2A(x-c)^{2}}. This implies ${\displaystyle P^{(1)}(c)=0}${\displaystyle P^{(1)}(c)=0}, however this is absurd, since ${\displaystyle f^{(1)}(c)}${\displaystyle f^{(1)}(c)} is not necessarily ${\displaystyle 0}${\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}}${\displaystyle {\begin{pmatrix}1&0&0\0円&1&0\1円&0&0\end{pmatrix}}_{3\times 3}}

Consider a differentiable function ${\displaystyle f(x)}${\displaystyle f(x)} on ${\displaystyle [a,b]}${\displaystyle [a,b]}, and denote ${\displaystyle x_{0}=a,x_{2}=b}${\displaystyle x_{0}=a,x_{2}=b} with ${\displaystyle x_{1}\in [a,b]}${\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})}${\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})}${\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)}${\displaystyle f^{(1)}(x)} at the nodes ${\displaystyle x_{0},x_{2}}${\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})}${\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}${\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}}${\displaystyle {\begin{pmatrix}0&1&0\1円&0&0\0円&1&0\end{pmatrix}}_{3\times 3}}

Given a natural number ${\displaystyle N}${\displaystyle N}, and a differentiable function ${\displaystyle f(x)}${\displaystyle f(x)} on ${\displaystyle [a,b]}${\displaystyle [a,b]}, is there a polynomial such that: ${\displaystyle P(x_{0})=f(x_{0})}${\displaystyle P(x_{0})=f(x_{0})} and ${\displaystyle P^{(1)}(x_{i})=f^{(1)}(x_{i})}${\displaystyle P^{(1)}(x_{i})=f^{(1)}(x_{i})} for ${\displaystyle i=1,\cdots ,N}${\displaystyle i=1,\cdots ,N} with ${\displaystyle x_{0},x_{1},\cdots ,x_{N}\in [a,b]}${\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)}${\displaystyle P_{N-1}(x)} that satisfies ${\displaystyle P_{N-1}(x_{i})=f^{(1)}(x_{i})}${\displaystyle P_{N-1}(x_{i})=f^{(1)}(x_{i})} for ${\displaystyle i=1,\cdots ,N}${\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}${\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}}${\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}${\displaystyle N}, and a ${\displaystyle 2N}${\displaystyle 2N} differentiable function ${\displaystyle f(x)}${\displaystyle f(x)} on ${\displaystyle [a,b]}${\displaystyle [a,b]}, is there a polynomial such that: ${\displaystyle P^{(k)}(a)=f^{(k)}(a)}${\displaystyle P^{(k)}(a)=f^{(k)}(a)} and ${\displaystyle P^{(k)}(b)=f^{(k)}(b)}${\displaystyle P^{(k)}(b)=f^{(k)}(b)} for ${\displaystyle k=0,2,\cdots ,2N}${\displaystyle k=0,2,\cdots ,2N}? Construct ${\displaystyle P_{1}(x)}${\displaystyle P_{1}(x)} as the interpolating polynomial of ${\displaystyle f(x)}${\displaystyle f(x)} at ${\displaystyle x=a}${\displaystyle x=a} and ${\displaystyle x=b}${\displaystyle x=b}, such that ${\displaystyle P_{1}(x)={\frac {f^{(2N)}(b)-f^{(2N)}(a)}{b-a}}(x-a)+f^{(2N)}(a)}${\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}${\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)}${\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}}${\displaystyle {\begin{pmatrix}1&0&1&0\cdots \1円&0&1&0\cdots \\\end{pmatrix}}_{2\times N}}

• Interpolation

• CS1 German-language sources (de)
• Wikipedia articles needing clarification from December 2010
• All Wikipedia articles needing clarification