Editing Birkhoff interpolation

{{confusing|date=December 2010}}

In [[mathematics]], '''Birkhoff interpolation''' is an extension of [[polynomial interpolation]]. It refers to the problem of finding a polynomial <math>P(x)</math> of degree <math>d</math> such that ''only certain'' [[derivative]]s have specified values at specified points:
:<math> P^{(n_i)}(x_i) = y_i \qquad\mbox{for } i=1,\ldots,d, </math>
where the data points <math>(x_i,y_i)</math> and the nonnegative integers <math>n_i</math> are given. It differs from [[Hermite interpolation]] in that it is possible to specify derivatives of <math>P(x)</math> 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.<ref>{{Cite journal |last=Birkhoff |first=George David |date=1906 |title=General mean value and remainder theorems with applications to mechanical differentiation and quadrature |url=https://www.ams.org/tran/1906-007-01/S0002-9947-1906-1500736-1/ |journal=Transactions of the American Mathematical Society |language=en |volume=7 |issue=1 |pages=107–136 |doi=10.1090/S0002-9947-1906-1500736-1 |issn=0002-9947|doi-access=free }}</ref>

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

An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. [[Isaac Jacob Schoenberg|Schoenberg]]<ref>{{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 }}</ref> formulates the problem as follows. Let <math>d</math> denote the number of conditions (as above) and let <math>k</math> be the number of interpolation points. Given a <math>d\times k</math> matrix <math>E</math>, all of whose entries are either <math>0</math> or <math>1</math>, such that exactly <math>d</math> entries are <math>1</math>, then the corresponding problem is to determine <math>P(x)</math> such that
:<math> P^{(j)}(x_i) = y_{i,j} \qquad\forall (i,j) / e_{ij} = 1 </math>
The matrix <math>E</math> is called the '''incidence matrix'''. For example, the incidence matrices for the interpolation problems mentioned in the previous paragraph are:
:<math> \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}. </math>
Now the question is: Does a Birkhoff interpolation problem with a given incidence matrix <math>E</math> have a unique solution for any choice of the interpolation points?


The case with <math>k=2</math> interpolation points was tackled by [[George Pólya]] in 1931.<ref>{{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 }}</ref> Let <math>S_m</math> denote the sum of the entries in the first <math>m</math> columns of the incidence matrix:
:<math> S_m = \sum_{i=1}^k \sum_{j=1}^m e_{ij}. </math>
Then the Birkhoff interpolation problem with <math>k=2</math> has a unique solution if and only if <math>S_m\geqslant m \quad\forall m</math>. Schoenberg showed that this is a necessary condition for all values of <math>k</math>.

==Some examples==

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


Consider a differentiable function <math>f(x)</math> on <math>[a,b]</math>, and denote <math>x_0=a,x_2=b</math> with <math>x_1\in[a,b]</math>. Let us see that there is indeed Birkhoff interpolation quadratic polynomial such that <math>P(x_1)=f(x_1)</math> and <math>P^{(1)}(x_0)=f^{(1)}(x_0),P^{(1)}(x_2)=f^{(1)}(x_2)</math>. Construct the interpolating polynomial of <math>f^{(1)}(x)</math> at the nodes <math>x_0,x_2</math>, such that <math>\displaystyle P_1(x) = \frac{f^{(1)}(x_2)-f^{(1)}(x_0)}{x_2-x_0}(x-x_0)+f^{(1)}(x_0)</math>. Thus the polynomial : <math>\displaystyle P_2(x) = f(x_1) + \int_{x_1}^x\!P_1(t)\;\mathrm{d}t</math> is the Birkhoff interpolating polynomial. The incidence matrix is given by:
:<math> \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}_{3\times3} </math>


Given a natural number <math>N</math>, and a differentiable function <math>f(x)</math> on <math>[a,b]</math>, is there a polynomial such that: <math>P(x_0)=f(x_0)</math> and <math>P^{(1)}(x_i)=f^{(1)}(x_i)</math> for <math>i=1,\cdots,N</math> with <math>x_0,x_1,\cdots,x_N\in[a,b]</math>? Construct the Lagrange/[[Newton polynomial]] (same interpolating polynomial, different form to calculate and express them) <math>P_{N-1}(x)</math> that satisfies <math>P_{N-1}(x_i)=f^{(1)}(x_i)</math> for <math>i=1,\cdots,N</math>, then the polynomial <math>\displaystyle P_N(x) = f(x_0) + \int_{x_0}^x\! P_{N-1}(t)\;\mathrm{d}t</math> is the Birkhoff interpolating polynomial satisfying the above conditions. The incidence matrix is given by:
:<math> \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} </math>


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

==References==
[[Category:Interpolation]]
<references />