Independent sets of interpolation nodes or “how to make all sets regular”

Marcel G. de Bruin\(^\ast \) Detlef H. Mache\(^{\ast \ast }\)

June 5, 2012.

\(^\ast \) Delft Institute of Applied Mathematics, Delft University of Technology, P.O. Box 5031, 2600 GA Delft, The Netherlands, e-mail: marcelgdeb@netscape.net.

\(^{\ast \ast }\) University of Applied Sciences Bochum, WB 3 - Applied Mathematics (Constructive Approximation), Herner Str. 45, D-44787 Bochum, Germany and Technical University of Dortmund, Department of Mathematics, Vogelpothsweg 87, D-44221 Dortmund, Germany, e-mail: mache@tfh-bochum.de, Detlef.Mache@math.tu-dortmund.de.

Hermite-Birkhoff interpolation and Pál-type interpolation have been receiving much attention over the years. Also during the previous 15 years the subject of interpolation in non-uniformly distributed nodes has been looked into. There are, however, not many examples known where lacunary problems (the orders of the derivatives for which data are given, are non-consecutive) are regular. Here lacunary Pál-type interpolation is looked into “the other way around”: the interpolation points are given and the orders of the derivatives to be used are derived from the number of points.

MSC. 41A05.

Keywords. Pál-type interpolation, regularity.

1 Introduction

Let \(\Pi _N\) be the set of polynomials of degree at most \(N\) with complex coefficients and consider for an arbitrary integer \(q\geq 0\) the following problem:

given \(q+1\) sets of different points \(\{ z^{[j]}_i\} _{i=1}^{n_j},\ (0\leq j\leq q)\) (nodes),

given \(q+1\) natural numbers \(0=d_0{\lt}d_1\cdots {\lt}d_q\) (orders)

given complex numbers \(\{ c^{[j]}_i\} \ (1\leq i\leq n_j,\ 0\leq j\leq q)\) (data),

find \(P_N\in \Pi _N,\ N=\sum _{j=0}^q\, d_j-1\) with \(P^{(d_j)}_N(z^{[j]}_i)=c^{[j]}_i \ (1\leq i\leq n_j,\ 0\leq j\leq q)\).

This interpolation problem is called regular when the solution \(P_N(z)\) is unique for any set of data; this is equivalent to the statement:

if all data are zero, then the problem has the trivial solution \(P_N(z)\equiv 0\) only.

When the numbers \(n_j\) and nodes \(z_i^{[j]}\) do not depend on \(j\) (just one set of nodes is used), this type of problem is called Hermite-Birkhoff interpolation, a well known subject (cf. the excellent book [ 5 ] ). When the nodes do depend on \(j\), one usually speaks of Pál-type interpolation, cf. [ 6 ] .

In both cases the problem is called lacunary when the orders of the derivatives are not consecutive.

There are few general examples of regular lacunary problems, for Hermite-Birkhoff see [ 4 ] , for lacunary Pál-type see [ 1 ] .

After it has been established that a set of nodes and orders leads to a regular problem, it is (sometimes) possible to solve it explicitly, using the so called fundamental polynomials. These polynomials \(P_{i,j}(z)\) are defined for all values of \(i,\, j\) as the solution of the interpolation problem with all data zero except for \(c^{[j]}_i=1\).

The solution to the full interpolation problem is then given by

\[ P_N(z)=\sum _{j=0}^q\, \sum _{i=1}^{n_j}\, c^{[j]}_iP_{i,j}(z). \]

Usually in these type of problems, the nodes and orders are given at the beginning, along with the fact that the problem is indeed regular.

The first steps to approach the problem from another direction were taken in [ 2 ] , [ 3 ] : there, starting from given nodes for the order \(0\), conditions were given on a second set of nodes to find a regular \((0,1)\) or \((0,2)\) Pál-type interpolation problem.

Here this method will be taken to the extreme: for \(q+1\) fixed sets of nodes given, \(q\) orders will be exhibited that make the \((d_0,d_1,\ldots ,d_q)\) Pál-type interpolation problem regular.

The layout of the paper is as follows: in section 2 the main results are stated–along with two examples–followed by the proofs in section 3. Finally some references are given.

2 Main results

Consider \(q+1\) (\(q\geq 0\) an integer) sets of complex interpolation nodes

\begin{equation} \label{nodes} S_j=\{ z^{[j]}_1,z^{[j]}_2,\ldots ,z^{[j]}_{n_j}\} ,\ (0\leq j\leq q). \end{equation}

The nodes in \(S_j\) are pairwise different for fixed \(j\), but nodes may appear in different sets; moreover, the \(n_j\geq 1\) are completely arbitrary positive integers.

Let the orders \(d_j\) be positive integers satisfying

\begin{equation} \label{orders} 0 = d_0 < d_1 \cdots < d_q. \end{equation}

The \((d_0,d_1,\ldots ,d_q)\) Pál-type interpolation problem is then formulated as follows.

Given a set of data

\begin{equation} \label{data} c^{[j]}_i \ (1\leq i\leq n_j,\ 0\leq j\leq q), \end{equation}

find a polynomial \(P_N\) of degree at most \(N=n_0+n_1+\cdots +n_q-1\), satisfying

\begin{equation} \label{pip} P^{(d_j)}_N(z^{[j]}_i)=c^{[j]}_i \ (1\leq i\leq n_j,\ 0\leq j\leq q) \end{equation}

The problem is denoted regular when 4 has a unique solution for arbitrary data 3. This is equivalent to

\begin{equation} \label{piphom} \mathrm{\eqref{pip}\ with\ }c^{[j]}_i=0 \ (1\leq i\leq n_j,\ 0\leq j\leq q)\mathrm{\ has \ the\ trivial\ solution\ only}. \end{equation}

Then we have

Theorem 1

The \((d_0,d_1,\ldots ,d_q)\) Pál-type interpolation problem 4 with nodes 1 and orders

\begin{equation} \label{ordval} d_0=0;\ d_j=\sum _{k=0}^{j-1}\, n_k,\ 1\leq j\leq q, \end{equation}

is regular.

Also we have ‘the other way around’:

Theorem 2

Let the integer orders \(d_j\ (0\leq j\leq q)\) be given as in 2 with

\[ 0=d_0{\lt}d_1{\lt}\cdots {\lt}d_q. \]

Then for any sequence of arbitrary sets of nodes \(S_0,S_1,\ldots ,S_q\) with \(S_i\) consisting of

\begin{equation} \label{numberval} n_i=d_{i+1}-d_i\ (0\leq i\leq q-1),\ n_q\ \hbox{arbitrary}, \end{equation}

pairwise different nodes (for a set of fixed index) we have that the
\((d_0,d_1,\ldots ,d_q)\) Pál-type interpolation problem on \(\{ S_0,S_1,\ldots ,S_q\} \) is regular.

This section will be concluded with two examples, one for each of the theorems given above.

Example 3

Given the sets of interpolation nodes

\begin{equation} \label{ex1nodes} S_0=\{ x_1,x_2\} ,\ S_1=\{ y_1,y_2,y_3\} ,\ S_2=\{ z_1,z_2\} , \end{equation}

where the \(S_j\) contain pairwise different points.

According to Theorem 1, the \((0,2,5)\) Pál-type interpolation problem on \(\{ S_0,S_1,S_2\} \) is regular.â–¡

Indeed, putting

\begin{equation} \label{expol} P_6(z)=\sum _{k=0}^6\, a_k z^k, \end{equation}

the set of equations that determines the \(a_k\) has coefficient-matrix

\begin{equation} \label{ex1mat} A=\begin{pmatrix} 1 & x_1 & x_1^2 & x_1^3 & x_1^4 & x_1^5 & x_1^6 \\ 1 & x_2 & x_2^2 & x_2^3 & x_2^4 & x_2^5 & x_2^6 \\ 0 & 0 & 2 & 6y_1 & 12y_1^2 & 20y_1^3 & 360y_1^4 \\ 0 & 0 & 2 & 6y_2 & 12y_2^2 & 20y_2^3 & 360y_2^4 \\ 0 & 0 & 2 & 6y_3 & 12y_3^2 & 20y_3^3 & 360y_3^4 \\ 0 & 0 & 0 & 0 & 0 & 5! & 6!z_1 \\ 0 & 0 & 0 & 0 & 0 & 5! & 6!z_2 \end{pmatrix}, \end{equation}

with

\[ \det {A}=\begin{vmatrix} 1 & x_1 \\ 1 & x_2 \end{vmatrix}\times \begin{vmatrix} 2 & 6y_1 & 12y_1^2 \\ 2 & 6y_2 & 12y_2^2 \\ 2 & 6y_3 & 12y_3^2 \end{vmatrix}\times \begin{vmatrix} 5! & 6!z_1 \\ 5! & 6!z_2 \end{vmatrix}\not=0. \]

Thus the interpolation problem is regular.

Example 4

A \((0,1,4)\) Pál-type interpolation problem is, according to Theorem 2, regular on \(\{ S_0,S_1,S_2\} \) with \(S_0\) having \(1-0=1\), \(S_1\) having \(4-1=3\) point(s) and \(S_2\) having arbitrary many points.â–¡

Indeed, put for instance

\begin{equation} \label{ex2nodes} S_0=\{ x_1,x_2\} ,\ S_1=\{ y_1,y_2,y_3\} ,\ S_2=\{ z_1,z_2,z_3\} , \end{equation}

and use \(P_6(z)\) as in 9,then the coefficient matrix is

\begin{equation} \label{ex2mat} B=\begin{pmatrix} 1 & x_1 & x_1^2 & x_1^3 & x_1^4 & x_1^5 & x_1^6 \\ 0 & 1 & 2y_1 & 3y_1^2 & 4y_1^3 & 5y_1^4 & 6y_1^5 \\ 0 & 1 & 2y_2 & 3y_2^2 & 4y_2^3 & 5y_2^4 & 6y_2^5 \\ 0 & 1 & 2y_3 & 3y_3^2 & 4y_3^3 & 5y_3^4 & 6y_3^5 \\ 0 & 0 & 0 & 0 & 4! & 5!z_1 & 360z_1^2 \\ 0 & 0 & 0 & 0 & 4! & 5!z_2 & 360z_2^2 \\ 0 & 0 & 0 & 0 & 4! & 5!z_3 & 360z_3^2 \end{pmatrix}, \end{equation}

with

\[ \det {B}=\begin{vmatrix} 1 & 2y_1 & 3y_1^2 \\ 1 & 2y_2 & 3y_2^2 \\ 1 & 2y_3 & 3y_3^2 \end{vmatrix}\times \begin{vmatrix} 4! & 5!z_1 & 360z_1^2 \\ 4! & 5!z_2 & 360z_2^2 \\ 4! & 5!z_3 & 360z_3^2 \end{vmatrix}\not=0, \]

and the problem is regular.

3 Proofs

Introduce for \(c\in \bf C\) the descending factorial (Pochhammer symbol) by

\begin{equation} \label{poch} [c]_0=1;\ [c]_m=c(c-1)\cdots (c-m+1)\ (m=1,2,\ldots ). \end{equation}

Putting

\begin{equation} \label{pol} P_N(z)=\sum _{j=0}^N\, a_j z^j, \end{equation}

we get

\begin{equation} \label{polkderiv} P^{(k)}_N(z)=\sum _{j=k}^N\, [j]_k a_j z^{j-k}=\sum _{j=0}^{N-k}\, [k+j]_j a_{k+j} z^j. \end{equation}

Proof of Theorem 1.

Because of the values of the orders 6, the polynomial 14 can be written as

\begin{equation} \label{blockpol} P_N(z)=\sum _{j=0}^q\, \sum _{k=0}^{n_j-1}\, a_{d_j+k}z^{d_j+k}. \end{equation}

The equations 4 for the homogeneous interpolation problem then are for \(j=0\):

\begin{equation} \label{eq0} 0=\sum _{j=0}^q\, \sum _{k=0}^{n_j-1}\, a_{d_j+k} \left(z^{[0]}_r\right)^{k},\ 1\leq r\leq n_0. \end{equation}

The derivative of order \(d_i\) with fixed \(i,\ (1\leq i\leq q)\) leads to the equations:

\begin{equation} \label{eqj} 0=\sum _{j=i}^q\, \sum _{k=0}^{n_j-1}\, [d_j+k]_{d_i} a_{d_j+k} \left(z^{[j]}_r\right)^{k},\ 1\leq r\leq n_j. \end{equation}

Introduce the vectors

\begin{equation} \label{unknowns} \vec{\mathbf{b}}_i=(a_{d_i},\, a_{d_i+1},\, \ldots ,\, a_{d_i+n_i-1})^{\mathrm{T}}\ (0\leq i\leq q),\ \vec{\mathbf{b}}= (\vec{\mathbf{b}}_0^{\mathrm{T}} ,\vec{\mathbf{b}}_2^{\mathrm{T}},\ldots ,\vec{\mathbf{b}}_q^{\mathrm{T}}) \end{equation}

and the \((N+1)\times (N+1)\) block matrix

\begin{equation} \label{blockmatrix} \mathcal{A}=\begin{pmatrix} A_{0,0} & A_{0,1} & \cdots & A_{0,q} \\ A_{1,0} & A_{1,1} & \cdots & A_{1,q} \\ \vdots & \vdots & \ddots & \vdots \\ A_{q,0} & A_{q,1} & \cdots & A_{q,q} \end{pmatrix} \end{equation}

with \(A_{i,j}\) for \(0\leq i\leq j\leq q\) given by \(n_i\times n_j\) blocks of the form

\begin{equation} \label{blockij}{\footnotesize A_{i,j}\! \! =\! \! \begin{pmatrix} [d_j]_{d_i} \left(z^{[i]}_1\right)^{d_j\! -\! d_i} & [d_j\! +\! 1]_{d_i} \left(z^{[i]}_1\right)^{d_j\! -\! d_i\! +\! 1} & \cdots & [d_j\! +\! n_j-1]_{d_i} \left(z^{[i]}_1\right)^{d_j\! -\! d_i\! +\! n_j-1} \\[d_j]_{d_i} \left(z^{[i]}_2\right)^{d_j\! -\! d_i} & [d_j\! +\! 1]_{d_i} \left(z^{[i]}_2\right)^{d_j\! -\! d_i+1} & \cdots & [d_j\! +\! n_j-1]_{d_i} \left(z^{[i]}_2\right)^{d_j\! -\! d_i\! +\! n_j\! -\! 1} \\ \vdots & \vdots & \ddots & \vdots \\[d_j]_{d_i} \left(z^{[i]}_{n_i}\right)^{d_j\! -\! d_i} & [d_j\! +\! 1]_{d_i} \left(z^{[i]}_{n_i}\right)^{d_j\! -\! d_i+1} & \cdots & [d_j\! +\! n_j-1]_{d_i} \left(z^{[i]}_{n_i}\right)^{d_j\! -\! d_i\! +\! n_j\! -\! 1} \end{pmatrix}\! ,} \end{equation}

and from the values of the \(d_i\) in 6 and the Pochhammer symbols 13 in the blocks, it is immediately clear that the blocks \(A_{i,j}\) with \(0\leq j\lvertneqq i\leq q\) consist of zeroes only!

Then the equations 17 and 18 for \(1\leq j\leq q\) can be written as

\begin{equation} \label{} \mathcal{A}\vec{\mathbf{b}}=\vec{\mathbf{0}}. \end{equation}

where \(\mathcal{A}\) has “upper triangular” block form

\begin{equation} \label{blockdiag} \mathcal{A}=\begin{pmatrix} A_{0,0} & A_{0,1} & A_{0,2} & \cdots & A_{0,q} \\ \mathcal{O}_{1,0} & A_{1,1} & A_{1,2} & \cdots & A_{1,q} \\ \mathcal{O}_{2,0} & \mathcal{O}_{2,1} & A_{2,2} & \cdots & A_{3,q} \\ \vdots & \vdots & & \ddots & \vdots \\ \mathcal{O}_{q,0} & \mathcal{O}_{q,1} & \mathcal{O}_{q,2} & \cdots & A_{q,q} \end{pmatrix}. \end{equation}

Using Laplace expansion and the block structure of \(\mathcal{A}\), we find

\begin{equation} \label{det} \mathrm{det}(\mathcal{A})=\prod _{j=1}^q\, \left(\prod _{k=0}^{n_j-1}\, [d_j+k]_{d_j}\right) \times \prod _{j=0}^q\, V(z^{[j]}_1,\ldots ,z^{[j]}_{n_j}), \end{equation}

where \(V(x_1,\ldots ,x_s)\) denotes the ordinary Vandermonde determinant on
\(x_1,\ldots ,x_s\).

From 24 we see that \(\mathrm{det}(\mathcal{A})\not= 0\), thus \(P_N\equiv 0\) and the problem is regular.â–¡

Bibliography

1: M.G. de Bruin and A. Sharma, Lacunary Pál-type interpolation and over-convergence, Comput. Methods Funct. Theory, 3, nos. 1–2, pp. 305–323, 2003.
2: M.G. de Bruin and D.H. Mache, Pál-type interpolation: a general method for regularity, Buhmann, M.D. & Mache, D.H. (ed.), Advanced problems in constructive approximation. 3rd IDoMAT, Witten-Bommerholz, Germany, August 20-24, 2001, Basel: Birkhäuser. ISNM, International Series of Numerical Mathematics, 142, pp. 21–26, 2003.
3: M.G. de Bruin and D.H. Mache, Pál-type interpolation: a general method for regularity, de Bruin, M.G., Mache, D.H. & Szabados, J., Trends and applications in constructive approximation. 4th IBoMAT, Witten-Bommerholz, Germany, February 15-19, 2004. Basel: Birkhäuser, ISNM, International Series of Numerical Mathematics, 151, pp. 61–70, 2005.
4: A.S. Cavaretta, Jr. A. Sharma and R.S. Varga, Interpolation in the roots of unity: an extension of a theorem of J.L. Walsh, Resultate der Math., 3, pp. 155–191, 1981.
5: G.G. Lorentz, S.D. Riemenschneider and K. Jetter, Birkhoff Interpolation, Addison Wesley Pub. Co., Mass. USA, 1983.
6: L.G. Pál, A new modification of the Hermite-Fejér interpolation, Anal. Math., 1, pp. 197–205, 1975.

This work is licensed under a Creative Commons Attribution 4.0 International License.