Birkhoff interpolation

<h2 id="existence-and-uniqueness-of-solutions">Existence and uniqueness of solutions</h2>
In contrast to <a href="/facts/Lagrange_interpolation/MnpMmhtC">Lagrange interpolation</a> and <a href="/facts/Hermite_interpolation/u36d6yH2">Hermite interpolation</a>, a Birkhoff interpolation problem does not always have a unique solution. For instance, there is no quadratic polynomial 
 
 
 
 P
 (
 x
 )
 
 
 {\displaystyle P(x)}
 
 such that 
 
 
 
 P
 (
 −
 1
 )
 =
 P
 (
 1
 )
 =
 0
 
 
 {\displaystyle P(-1)=P(1)=0}
 
 and 
 
 
 
 
 P
 
 (
 1
 )
 
 
 (
 0
 )
 =
 1
 
 
 {\displaystyle P^{(1)}(0)=1}
 
. On the other hand, the Birkhoff interpolation problem where the values of 
 
 
 
 
 P
 
 (
 1
 )
 
 
 (
 −
 1
 )
 ,
 P
 (
 0
 )
 
 
 {\displaystyle P^{(1)}(-1),P(0)}
 
 and 
 
 
 
 
 P
 
 (
 1
 )
 
 
 (
 1
 )
 
 
 {\displaystyle P^{(1)}(1)}
 
 are given always has a unique solution.<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
An important problem in the theory of Birkhoff interpolation is to classify those problems that have a unique solution. <a href="/facts/Isaac_Jacob_Schoenberg/H88Sjl2g">Schoenberg</a><a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> formulates the problem as follows. Let 
 
 
 
 d
 
 
 {\displaystyle d}
 
 denote the number of conditions (as above) and let 
 
 
 
 k
 
 
 {\displaystyle k}
 
 be the number of interpolation points. Given a 
 
 
 
 d
 ×
 k
 
 
 {\displaystyle d\times k}
 
 matrix 
 
 
 
 E
 
 
 {\displaystyle E}
 
, all of whose entries are either 
 
 
 
 0
 
 
 {\displaystyle 0}
 
 or 
 
 
 
 1
 
 
 {\displaystyle 1}
 
, such that exactly 
 
 
 
 d
 
 
 {\displaystyle d}
 
 entries are 
 
 
 
 1
 
 
 {\displaystyle 1}
 
, then the corresponding problem is to determine 
 
 
 
 P
 (
 x
 )
 
 
 {\displaystyle P(x)}
 
 such that

P
          
            (
            j
            )
          
        
        (
        
          x
          
            i
          
        
        )
        =
        
          y
          
            i
            ,
            j
          
        
        
        ∀
        (
        i
        ,
        j
        )
        
          /
        
        
          e
          
            i
            j
          
        
        =
        1
      
    
    {\displaystyle P^{(j)}(x_{i})=y_{i,j}\qquad \forall (i,j)/e_{ij}=1}

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

(
            
              
                
                  1
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  1
                
                
                  0
                
              
              
                
                  1
                
                
                  0
                
                
                  0
                
              
            
            )
          
        
        
        
          a
          n
          d
        
        
        
          
            (
            
              
                
                  0
                
                
                  1
                
                
                  0
                
              
              
                
                  1
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  1
                
                
                  0
                
              
            
            )
          
        
        .
      
    
    {\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}}.}

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

The case with 
 
 
 
 k
 =
 2
 
 
 {\displaystyle k=2}
 
 interpolation points was tackled by <a href="/facts/George_P%C3%B3lya/cYgGdvJu">George Pólya</a> in 1931.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> Let 
 
 
 
 
 S
 
 m
 
 
 
 
 {\displaystyle S_{m}}
 
 denote the sum of the entries in the first 
 
 
 
 m
 
 
 {\displaystyle m}
 
 columns of the incidence matrix:

S
          
            m
          
        
        =
        
          ∑
          
            i
            =
            1
          
          
            k
          
        
        
          ∑
          
            j
            =
            1
          
          
            m
          
        
        
          e
          
            i
            j
          
        
        .
      
    
    {\displaystyle S_{m}=\sum _{i=1}^{k}\sum _{j=1}^{m}e_{ij}.}

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

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

(
              
                
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                
                
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                
              
              )
            
          
          
            3
            ×
            3
          
        
      
    
    {\displaystyle {\begin{pmatrix}1&0&0\\0&1&0\\1&0&0\end{pmatrix}}_{3\times 3}}

Consider a differentiable function 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 on 
 
 
 
 [
 a
 ,
 b
 ]
 
 
 {\displaystyle [a,b]}
 
, and denote 
 
 
 
 
 x
 
 0
 
 
 =
 a
 ,
 
 x
 
 2
 
 
 =
 b
 
 
 {\displaystyle x_{0}=a,x_{2}=b}
 
 with 
 
 
 
 
 x
 
 1
 
 
 ∈
 [
 a
 ,
 b
 ]
 
 
 {\displaystyle x_{1}\in [a,b]}
 
. Let us see that there is indeed Birkhoff interpolation quadratic polynomial such that 
 
 
 
 P
 (
 
 x
 
 1
 
 
 )
 =
 f
 (
 
 x
 
 1
 
 
 )
 
 
 {\displaystyle P(x_{1})=f(x_{1})}
 
 and 
 
 
 
 
 P
 
 (
 1
 )
 
 
 (
 
 x
 
 0
 
 
 )
 =
 
 f
 
 (
 1
 )
 
 
 (
 
 x
 
 0
 
 
 )
 ,
 
 P
 
 (
 1
 )
 
 
 (
 
 x
 
 2
 
 
 )
 =
 
 f
 
 (
 1
 )
 
 
 (
 
 x
 
 2
 
 
 )
 
 
 {\displaystyle P^{(1)}(x_{0})=f^{(1)}(x_{0}),P^{(1)}(x_{2})=f^{(1)}(x_{2})}
 
. Construct the interpolating polynomial of 
 
 
 
 
 f
 
 (
 1
 )
 
 
 (
 x
 )
 
 
 {\displaystyle f^{(1)}(x)}
 
 at the nodes 
 
 
 
 
 x
 
 0
 
 
 ,
 
 x
 
 2
 
 
 
 
 {\displaystyle x_{0},x_{2}}
 
, such that 
 
 
 
 
 
 P
 
 1
 
 
 (
 x
 )
 =
 
 
 
 
 f
 
 (
 1
 )
 
 
 (
 
 x
 
 2
 
 
 )
 −
 
 f
 
 (
 1
 )
 
 
 (
 
 x
 
 0
 
 
 )
 
 
 
 x
 
 2
 
 
 −
 
 x
 
 0
 
 
 
 
 
 (
 x
 −
 
 x
 
 0
 
 
 )
 +
 
 f
 
 (
 1
 )
 
 
 (
 
 x
 
 0
 
 
 )
 
 
 
 {\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})}
 
. Thus the polynomial : 
 
 
 
 
 
 P
 
 2
 
 
 (
 x
 )
 =
 f
 (
 
 x
 
 1
 
 
 )
 +
 
 ∫
 
 
 x
 
 1
 
 
 
 
 x
 
 
 
 
 P
 
 1
 
 
 (
 t
 )
 
 
 d
 
 t
 
 
 
 {\displaystyle \displaystyle P_{2}(x)=f(x_{1})+\int _{x_{1}}^{x}\!P_{1}(t)\;\mathrm {d} t}
 
 is the Birkhoff interpolating polynomial. The incidence matrix is given by:

(
              
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                
                
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                
              
              )
            
          
          
            3
            ×
            3
          
        
      
    
    {\displaystyle {\begin{pmatrix}0&1&0\\1&0&0\\0&1&0\end{pmatrix}}_{3\times 3}}

Given a natural number 
 
 
 
 N
 
 
 {\displaystyle N}
 
, and a differentiable function 
 
 
 
 f
 (
 x
 )
 
 
 {\displaystyle f(x)}
 
 on 
 
 
 
 [
 a
 ,
 b
 ]
 
 
 {\displaystyle [a,b]}
 
, is there a polynomial such that: 
 
 
 
 P
 (
 
 x
 
 0
 
 
 )
 =
 f
 (
 
 x
 
 0
 
 
 )
 
 
 {\displaystyle P(x_{0})=f(x_{0})}
 
 and 
 
 
 
 
 P
 
 (
 1
 )
 
 
 (
 
 x
 
 i
 
 
 )
 =
 
 f
 
 (
 1
 )
 
 
 (
 
 x
 
 i
 
 
 )
 
 
 {\displaystyle P^{(1)}(x_{i})=f^{(1)}(x_{i})}
 
 for 
 
 
 
 i
 =
 1
 ,
 ⋯
 ,
 N
 
 
 {\displaystyle i=1,\cdots ,N}
 
 with 
 
 
 
 
 x
 
 0
 
 
 ,
 
 x
 
 1
 
 
 ,
 ⋯
 ,
 
 x
 
 N
 
 
 ∈
 [
 a
 ,
 b
 ]
 
 
 {\displaystyle x_{0},x_{1},\cdots ,x_{N}\in [a,b]}
 
? Construct the Lagrange/<a href="/facts/Newton_polynomial/2vRsjpA2">Newton polynomial</a> (same interpolating polynomial, different form to calculate and express them) 
 
 
 
 
 P
 
 N
 −
 1
 
 
 (
 x
 )
 
 
 {\displaystyle P_{N-1}(x)}
 
 that satisfies 
 
 
 
 
 P
 
 N
 −
 1
 
 
 (
 
 x
 
 i
 
 
 )
 =
 
 f
 
 (
 1
 )
 
 
 (
 
 x
 
 i
 
 
 )
 
 
 {\displaystyle P_{N-1}(x_{i})=f^{(1)}(x_{i})}
 
 for 
 
 
 
 i
 =
 1
 ,
 ⋯
 ,
 N
 
 
 {\displaystyle i=1,\cdots ,N}
 
, then the polynomial 
 
 
 
 
 
 P
 
 N
 
 
 (
 x
 )
 =
 f
 (
 
 x
 
 0
 
 
 )
 +
 
 ∫
 
 
 x
 
 0
 
 
 
 
 x
 
 
 
 
 P
 
 N
 −
 1
 
 
 (
 t
 )
 
 
 d
 
 t
 
 
 
 {\displaystyle \displaystyle P_{N}(x)=f(x_{0})+\int _{x_{0}}^{x}\!P_{N-1}(t)\;\mathrm {d} t}
 
 is the Birkhoff interpolating polynomial satisfying the above conditions. The incidence matrix is given by:

(
              
                
                  
                    1
                  
                  
                    0
                  
                  
                    0
                  
                  
                    ⋯
                  
                  
                    0
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    ⋯
                  
                  
                    0
                  
                
                
                  
                    ⋮
                  
                  
                    ⋮
                  
                  
                    ⋮
                  
                  
                    ⋱
                  
                  
                    ⋮
                  
                
                
                  
                    0
                  
                  
                    1
                  
                  
                    0
                  
                  
                    ⋯
                  
                  
                    0
                  
                
              
              )
            
          
          
            N
            ×
            N
          
        
      
    
    {\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}}

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

(
              
                
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                    ⋯
                  
                
                
                  
                    1
                  
                  
                    0
                  
                  
                    1
                  
                  
                    0
                    ⋯
                  
                
              
              )
            
          
          
            2
            ×
            N
          
        
      
    
    {\displaystyle {\begin{pmatrix}1&0&1&0\cdots \\1&0&1&0\cdots \\\end{pmatrix}}_{2\times N}}

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Birkhoff, George David (1906). "General mean value and remainder theorems with applications to mechanical differentiation and quadrature". Transactions of the American Mathematical Society. 7 (1): 107–136. doi:10.1090/S0002-9947-1906-1500736-1. ISSN 0002-9947. <a href="https://www.ams.org/tran/1906-007-01/S0002-9947-1906-1500736-1/" target="_blank">https://www.ams.org/tran/1906-007-01/S0002-9947-1906-1500736-1/</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"American Mathematical Society". American Mathematical Society. Retrieved 2022-05-19. <a href="https://www.ams.org/journals/bull/1983-09-03/S0273-0979-1983-15204-7/home.html" target="_blank">https://www.ams.org/journals/bull/1983-09-03/S0273-0979-1983-15204-7/home.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Schoenberg, I. J (1966-12-01). "On Hermite-Birkhoff interpolation". Journal of Mathematical Analysis and Applications. 16 (3): 538–543. doi:10.1016/0022-247X(66)90160-0. ISSN 0022-247X. <a href="https://doi.org/10.1016%2F0022-247X%2866%2990160-0" target="_blank">https://doi.org/10.1016%2F0022-247X%2866%2990160-0</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Pólya, G. (1931). "Bemerkung zur Interpolation und zur Näherungstheorie der Balkenbiegung". ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik (in German). 11 (6): 445–449. Bibcode:1931ZaMM...11..445P. doi:10.1002/zamm.19310110620. <a href="https://onlinelibrary.wiley.com/doi/10.1002/zamm.19310110620" target="_blank">https://onlinelibrary.wiley.com/doi/10.1002/zamm.19310110620</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
</ol>

Birkhoff interpolation open-in-new

Birkhoff interpolation