Birkhoff interpolation

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.{{Cite web |title=American Mathematical Society |url=https://www.ams.org/journals/bull/1983-09-03/S0273-0979-1983-15204-7/home.html |access-date=2022-05-19 |website=American Mathematical Society |language=en}}

An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. Schoenberg{{Cite journal |last=Schoenberg |first=I. J |date=1966-12-01 |title=On Hermite-Birkhoff interpolation |journal=Journal of Mathematical Analysis and Applications |language=en |volume=16 |issue=3 |pages=538–543 |doi=10.1016/0022-247X(66)90160-0 |issn=0022-247X|doi-access=free }} 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\backslash 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\}\; \backslash qquad\backslash 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:

:

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.{{Cite journal |last=Pólya |first=G. |date=1931 |title=Bemerkung zur Interpolation und zur Näherungstheorie der Balkenbiegung |url=https://onlinelibrary.wiley.com/doi/10.1002/zamm.19310110620 |journal=ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik |language=de |volume=11 |issue=6 |pages=445–449 |doi=10.1002/zamm.19310110620|bibcode=1931ZaMM...11..445P |url-access=subscription }} Let $S\_m$ denote the sum of the entries in the first $m$ columns of the incidence matrix:

:$S\_m\; =\; \backslash sum\_\{i=1\}^k\; \backslash sum\_\{j=1\}^m\; e\_\{ij\}.$

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

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=\backslash 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:

:

Consider a differentiable function $f(x)$ on $[a,b]$, and denote $x\_0=a,x\_2=b$ with $x\_1\backslash 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 $\backslash displaystyle\; P\_1(x)\; =\; \backslash frac\{f^\{(1)\}(x\_2)-f^\{(1)\}(x\_0)\}\{x\_2-x\_0\}(x-x\_0)+f^\{(1)\}(x\_0)$. Thus the polynomial : $\backslash displaystyle\; P\_2(x)\; =\; f(x\_1)\; +\; \backslash int\_\{x\_1\}^x\backslash !P\_1(t)\backslash ;\backslash mathrm\{d\}t$ is the Birkhoff interpolating polynomial. The incidence matrix is given by:

:

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,\backslash cdots,N$ with $x\_0,x\_1,\backslash cdots,x\_N\backslash 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,\backslash cdots,N$, then the polynomial $\backslash displaystyle\; P\_N(x)\; =\; f(x\_0)\; +\; \backslash int\_\{x\_0\}^x\backslash !\; P\_\{N-1\}(t)\backslash ;\backslash mathrm\{d\}t$ is the Birkhoff interpolating polynomial satisfying the above conditions. The incidence matrix is given by:

:

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,\backslash cdots,2N$? Construct $P\_1(x)$ as the interpolating polynomial of $f(x)$ at $x=a$ and $x=b$, such that $P\_1(x)=\backslash frac\{f^\{(2N)\}(b)-f^\{(2N)\}(a)\}\{b-a\}(x-a)$

+f^{(2N)}(a). Define then the iterates $\backslash displaystyle\; P\_\{k+2\}(x)=\backslash 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:

:

Category:Interpolation