MATHEMATICS

V. S. VIDENSKII

ON A CLASS OF INTERPOLATION POLYNOMIALS WITH UNFIXED NODES

(Presented by Academician S. N. Bernstein on 2 XII 1964)

In the work of Ya. Mycielski and S. Paszkowski \((^1)\) the following interesting theorem was proved. Let \(v_0, v_1, \ldots, v_n\) be given positive numbers and let \([a,b]\) be a real interval. There exists a unique sequence of points
\[ a=x_0<x_1<\cdots<x_{n-1}<x_n=b \]
and such an algebraic polynomial \(P_n(x)\) of degree \(n\) that
\[ P_n(x_k)=(-1)^{\,n-k}v_k \quad (k=0,1,\ldots,n); \]
\[ P_n'(x_i)=0 \quad (i=1,\ldots,n-1). \]
In particular, if all \(v_k=1\), then \(P_n(x)\) is the Chebyshev polynomial. Here we generalize this theorem and give a proof based on an entirely different idea than in \((^1)\). Consider a sequence of functions \(\{\varphi_k(x)\}_{k=0}^n\), continuously differentiable on \([a,b]\). We shall write \(\{\varphi_k(x)\}\in T_n\) if every polynomial
\[ P(x)=\sum_{k=0}^n a_k\varphi_k(x) \quad \left(\sum_{k=0}^n |a_k|>0\right) \]
on \([a,b]\) has \(\le n\) zeros. If, moreover, its derivative \(P'(x)\) also has \(\le n\) zeros on \([a,b]\), then we shall write \(\{\varphi_k(x)\}\in T_n'\).

Fix positive numbers \(v_0,v_1,\ldots,v_n\) and, having chosen a system of interpolation nodes
\[ a=\xi_0<\xi_1<\cdots<\xi_{n-1}<\xi_n=b, \]
construct, with respect to \(\{\varphi_k(x)\}\), the polynomial
\[ P(x)=P(x;\xi_0,\xi_1,\ldots,\xi_n)=\sum_{k=0}^n (-1)^{\,n-k}v_k l_k(x), \tag{1} \]
where
\[ l_k(x)=D_k(x)/D[\varphi_0(\xi_0),\varphi_1(\xi_1),\ldots,\varphi_n(\xi_n)], \]
\[ D[\varphi_0(\xi_0),\varphi_1(\xi_1),\ldots,\varphi_n(\xi_n)] = \begin{vmatrix} \varphi_0(\xi_0) & \varphi_1(\xi_0) & \cdots & \varphi_n(\xi_0)\\ \varphi_0(\xi_1) & \varphi_1(\xi_1) & \cdots & \varphi_n(\xi_1)\\ \cdot & \cdot & \cdot & \cdot\\ \varphi_0(\xi_n) & \varphi_1(\xi_n) & \cdots & \varphi_n(\xi_n) \end{vmatrix}, \]
\[ D_k(x)=D[\varphi_0(\xi_0),\ldots,\varphi_{k-1}(\xi_{k-1}),\varphi_k(x),\varphi_{k+1}(\xi_{k+1}),\ldots,\varphi_n(\xi_n)]. \]
The class of polynomials of the form (1), for fixed \(v_k>0\) and arbitrary \(\xi_1<\cdots<\xi_{n-1}\) from \((a,b)\), will be denoted by \(V_n\).

Theorem 1. Let \(\{\varphi_k(x)\}\in T_n\), and suppose that the points
\[ a=\xi_0<\cdots<\xi_{i-1}<\xi_{i+1}<\cdots<\xi_n=b \quad (1\le i\le n-1) \]
and the numbers \(w_0,\ldots,w_{i-1},w_i,w_{i+1},\ldots,w_n\) are given such that
\[ w_{i-1}>0,\quad w_i\le 0,\quad w_{i+1}>0. \]
In \((\xi_{i-1},\xi_{i+1})\) there exists such a point \(\xi_i\) and such a polynomial \(L(x)\) with respect to the system \(\{\varphi_k(x)\}\) that
\[ L(\xi_k)=w_k \quad (k=0,1,\ldots,n);\qquad L'(\xi_i)=0. \]

Adjoin to the points \(\xi_k\) \((k\ne i)\), as an interpolation node, an arbitrary point \(z\) from \((\xi_{i-1},\xi_{i+1})\), and construct the polynomial
\[ L(x)=L(x;\xi_0,\ldots,\xi_{i-1},z,\xi_{i+1},\ldots,\xi_n) =\sum_{k=0}^n w_k l_k(x), \tag{2} \]

where \(l_k(x)\) are the fundamental polynomials for the system of nodes
\(\xi_0<\cdots<\xi_{i-1}<z<\xi_{i+1}<\cdots<\xi_n\). Differentiating formula (2) with respect to \(x\) at the point \(x=z\), we obtain

\[ L'(z)D_i(z)=\sum_{k=0}^{n} w_kD_k'(z)=\Phi(z),\quad \text{where } \quad D_k'(z)=D_k'(x)\big|_{x=z}. \]

We shall show that \(\Phi(\xi_{i-1})\Phi(\xi_{i+1})<0\). Consequently, there is a point \(z=\xi_i,\ \xi_{i-1}<\xi_i<\xi_{i+1}\), such that \(\Phi(\xi_i)=0\), and hence also \(L'(\xi_i)=0\), since \(D_i(\xi_i)=D[\varphi_0(\xi_0),\ldots,\varphi_n(\xi_n)]\ne0\) for \(\{\varphi_k(x)\}\in T_n\). If \(i\ne k\), then
\(D_k'(z)=D[\varphi_0(\xi_0),\ldots,\varphi_i(z),\ldots,\varphi_k'(z),\ldots,\varphi_n(\xi_n)]\). For \(i\ne k\) the determinant \(D_k'(\xi_j)=0\), if \(j\ne i,k\), since it contains two identical rows. Thus,

\[ \Phi(\xi_{i-1})=w_{i-1}D_{i-1}'(\xi_{i-1})+w_iD_i'(\xi_{i-1}),\quad \Phi(\xi_{i+1})=w_iD_i'(\xi_{i+1})+w_{i+1}D_{i+1}'(\xi_{i+1}) \]

The polynomial \(D_i(x)\) vanishes at the \(n\) points \(\xi_j\) \((j\ne i)\); hence the \(\xi_j\) are its simple zeros, and therefore, in particular, \(D_i'(\xi_{i-1})\ne0\). Since the determinant \(D_{i-1}'(\xi_{i-1})\) is obtained from the determinant \(D_i'(\xi_{i-1})\) by interchanging two of its rows, we have
\(D_{i-1}'(\xi_{i-1})=-D_i'(\xi_{i-1})\). We obtain

\[ \Phi(\xi_{i-1})=(-w_{i-1}+w_i)D_i'(\xi_{i-1}),\quad \Phi(\xi_{i+1})=(w_i-w_{i+1})D_i'(\xi_{i+1}), \]

and since \(\xi_{i-1},\xi_{i+1}\) are neighboring simple zeros of the polynomial \(D_i(x)\), it follows that
\(D_i'(\xi_{i-1})D_i'(\xi_{i+1})<0\), and consequently
\(\Phi(\xi_{i-1})\Phi(\xi_{i+1})<0\).

Theorem 2. Let \(\{\varphi_k(x)\}\in T_n'\), and let points be given

\[ a=\xi_0<\xi_1<\cdots<\xi_{i-1}<\xi_{i+r}<\cdots<\xi_{n-1}<\xi_n=b \]
\[ (1\le i\le n-1;\quad 1\le r\le n-1;\quad i+r\le n). \]

In \((\xi_{i-1},\xi_{i+r})\) there exists a unique system of \(r\) points
\(\xi_i<\xi_{i+1}<\cdots<\xi_{i+r-1}\) such that
\(P(x)=P(x;\xi_0,\ldots,\xi_n)\in V_n\) satisfies the conditions

\[ P'(\xi_i)=P'(\xi_{i+1})=\cdots=P'(\xi_{i+r-1})=0. \tag{3} \]

Theorem 2 generalizes the result of [1] in two directions: algebraic polynomials are replaced by polynomials with respect to \(\{\varphi_k(x)\}\in T_n'\), and instead of \(r=n-1\) the condition \(1\le r\le n-1\) is introduced.

We shall prove Theorem 2 by induction applied to the number \(r\). For \(r=1\) the result follows from Theorem 1. Indeed, suppose that in \((\xi_{i-1},\xi_{i+1})\) there exist two points \(\xi_{i1}\) and \(\xi_{i2}\) such that the corresponding polynomials \(P_1(x)\in V_n\) and \(P_2(x)\in V_n\) satisfy the conditions
\(P_1'(\xi_{i1})=0,\ P_2'(\xi_{i2})=0\). Since \(\xi_{i1}\) and \(\xi_{i2}\) are the unique points of maximum of the polynomials \((-1)^{\,n-i}P_1(x)\), \((-1)^{\,n-i}P_2(x)\) in \((\xi_{i-1},\xi_{i+1})\), it follows that
\(v_i=|P_1(\xi_{i1})|>(-1)^{\,n-i}P_2(\xi_{i1})\),
\((-1)^{\,n-i}P_1(\xi_{i2})<|P_2(\xi_{i2})|=v_i\). Hence it follows that the polynomial \(P_1(x)-P_2(x)\) has a zero in \((\xi_{i1},\xi_{i2})\). On the other hand,
\(P_1(\xi_k)-P_2(\xi_k)=0\) \((k\ne i)\); consequently, the total number of zeros of \(P_1(x)-P_2(x)\) is greater than \(n\) on \([a,b]\).

We shall now assume that Theorem 2 has already been established for some fixed number \(r\) \((1\le r\le n-2)\) for any \(i\), and shall show that in this case it is valid also for the number \(r+1\). Thus, let points be given
\(a=\xi_0<\xi_1<\cdots<\xi_{i-1}<\xi_{i+r+1}<\cdots<\xi_n=b\). Adjoin to them an arbitrary point
\(\xi_{i+r}'\), \(\xi_{i-1}<\xi_{i+r}'<\xi_{i+r+1}\). By the induction hypothesis, in
\((\xi_{i-1},\xi_{i+r}')\) there are uniquely found \(r\) points
\(\xi_i'<\xi_{i+1}'<\cdots<\xi_{i+r-1}'\) such that the polynomial

\[ P_1(x)=P_1(x;\xi_0,\ldots,\xi_{i-1},\xi_i',\ldots,\xi_{i+r}',\xi_{i+r+1},\ldots,\xi_n)\in V_n \]

satisfies (3) at these points. If \(P_1'(\xi_{i+r}')=0\), then \(P_1(x)\) is the desired polynomial. If, however, \(P_1'(\xi_{i+r}')\ne0\), then in
\((\xi_{i+r-1}',\xi_{i+r+1})\) there is a point
\(\eta_{i+r}'\), \(\eta_{i+r}'\ne\xi_{i+r}'\), such that
\(P_1(\eta_{i+r}')=(-1)^{\,n-i-r}v_{i+r}\). Next choose

\[ \xi_{i+r}''=\frac12(\xi_{i+r}'+\eta_{i+r}') \]

and repeat the preceding reasoning. In

\((\xi_{i-1}, \xi''_{i+r})\) there are uniquely determined \(r\) points \(\xi''_i < \cdots < \xi''_{i+r-1}\) such that the polynomial

\[ P_2(x)=P_2(x;\xi_0,\ldots,\xi_{i-1},\xi''_i,\ldots,\xi''_{i+r},\xi_{i+r+1},\ldots,\xi_n)\in V_n \]

satisfies conditions (3) at these points. Suppose that \(P_2'(\xi''_{i+r})\ne 0\); denote by \(x'_1<\cdots<x'_n\) the zeros of \(P_1(x)\), and let us show that \(P_1(x)-P_2(x)\ne 0\) in \((x'_{i+r},x'_{i+r+1})\). Indeed, if at some point \(z\), \(x'_{i+r}<z<x'_{i+r+1}\),

\[ P_1(z)=P_2(z)=(-1)^{n-i-r}v^*_{i+r}, \qquad v^*_{i+r}>0, \]

then this would mean that the two distinct polynomials

\[ P_1(x)=P_1(x;\xi_0,\ldots,\xi'_{i+r-1},z,\xi_{i+r+1},\ldots,\xi_n)\in V_n^*, \]

\[ P_2(x)=P_2(x;\xi_0,\ldots,\xi''_{i+r-1},z,\xi_{i+r+1},\ldots,\xi_n)\in V_n^* \]

satisfy conditions (3), where \(V_n^*\) is the class of polynomials obtained from \(V_n\) by replacing \(v_{i+r}\) by \(v^*_{i+r}\). But this contradicts the induction hypothesis on the uniqueness of such a polynomial. Since \(P_1(x)-P_2(x)\ne 0\) in \((\eta'_{i+r},\xi'_{i+r})\subset (x'_{i+r},x'_{i+r+1})\), and since \(P_1(\xi'_{i+r})=P_1(\eta'_{i+r})=P_2(\xi'_{i+r})\), it follows that \(P_2(x)<|P_1(x)|\) for \(x\in[\eta'_{i+r},\xi'_{i+r}]\), and in \((\eta'_{i+r},\xi'_{i+r})\) there is a point \(\eta''_{i+r}\ne \xi'_{i+r}\) such that

\[ P_2(\eta''_{i+r})=(-1)^{n-i-r}v_{i+r}. \]

It is clear that \(|\eta''_{i+r}-\xi''_{i+r}|<\frac12|\eta'_{i+r}-\xi'_{i+r}|\). We shall now show that

\[ \xi_i<\xi''_i,\ldots,\xi'_{i+r-1}<\xi''_{i+r-1}. \tag{4} \]

We shall regard the polynomial \(P_2(x)\) as a continuous image of the polynomial \(P_1(x)\) corresponding to the continuous displacement of the point \(\xi'_{i+r}\) to \(\xi''_{i+r}\). Move the point \(\xi'_{i+r}\) to the point \(\widetilde{\xi}_{i+r}\), and assume that \(|\xi'_{i+r}-\widetilde{\xi}_{i+r}|\) is as small as we need. In \((\xi_{i-1},\widetilde{\xi}_{i+r})\) there are uniquely determined \(r\) points \(\widetilde{\xi}_i<\cdots<\widetilde{\xi}_{i+r-1}\), which are, respectively, small displacements of the points \(\xi'_i<\cdots<\xi'_{i+r-1}\), such that the polynomial

\[ Q'(x)=Q'(x;\xi_0,\ldots,\xi_{i-1},\widetilde{\xi}_i,\ldots,\widetilde{\xi}_{i+r},\ldots,\xi_n)\in V_n' \]

satisfies conditions (3) at the points \(\widetilde{\xi}_i,\ldots,\widetilde{\xi}_{i+r-1}\). If \(|\widetilde{\xi}_k-\xi'_k|\) \((k=i,\ldots,i+r-1)\) are sufficiently small, then

\[ \xi_i<\widetilde{\xi}_i,\ldots,\xi'_{i+r-1}<\widetilde{\xi}_{i+r-1}. \tag{5} \]

Indeed, if for some \(k\) we had \(\widetilde{\xi}_k<\xi'_k\), then the polynomial \(P_1(x)-Q'(x)\) would have two zeros in a neighborhood of the point \(\xi'_k\). In a neighborhood of each of the \(\xi'_j\) it has at least one zero, so that the total number of its zeros in \((\xi_{i-1},\xi_{i+r+1})\) would be \(\ge r+1\), while at the remaining \(n-r\) nodes \(\xi_s\), \(P_1(\xi_s)-Q'(\xi_s)=0\); hence on \([a,b]\) the function \(P_1(x)-Q'(x)\) would have \(\ge n+1\) zeros. This proves also inequalities (4), since inequalities (5) cannot be violated as \(\xi'_{i+r}\to \xi''_{i+r}\).

Continuing the construction process by the same scheme, we obtain \(\{P_m(x)\}\subset V_n\). We see that \(\{\xi_k^{(m)}\}\) \((k=i,\ldots,i+r-1)\), for fixed \(k\), is increasing and bounded; consequently, as \(m\to\infty\) it has a limit \(\xi_k\); \(\{\xi_{i+r}^{(m)}\}\) has a limit as \(m\to\infty\), since

\[ [\eta_{i+r}^{(m)},\xi_{i+r}^{(m)}]\subset[\eta_{i+r}^{(m-1)},\xi_{i+r}^{(m-1)}] \]

and

\[ |\eta_{i+r}^{(m)}-\xi_{i+r}^{(m)}|<2^{-m+1}|\eta'_{i+r}-\xi'_{i+r}|. \]

Let us note that \(\xi_k\ne \xi_{k+1}\). Indeed, if \(\xi_k=\xi_{k+1}\), then \(\{P_m(x)\}\) would converge to a discontinuous function; meanwhile, \(\{P_m(x)\}\) is uniformly bounded on \([\xi'_{i+r-1},\xi'_{i+r}]\), hence it is compact and can have as its limit only a polynomial from \(T_n'\). Put

\[ P(x)=\lim_{m\to\infty}P_m(x). \]

It is easy to see that \(P(x)=P(x;\xi_0,\ldots,\xi_n)\in V_n\) and that

\[ P'(\xi_i)=\cdots=P'(\xi_{i+r})=0. \tag{6} \]

We shall now show that the points \(\xi_i<\cdots<\xi_{i+r}\) and the corresponding polynomial \(P(x)\in V_n\) are uniquely determined by conditions (6). Suppose that there exists another system of points \(\zeta_i<\cdots<\zeta_{i+r}\) such that the polynomial \(Q(x)\in V_n\) corresponding to it satisfies conditions (6) at these points. If \(\xi_{i+r}=\zeta_{i+r}\), then for the two systems of \(r\) points \(\xi_i<\cdots<\xi_{i+r-1}\) and \(\zeta_i<\cdots<\zeta_{i+r-1}\), and for the polynomials \(P(x)\) and \(Q(x)\), conditions (3) would be fulfilled, which contradicts the inductive assumption of uniqueness. Let, for definiteness, \(\xi_{i+r}<\zeta_{i+r}\). We begin our construction process by choosing in \((\xi_{i-1},\xi_{i+r+1})\) an arbitrary point \(\xi'_{i+r}\). Denote by \(X\) the upper bound of those \(\xi'_{i+r}\) starting from which we arrive at the points \(\xi_i<\cdots<\xi_{i+r}\) and at the polynomial \(P(x)\). It is clear that \(X\le \zeta_{i+r}\), since the sequence of contracting intervals \([\eta^{(m)}_{i+r},\xi^{(m)}_{i+r}]\) is constructed uniquely after the point \(\xi'_{i+r}\) has been chosen. Suppose that \(X=\zeta_{i+r}\). Choose \(\xi'_{i+r}<X\) and so close to \(X\) that the polynomial \(Q(x)\) does not change sign in \((\xi'_{i+r},X)\) and so that \(\xi_{i+r}<\xi'_{i+r}\). Then \(\xi'_{i+r}\) will be the right endpoint of the interval \([\eta'_{i+r},\xi'_{i+r}]\), and the corresponding polynomial \(P_1(x)\) will be monotone on \([\xi'_{i+r},\xi_{i+r+1}]\). Hence it follows that \(|P_1(X)|<|Q(X)|,\ |P_1(\xi'_{i+r})|>|Q(\xi'_{i+r})|\). Consequently, in \((\xi'_{i+r},X)\) there is a point \(\mu_{i+r}\) such that
\(P_1(\mu_{i+r})=Q(\mu_{i+r})=(-1)^{\,n-i-r}v^*_{i+r},\ v^*_{i+r}>0\), and this means that two distinct polynomials

\[ \begin{aligned} P_1(x)&=P_1(x;\xi_0,\ldots,\xi_{i+r-1},\mu_{i+r},\ldots,\xi_n)\in V_n^*,\\ Q(x)&=Q(x;\xi_0,\ldots,\xi_{i+r-1},\mu_{i+r},\ldots,\xi_n)\in V_n^* \end{aligned} \]

satisfy conditions (3) at the points \(\xi_i<\cdots<\xi_{i+r-1}\) and \(\zeta_i<\cdots<\zeta_{i+r-1}\), respectively; \(V_n^*\) is the class obtained from \(V_n\) by replacing \(v_{i+r}\) by \(v^*_{i+r}\). We have arrived at a contradiction with the inductive assumption of the uniqueness of such a polynomial. The case \(X<\zeta_{i+r}\) is considered analogously. It is only necessary, in addition to the point \(\xi'_{i+r}<X\), to choose another point \(\zeta'_{i+r}>X\) and, with the aid of our process, to construct the polynomial \(Q_1(x)\), and then repeat arguments similar to those given above.

Leningrad Electrotechnical Institute of Communications
named after M. A. Bonch-Bruevich

Received
1 XII 1964

REFERENCES

1. J. Mycielski, S. Paszkowski, Bull. Acad. Polon. Sci., Ser. math., astronom., phys., 8, No. 7, 433 (1960).