Birkhoff interpolation

{{ safesubst:#invoke:Unsubst||date=__DATE__|$B= Template:Ambox }}

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 derivatives 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>Template:Cite journal</ref>

Existence and uniqueness of solutionsEdit

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>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>

An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. Schoenberg<ref>Template:Cite journal</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>Template:Cite journal</ref> Let <math>S_m</math> denote the sum of the entries in the first <math>m</math> columns of the incidence matrix:

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 examplesEdit

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>

ReferencesEdit