Birkhoff interpolation

In mathematics, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial [math]\displaystyle{ P(x) }[/math] of degree [math]\displaystyle{ d }[/math] such that only certain derivatives have specified values at specified points:

[math]\displaystyle{ P^{(n_i)}(x_i) = y_i \qquad\mbox{for } i=1,\ldots,d, }[/math]

where the data points [math]\displaystyle{ (x_i,y_i) }[/math] and the nonnegative integers [math]\displaystyle{ n_i }[/math] are given. It differs from Hermite interpolation in that it is possible to specify derivatives of [math]\displaystyle{ 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.^[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 [math]\displaystyle{ P(x) }[/math] such that [math]\displaystyle{ P(-1)=P(1)=0 }[/math] and [math]\displaystyle{ P^{(1)}(0)=1 }[/math]. On the other hand, the Birkhoff interpolation problem where the values of [math]\displaystyle{ P^{(1)}(-1), P(0) }[/math] and [math]\displaystyle{ P^{(1)}(1) }[/math] 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 [math]\displaystyle{ d }[/math] denote the number of conditions (as above) and let [math]\displaystyle{ k }[/math] be the number of interpolation points. Given a [math]\displaystyle{ d\times k }[/math] matrix [math]\displaystyle{ E }[/math], all of whose entries are either [math]\displaystyle{ 0 }[/math] or [math]\displaystyle{ 1 }[/math], such that exactly [math]\displaystyle{ d }[/math] entries are [math]\displaystyle{ 1 }[/math], then the corresponding problem is to determine [math]\displaystyle{ P(x) }[/math] such that

[math]\displaystyle{ P^{(j)}(x_i) = y_{i,j} \qquad\forall (i,j) / e_{ij} = 1 }[/math]

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

[math]\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}. }[/math]

Now the question is: Does a Birkhoff interpolation problem with a given incidence matrix [math]\displaystyle{ E }[/math] have a unique solution for any choice of the interpolation points?

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

[math]\displaystyle{ S_m = \sum_{i=1}^k \sum_{j=1}^m e_{ij}. }[/math]

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

Some examples

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

[math]\displaystyle{ \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{pmatrix}_{3\times3} }[/math]

Consider a differentiable function [math]\displaystyle{ f(x) }[/math] on [math]\displaystyle{ [a,b] }[/math], and denote [math]\displaystyle{ x_0=a,x_2=b }[/math] with [math]\displaystyle{ x_1\in[a,b] }[/math]. Let us see that there is indeed Birkhoff interpolation quadratic polynomial such that [math]\displaystyle{ P(x_1)=f(x_1) }[/math] and [math]\displaystyle{ P^{(1)}(x_0)=f^{(1)}(x_0),P^{(1)}(x_2)=f^{(1)}(x_2) }[/math]. Construct the interpolating polynomial of [math]\displaystyle{ f^{(1)}(x) }[/math] at the nodes [math]\displaystyle{ x_0,x_2 }[/math], such that [math]\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) }[/math]. Thus the polynomial : [math]\displaystyle{ \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]\displaystyle{ \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}_{3\times3} }[/math]

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

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

[math]\displaystyle{ \begin{pmatrix} 1 & 0 & 1 & 0 \cdots \\ 1 & 0 & 1 & 0 \cdots \\ \end{pmatrix}_{2\times N} }[/math]

References

0.00 (0 votes) Original source: https://en.wikipedia.org/wiki/Birkhoff interpolation. Read more