HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Birkhoff interpolation is an extension of polynomial interpolation. It refers to the problem of finding a polynomial P(x) of degree d such that ''only certain''
derivative In mathematics, the derivative is a fundamental tool that quantifies the sensitivity to change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is t ...
s have specified values at specified points: : P^(x_i) = y_i \qquad\mbox i=1,\ldots,d, where the data points (x_i,y_i) and the nonnegative integers n_i are given. It differs from Hermite interpolation in that it is possible to specify derivatives of P(x) at some points without specifying the lower derivatives or the polynomial itself. The name refers to
George David Birkhoff George David Birkhoff (March21, 1884November12, 1944) was one of the top American mathematicians of his generation. He made valuable contributions to the theory of differential equations, dynamical systems, the four-color problem, the three-body ...
, who first studied the problem in 1906.


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 P(x) such that P(-1)=P(1)=0 and P^(0)=1. On the other hand, the Birkhoff interpolation problem where the values of P^(-1), P(0) and P^(1) are given always has a unique solution. An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. Schoenberg 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\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^(x_i) = y_ \qquad\forall (i,j) / e_ = 1 The matrix E is called the incidence matrix. For example, the incidence matrices for the interpolation problems mentioned in the previous paragraph are: : \begin 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end \qquad\mathrm\qquad \begin 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end. 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 George Pólya (; ; December 13, 1887 – September 7, 1985) was a Hungarian-American mathematician. He was a professor of mathematics from 1914 to 1940 at ETH Zürich and from 1940 to 1953 at Stanford University. He made fundamental contributi ...
in 1931. Let S_m denote the sum of the entries in the first m columns of the incidence matrix: : S_m = \sum_^k \sum_^m e_. Then the Birkhoff interpolation problem with k=2 has a unique solution if and only if S_m\geqslant m \quad\forall m. Schoenberg showed that this is a necessary condition for all values of k.


Some examples

Consider a differentiable function f(x) on ,b/math>, such that f(a)=f(b). Let us see that there is no Birkhoff interpolation quadratic polynomial such that P^(c)=f^(c) where c=\frac: Since f(a)=f(b), one may write the polynomial as P(x)=A(x-c)^2+B (by
completing the square In elementary algebra, completing the square is a technique for converting a quadratic polynomial of the form to the form for some values of and . In terms of a new quantity , this expression is a quadratic polynomial with no linear term. By s ...
) where A,B are merely the interpolation coefficients. The derivative of the interpolation polynomial is given by P^(x)=2A(x-c)^2. This implies P^(c)=0, however this is absurd, since f^(c) is not necessarily 0. The incidence matrix is given by: : \begin 1 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end_ Consider a differentiable function f(x) on ,b/math>, and denote x_0=a,x_2=b with x_1\in ,b/math>. Let us see that there is indeed Birkhoff interpolation quadratic polynomial such that P(x_1)=f(x_1) and P^(x_0)=f^(x_0),P^(x_2)=f^(x_2). Construct the interpolating polynomial of f^(x) at the nodes x_0,x_2, such that \displaystyle P_1(x) = \frac(x-x_0)+f^(x_0). Thus the polynomial : \displaystyle P_2(x) = f(x_1) + \int_^x\!P_1(t)\;\mathrmt is the Birkhoff interpolating polynomial. The incidence matrix is given by: : \begin 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end_ Given a natural number N, and a differentiable function f(x) on ,b/math>, is there a polynomial such that: P(x_0)=f(x_0) and P^(x_i)=f^(x_i) for i=1,\cdots,N with x_0,x_1,\cdots,x_N\in ,b/math>? Construct the Lagrange/ Newton polynomial (same interpolating polynomial, different form to calculate and express them) P_(x) that satisfies P_(x_i)=f^(x_i) for i=1,\cdots,N, then the polynomial \displaystyle P_N(x) = f(x_0) + \int_^x\! P_(t)\;\mathrmt is the Birkhoff interpolating polynomial satisfying the above conditions. The incidence matrix is given by: : \begin 1 & 0 & 0 & \cdots & 0 \\ 0 & 1 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 0 & \cdots & 0 \\ \end_ Given a natural number N, and a 2N differentiable function f(x) on ,b/math>, is there a polynomial such that: P^(a)=f^(a) and P^(b)=f^(b) for k=0,2,\cdots,2N? Construct P_1(x) as the interpolating polynomial of f(x) at x=a and x=b, such that P_1(x)=\frac(x-a) +f^(a). Define then the iterates \displaystyle P_(x)=\frac(x-a) +f^(a) + \int_a^x\!\int_a^t\! P_k(s)\;\mathrms\;\mathrmt . Then P_(x) is the Birkhoff interpolating polynomial. The incidence matrix is given by: : \begin 1 & 0 & 1 & 0 \cdots \\ 1 & 0 & 1 & 0 \cdots \\ \end_{2\times N}


References

Interpolation