ON CONVERGENCE AND STABILITY OF THE COLLOCATION METHOD

G. M. VAINIKKO

1. Consider the linear ordinary differential equation

\[ u^{(m)}+\sum_{j=0}^{m-1} e_j(s)u^{(j)}=f(s), \tag{1} \]

which is to be integrated on the interval \([a,b]\) under certain homogeneous boundary conditions

\[ \sum_{j=0}^{m-1}\left[\alpha_{ij}u^{(j)}(a)+\beta_{ij}u^{(j)}(b)\right]=0 \quad (\alpha_{ij},\beta_{ij}=\mathrm{const};\ i=1,2,\ldots,m). \tag{2} \]

We shall solve the stated problem by the collocation method.

Suppose that the homogeneous equation \(u^{(m)}=0\) has, under the boundary conditions (2), only the trivial solution \(u(s)\equiv 0\). Then there exists a sequence of polynomials satisfying the boundary conditions (2),

\[ \varphi_k(s)=\sum_{l=0}^{m+k} c_{kl}s^l \quad (c_{k,m+k}\ne 0;\ k=0,1,2,\ldots) \tag{3} \]

of degrees \(m,m+1,m+2,\ldots\), respectively. We take the sequence \(\{\varphi_k(s)\}_{k=0}^{\infty}\) as a coordinate system.

Let a nonnegative summable function \(\rho(s)\) be given on the segment \([a,b]\) such that

\[ \int_a^b \frac{ds}{\rho(s)}<\infty, \tag{4} \]

and let \(\{\omega_n(s)\}_{n=0}^{\infty}\) be a system of polynomials (of degree \(n\)) orthogonal on the segment \([a,b]\) with weight \(\rho(s)\). As the interpolation nodes we take the roots of the polynomials \(\omega_n(s)\).

Thus, the approximate solution of the boundary-value problem \(\{(1),(2)\}\) is sought in the form

\[ u_n(s)=\sum_{k=0}^{n} a_k^{(n)}\varphi_k(s); \tag{5} \]

the constants \(a_k^{(n)}\) are determined by the collocation method from the condition that the residual vanish at the \(n+1\) interpolation nodes \(s_0^{(n)},s_1^{(n)},\ldots,s_n^{(n)}\)—the roots of the polynomial \(\omega_{n+1}(s)\):

\[ u_n^{(m)}(s_i^{(n)})+\sum_{j=0}^{m-1} e_j(s_i^{(n)})u_n^{(j)}(s_i^{(n)})-f(s_i^{(n)})=0\quad (i=0,1,\ldots,n). \tag{6} \]

This leads to an easily formed system of algebraic equations with respect to the unknowns \(a_k^{(n)}\):

\[ \sum_{k=0}^{n}\left[\varphi_k^{(m)}(s_i^{(n)})+ \sum_{j=0}^{m-1} e_j(s_i^{(n)})\varphi_k^{(j)}(s_i^{(n)})\right]a_k^{(n)} =f(s_i^{(n)})\quad (i=0,1,\ldots,n). \tag{7} \]

1. The convergence of the collocation method \(\{(5),(7)\}\) under certain restrictions was established by E. B. Karpilovskaya [1]–[3] with the aid of the general theory of approximate methods developed by L. V. Kantorovich. In the present paper we give a direct proof of convergence. This will allow us, on the one hand, to weaken the restrictions on the coefficients and the free term of equation (1) and, on the other hand, to refine estimates of the rate of convergence of the approximations \(u_n(s)\) and of their derivatives up to order \(m-1\) inclusive. Moreover, the proof proposed has the advantage that we need not consider separately the Chebyshev nodes \(\left(\text{the case } \rho(s)=\right.\)

\[ \left.=\frac{1}{\sqrt{(s-a)(b-s)}}\right), \]

the Gaussian nodes (the case \(\rho(s)=1\)), etc.; all these cases lead us to one and the same result.

Theorem 1. Let the coefficients \(e_j(s)\) and the free term \(f(s)\) of equation (1) be continuous on the interval \([a,b]\), and let the boundary-value problem \(\{(1),(2)\}\) have a unique solution \(u_0(s)\). Then, for all sufficiently large \(n\), the system of equations (7) is uniquely solvable, and the sequences of approximate solutions \(u_n(s)\) and of their derivatives up to order \(m-1\) inclusive converge, as \(n\to\infty\), uniformly to the solution \(u_0(s)\) and to its derivatives of the corresponding order, while the sequence \(u_n^{(m)}(s)\) converges to \(u_0^{(m)}(s)\) in the mean-square sense with weight \(\rho(s)\). The rate of convergence is characterized by the inequalities

\[ \left[\int_a^b \rho(s)\left|u_n^{(m)}(s)-u_0^{(m)}(s)\right|^2\,ds\right]^{1/2} \le CE_n(u_0^{(m)}), \tag{8} \]

\[ \max_{a\le s\le b}\left|u_n^{(j)}(s)-u_0^{(j)}(s)\right| \le CE_n(u_0^{(m)})\quad (j=0,1,\ldots,m-1), \tag{8′} \]

where \(C\) is a constant independent of \(n\) and of the free term \(f(s)\) of equation (1), and \(E_n(u_0^{(m)})\) is the best uniform approximation of the function \(u_0^{(m)}(s)\) by polynomials of degree not exceeding \(n\).

Proof. Denote by \(G(s,t)\) the Green’s function of the differential expression \(u^{(m)}\) under the boundary conditions (2). Setting \(v_n(s)=u_n^{(m)}(s)\), we have

\[ u_n^{(j)}(s)=\int_a^b \frac{\partial^j G(s,t)}{\partial s^j}\,v_n(t)\,dt \quad (j=0,1,\ldots,m-1), \]

and conditions (6) will be written as follows:

\[ v_n(s_i^{(n)})+\sum_{j=0}^{m-1} e_j(s_i^{(n)}) \int_a^b \frac{\partial^j G(s_i^{(n)},t)}{\partial s^j}\,v_n(t)\,dt -f(s_i^{(n)})=0\quad (i=0,1,\ldots,n). \tag{6′} \]

Let \(P_n\) be the linear projection operator that assigns to each function its Lagrange interpolation polynomial of degree \(n\), constructed at the nodes \(s_0^{(n)}, s_1^{(n)}, \ldots, s_n^{(n)}\). Conditions \((6')\) mean that

\[ P_n(v_n+Kv_n-f)=0, \]

where \(K\) is the integral operator with kernel

\[ K(s,t)=\sum_{j=0}^{m-1} e_j(s)\frac{\partial^j G(s,t)}{\partial s^j} \qquad \left(Kv=\int_a^b K(s,t)v(t)\,dt\right). \]

But the function \(v_n(s)\) itself is a polynomial of degree not exceeding \(n\); hence \(P_n v_n=v_n\), and therefore conditions (6) are equivalent to the condition

\[ v_n+P_nKv_n=P_n f, \tag{9} \]

which we shall regard as an equation (with respect to the unknown \(v_n\)) in the space \(L_\rho^2=L_\rho^2[a,b]\) of functions square-summable on the interval \([a,b]\) with weight \(\rho(s)\).

In view of the continuity of the coefficients \(e_j(s)\) and the known properties of the Green’s function, the kernel \(K(s,t)\) is continuous in the square \(a\le s,t\le b\), except, possibly, on the line \(s=t\), where, for \(e_{m-1}(s)\ne 0\), the kernel \(K(s,t)\) has a finite jump discontinuity. Taking condition (4) into account, we have

\[ \max_{a\le s\le b}\int_a^b \frac{|K(s,t)|^2}{\rho(t)}\,dt=M^2<\infty. \tag{10} \]

It is also not difficult to see that for any \(\varepsilon>0\) there exists \(\delta>0\) such that

\[ \int_a^b \frac{|K(s_1,t)-K(s_2,t)|^2}{\rho(t)}\,dt<\varepsilon^2 \tag{11} \]

for all \(s_1,s_2\in[a,b]\) satisfying the inequality \(|s_1-s_2|<\delta\). Setting \(w=Kv\), we find, by means of Bunyakovsky’s inequality, that

\[ \max_{a\le s\le b}|w(s)| = \max_{a\le s\le b} \left| \int_a^b \frac{K(s,t)}{\sqrt{\rho(t)}}\sqrt{\rho(t)}\,v(t)\,dt \right| \le \]

\[ \le \max_{a\le s\le b} \left[ \int_a^b \frac{|K(s,t)|^2}{\rho(t)}\,dt \right]^{1/2} \|v\|, \]

\[ |w(s_1)-w(s_2)| = \left| \int_a^b \frac{K(s_1,t)-K(s_2,t)}{\sqrt{\rho(t)}}\sqrt{\rho(t)}\,v(t)\,dt \right| \le \]

\[ \le \left[ \int_a^b \frac{|K(s_1,t)-K(s_2,t)|^2}{\rho(t)}\,dt \right]^{1/2} \|v\|, \]

where

\[ \|v\|=\left[\int_a^b \rho(t)|v(t)|^2\,dt\right]^{1/2}. \]

— the norm of the function \(v(s)\) in the space \(L_\rho^2\). Together with (10) and (11), this gives

\[ \max_{a \leq s \leq b} |w(s)| \leq M\|v\|,\quad |w(s_1)-w(s_2)|<\varepsilon\|v\|\quad (w=Kv), \]

provided \(|s_1-s_2|<\delta\). The last inequalities mean that the operator \(K\) maps the unit sphere of the space \(L_\rho^2\) into a set of functions that are bounded in the aggregate and equicontinuous, i.e. into a compact set of the space \(C=C[a,b]\) of functions continuous on the interval \([a,b]\). Consequently, the operator \(K\) is completely continuous as an operator mapping the space \(L_\rho^2\) into the space \(C\).

By the Erdős–Turán theorem (see [4], p. 547), the Lagrange interpolation polynomial of any continuous function, constructed with respect to the interpolation nodes considered by us, converges in mean square with weight \(\rho(s)\) to the function being approximated. In other words, the sequence of operators \(P_n\), considered as operators from \(C\) into \(L_\rho^2\), converges strongly to the embedding operator \(I\) of the space \(C\) into the space \(L_\rho^2\). Hence we immediately obtain two consequences important for us. First, on the basis of the Banach–Steinhaus theorem the norms of the operators \(P_n \in [C \to L_\rho^2]\) are bounded in the aggregate:

\[ \|P_n\|\leq \sigma=\operatorname{const}\quad (P_n\in [C\to L_\rho^2];\ n=1,2,\ldots). \tag{12} \]

Second, multiplying the operators \(P_n\in [C\to L_\rho^2]\) on the right by the completely continuous operator \(K\in [L_\rho^2\to C]\), we obtain a sequence of operators \(P_nK\in [L_\rho^2\to L_\rho^2]\) converging to the operator \(IK=K\) already in norm:

\[ \|P_nK-K\|\to 0\quad \text{as } n\to\infty \quad (K,\ P_nK\in [L_\rho^2\to L_\rho^2]). \tag{13} \]

To the solution \(u_0(s)\) of the boundary-value problem \(\{(1),(2)\}\) there corresponds the solution \(v_0(s)=u_0^{(m)}(s)\) of the equation

\[ v+Kv=f, \tag{14} \]

and this solution is unique in the class of functions \(L_\rho^2\). Obviously, the operator \(K\) is completely continuous also as an operator from \(L_\rho^2\) into \(L_\rho^2\). Hence there exists a bounded inverse operator \((E+K)^{-1}\in [L_\rho^2\to L_\rho^2]\) (\(E\) is the identity operator), and from (13) it follows that, for sufficiently large \(n\) (for \(n\geq n_0\)), the operators \(E+P_nK\) are also invertible, and the norms of the inverse operators are bounded in the aggregate:

\[ \|(E+P_nK)^{-1}\|\leq \chi=\operatorname{const}\quad ((E+P_nK)^{-1}\in [L_\rho^2\to L_\rho^2];\ n=n_0,n_0+1,\ldots). \tag{15} \]

Thus, for \(n\geq n_0\), equation (9) has a unique solution \(v_n(s)\), and this is equivalent to the unique solvability of the system of equations (7). We have

\[ (E+P_nK)v_0=P_n(E+K)v_0+(v_0-P_nv_0)=P_nf+(v_0-P_nv_0). \]

Together with (9) this gives

\[ (E+P_nK)(v_0-v_n)=v_0-P_nv_0. \tag{16} \]

Let \(p_n(s)\) be any polynomial of degree not higher than \(n\). From (16), with the aid of relations (15) and (12), we find that

\[ \|v_n-v_0\|\leq \chi \|v_0-P_n v_0\|=\chi \|(v_0-p_n)-P_n(v_0-p_n)\|\leq \]

\[ \leq \chi\bigl(\|v_0-p_n\|+\|P_n(v_0-p_n)\|\bigr)\leq \]

\[ \leq \chi\left(\sqrt{\int_a^b \rho(t)\,dt}+\sigma\right)\max_{a\leq s\leq b}|v_0(s)-p_n(s)|. \]

Hence, recalling that \(v_0(s)=u_0^{(m)}(s)\), \(v_n(s)=u_n^{(m)}(s)\), we obtain estimate (8).

The relations

\[ u_n^{(j)}(s)-u_0^{(j)}(s)=\int_a^b \frac{\partial^j G(s,t)}{\partial s^j}\bigl(u_n^{(m)}(t)-u_0^{(m)}(t)\bigr)\,dt \qquad (j=0,1,\ldots,m-1) \]

imply the inequalities

\[ |u_n^{(j)}(s)-u_0^{(j)}(s)|\leq M_j\|u_n^{(m)}-u_0^{(m)}\| \]

\[ \left( M_j=\max_{a\leq s\leq b} \left[ \int_a^b \left| \frac{\partial^j G(s,t)}{\partial s^j} \right|^2 \frac{dt}{\rho(t)} \right]^{1/2} \right), \]

and estimates \((8')\) follow from estimate (8).

Finally, the assertions of the theorem on the convergence of the sequences of approximations \(u_n(s)\) and of their derivatives follow in an obvious way from estimates (8) and \((8')\). Theorem 1 is proved.

Let the coefficients \(e_i(s)\) and the free term \(f(s)\) of equation (1) be continuously differentiable \(r\) (\(r\geq 0\)) times, and let their \(r\)-th derivatives satisfy a Lipschitz condition with exponent \(\alpha\). Then the function \(u_0^{(m)}(s)\) has the same differentiability properties, and, by Jackson’s theorem, \(E_n(u_0^{(m)})=O(n^{-r-\alpha})\). Thus estimates (8) and \((8')\) have order \(O(n^{-r-\alpha})\). The estimates of E. B. Karpilovskaya are coarser: in the case of Chebyshev nodes they have order \(O(n^{-r-\alpha}\ln n)\), in the case of Gauss nodes order \(O(n^{-r-\alpha+1/2})\), and in the case of an arbitrary weight function \(\rho(s)\geq \rho_0>0\) order \(O(n^{-r-\alpha+1})\). It is assumed, respectively, that \(r+\alpha>0\), \(r+\alpha>\dfrac12\), \(r+\alpha>1\). We note that one arrives at the results of E. B. Karpilovskaya by the method of proof of Theorem 1 if equations (9) and (14) are considered (not in the space \(L_\rho^2\), but) in the space \(C\).

Remark 1. The convergence \(\|u_n^{(m)}-u_0^{(m)}\|\to 0\) is not uniform with respect to the unit sphere \(\|u_0^{(m)}\|=1\): whatever numbers \(n\) and \(N\) we fix, there exists such a free term \(f\in C\) of equation (1) for which

\[ \|u_n^{(m)}\|>N\|u_0^{(m)}\|. \tag{17} \]

Indeed, from (16) it follows that

\[ \|u_n^{(m)}-u_0^{(m)}\|\geq \frac{1}{1+\|P_nK\|}\,\|u_0^{(m)}-P_nu_0^{(m)}\|; \]

whence

\[ \|u_n^{(m)}\|\geq \frac{1}{1+\|P_nK\|}\,\|P_nu_0^{(m)}\| -\frac{2+\|P_nK\|}{1+\|P_nK\|}\,\|u_0^{(m)}\|. \]

Now, in order to construct inequality (17), it suffices to observe that, as proved, the norms \(\|P_n\tilde K\|\) \((n=n_0, n_0+1,\ldots)\) are uniformly bounded, while the operator \(P_n^{-1}[L_\rho^2\to L_\rho^2]\) is unbounded.

We also note that, on the basis of (16), (15), and (12),

\[ \|u_n^{(m)}\|\le a\max_{a\le s\le b}|u_0^{(m)}(s)|, \tag{17'} \]

where the constant

\[ a=(\varkappa+1)\sqrt{\int_a^b \rho(s)\,ds}+\varkappa\sigma \]

does not depend on \(n\) and on the free term \(f\in C\) of equation (1). Thus, inequality (17), with a large number \(N\), may hold for those \(f\in C\) for which the norm \(\|u_0^{(m)}\|\) is significantly smaller than \(\max_{a\le s\le b}|u_0^{(m)}(s)|\).

1. The concept of stability of approximate methods of Galerkin type (the Ritz, Bubnov—Galerkin, and Galerkin—Petrov methods) was introduced and studied in recent works by S. G. Mikhlin and his students (see [5]—[8]). Here we study the collocation method from an analogous point of view, setting ourselves the aim of introducing the concept of stability in such a way as to obtain simple necessary and sufficient conditions for it.

When forming the system of equations (7), the matrix of the system and the column of free terms are always computed with certain errors \(\gamma_{ik}^{(n)}\) and \(\delta_i^{(n)}\) \((i,k=0,1,\ldots,n)\), respectively, as a result of which we in fact solve not system (7), but the “inexact” system

\[ \sum_{k=0}^{n}\left[\varphi_k^{(m)}(s_i^{(n)})+ \sum_{j=0}^{m-1} e_j(s_i^{(n)})\varphi_k^{(j)}(s_i^{(n)})+\gamma_{ik}^{(n)}\right]\tilde a_k^{(n)} = \]

\[ = f(s_i^{(n)})+\delta_i^{(n)} \quad (i=0,1,\ldots,n) \tag{7'} \]

and obtain the “inexact” approximation

\[ \tilde u_n(s)=\sum_{k=0}^{n}\tilde a_k^{(n)}\varphi_k(s). \]

Naturally, it becomes necessary to study the dependence of the error \(u_n(s)-\tilde u_n(s)\) on the errors \(\gamma_{ik}^{(n)}\) and \(\delta_i^{(n)}\).

In what follows, the vectors \(a^{(n)}=(a_0^{(n)},a_1^{(n)},\ldots,a_n^{(n)})\) and \(\tilde a^{(n)}=(\tilde a_0^{(n)},\tilde a_1^{(n)},\ldots,\tilde a_n^{(n)})\) will be regarded as elements of the space \(R_{n+1}\) (in which the norm is

\[ \|a^{(n)}\|=\left[\sum_{k=0}^{n}|a_k^{(n)}|^2\right]^{1/2}\right), \]

while the vectors \(f^{(n)}=(f(s_0^{(n)}),f(s_1^{(n)}),\ldots,f(s_n^{(n)}))\) and \(\delta^{(n)}=(\delta_0^{(n)},\delta_1^{(n)},\ldots,\delta_n^{(n)})\) are regarded as elements of the space \(m_{n+1}\) (in which the norm is

\[ \|\delta^{(n)}\|=\max_{0\le i\le n}|\delta_i^{(n)}|. \]

The matrix \(A_n\) of the system of equations (7) and the matrix of errors \(\Gamma_n=(\gamma_{ik})_{i,k=0}^{n}\) will be regarded as operators mapping the space \(R_{n+1}\) into the space \(m_{n+1}\). Correspondingly, below one must understand the norm \(\|\Gamma_n\|\) in this sense, so that, for example,

\[ \|\Gamma_n\|\le \max_{0\le i\le n}\left[\sum_{k=0}^{n}|\gamma_{ik}^{n}|^2\right]^{1/2}. \]

We shall investigate the stability of the collocation method in the following sense.

Definition. The collocation method \(\{(5),(7)\}\) will be called stable if there exist positive constants \(p, q\), and \(r\), independent of \(n\) and of the right-hand side \(f\in C\) of equation (1), such that for all sufficiently large \(n\) (for \(n\ge n_0\)), when \(\|\Gamma_n\|\le r\), the system of equations \((7')\) is uniquely solvable and

\[ \|u_n^{(m)}-\widetilde u_n^{(m)}\|\le p\|u_n^{(m)}\|\,\|\Gamma_n\|+q\|\delta^{(n)}\|. \tag{18} \]

(By the norm \(\|\cdot\|\) of a function we still mean its norm in the space \(L_\rho^2\).) If the collocation method is not stable in the indicated sense, then we shall call it unstable.

From (18) there follow the inequalities

\[ \max_{a\le s\le b}\left|u_n^{(j)}(s)-\widetilde u_n^{(j)}(s)\right| \le M_j\left(p\|u_n^{(m)}\|\,\|\Gamma_n\|+q\|\delta^{(n)}\|\right) \quad (j=0,1,\ldots,m-1), \]

where \(M_j\) are certain constants (introduced above). We also recall (see \((17')\)) that the sequence \(\|u_n^{(m)}\|\) \((n=n_0,n_0+1,\ldots)\) is bounded for any right-hand side \(f\in C\) of equation (1).

Starting from the coordinate sequence (3), construct the sequence of functions \(\psi_k(s)=\varphi_k^{(m)}(s)\) \((k=0,1,2,\ldots)\). It is known that the smallest eigenvalue \(\lambda_1^{(n)}\) of the matrix

\[ \Psi_n=\left(\int_a^b \rho(s)\psi_i(s)\overline{\psi_k(s)}\,ds\right)_{i,k=0}^n \]

is positive and the sequence \(\{\lambda_1^{(n)}\}\) is nonincreasing. Hence there exists a nonnegative limit

\[ \lambda_1=\lim_{n\to\infty}\lambda_1^{(n)}. \]

If \(\lambda_1>0\), i.e., if the eigenvalues of the matrices \(\Psi_n\) are bounded below by a positive number \(\lambda_1\) independent of \(n\), then the sequence \(\{\psi_k(s)\}_{k=0}^{\infty}\), according to the accepted terminology, is called strongly minimal in the space \(L_\rho^2\). In particular, the orthonormalized (in the sense of the metric of the space \(L_\rho^2\)) sequence of polynomials

\[ \chi_k(s)=\frac{\omega_k(s)}{\|\omega_k\|} \quad (k=0,1,2,\ldots) \]

(see item 1) will be strongly minimal.

The theorem 2 below shows that it is expedient to construct the coordinate sequence, in particular, so that

\[ \varphi_k^{(m)}(s)=\chi_k(s)\quad (k=0,1,2,\ldots). \]

Theorem 2. Suppose that the conditions of Theorem 1 are satisfied. Then, for the stability of the collocation method \(\{(5),(7)\}\), it is necessary and sufficient that the sequence

\[ \psi_k(s)=\varphi_k^{(m)}(s)\quad (k=0,1,2,\ldots) \]

be strongly minimal in the space \(L_\rho^2\).

Proof. Using the ordinary orthogonalization method, we orthonormalize the sequence \(\psi_k(s)\):

\[ \chi_i(s)=\sum_{k=0}^{i} d_{ik}\psi_k(s),\qquad \int_a^b \rho(s)\chi_i(s)\overline{\chi_j(s)}\,ds=\delta_{ij} = \begin{cases} 1 & \text{if } i=j,\\ 0 & \text{if } i\ne j \end{cases} \]

\[ (d_{ii}\ne 0;\ i,j=0,1,2,\ldots). \]

Introduce into consideration the triangular matrix

\[ D_n=(d_{ik})_{i,k=0}^{n}\qquad (d_{ik}=0\ \text{if } i<k). \]

For \(i, j \leq n\) the condition
\(\int_a^b \rho(s)\chi_i(s)\overline{\chi_j(s)}\,ds=\delta_{ij}\) is written in the form

\[ \sum_{k=0}^{n} d_{ik}\sum_{l=0}^{n}\overline{d}_{jl} \int_a^b \rho(s)\psi_k(s)\overline{\psi_l(s)}\,ds=\delta_{ij}, \]

i.e.,
\[ D_n\Psi_n D_n^{*}=I_n, \]
where \(I_n\) is the identity matrix, and \(D_n^{*}\) is the matrix adjoint to \(D_n\). Hence
\(\Psi_n^{-1}=D_n^{*}D_n\), and therefore

\[ \|D_n\|=\sqrt{\|\Psi_n^{-1}\|} =\frac{1}{\sqrt{\lambda_1^{(n)}}} \qquad (D_n\in [R_{n+1}\to R_{n+1}]). \tag{19} \]

Denote by \(D_n'\) the matrix obtained by transposing the matrix \(D_n\), and set

\[ b^{(n)}=(D_n')^{-1}a^{(n)} =(b_0^{(n)},\, b_1^{(n)},\ldots, b_n^{(n)}), \]

\[ \widetilde b^{(n)}=(D_n')^{-1}\widetilde a^{(n)} =(\widetilde b_0^{(n)},\, \widetilde b_1^{(n)},\ldots, \widetilde b_n^{(n)}) \quad (b^{(n)},\,\widetilde b^{(n)}\in R_{n+1}), \]

\[ A_nD_n'=B_n,\qquad \Gamma_nD_n'=\Gamma_n' \quad (B_n,\Gamma_n'\in [R_{n+1}\to m_{n+1}]). \]

Let us verify that

\[ \|u_n^{(m)}\|=\|b^{(n)}\|, \tag{20} \]

\[ \|u_n^{(m)}-\widetilde u_n^{(m)}\| =\|b^{(n)}-\widetilde b^{(n)}\|. \tag{20'} \]

Indeed, we have \(a^{(n)}=D_n'b^{(n)}\),

\[ u_n^{(m)}(s)=\sum_{k=0}^{n}a_k^{(n)}\varphi_k^{(m)}(s) =\sum_{k=0}^{n}a_k^{(n)}\psi_k(s) =\sum_{k=0}^{n}\left(\sum_{i=0}^{n}d_{ik}b_i^{(n)}\right)\psi_k(s) \]

\[ =\sum_{i=0}^{n}b_i^{(n)}\sum_{k=0}^{n}d_{ik}\psi_k(s) =\sum_{i=0}^{n}b_i^{(n)}\chi_i(s), \]

and to derive relation (20) it remains only to take into account the orthonormality in \(L_\rho^2\) of the sequence \(\{\chi_i(s)\}\). Relation (20′) is established analogously.

The systems of equations (7) and (7′), which in operator notation have the form

\[ A_na^{(n)}=f^{(n)},\qquad (A_n+\Gamma_n)\widetilde a^{(n)}=f^{(n)}+\delta^{(n)}, \]

are equivalent to the operator equations

\[ B_nb^{(n)}=f^{(n)},\qquad (B_n+\Gamma_n')\widetilde b^{(n)}=f^{(n)}+\delta^{(n)}, \]

whence

\[ (B_n+\Gamma_n')(b^{(n)}-\widetilde b^{(n)}) =\Gamma_n'b^{(n)}-\delta^{(n)}. \tag{21} \]

In view of the unique solvability of the system of equations (7) (see Theorem 1), the operator \(B_n\) is invertible for \(n\geq n_0\). We shall show that the norms of the inverse operators are bounded above and below by positive numbers independent of \(n\):

\[ \beta_0 \leq \|B_n^{-1}\| \leq \beta_1 \tag{22} \]

\[ \bigl(B_n^{-1}\in [m_{n+1}\to R_{n+1}];\ \beta_0,\beta_1=\operatorname{const}>0;\ n=n_0,n_0+1,\ldots\bigr). \]

Indeed, in view of the complete continuity of the operator \(K \in [C \to C]\) (see above), it follows from (14) that there exists such a constant \(\varkappa_1\) that for any right-hand side \(f \in C\) of equation (1)

\[ \max_{a \le s \le b}\left|u_0^{(m)}(s)\right| = \max_{a \le s \le b}|v_0(s)| \le \varkappa_1 \max_{a \le s \le b}|f(s)|. \]

Together with (17′) this gives

\[ \left\|u_n^{(m)}\right\| \le \beta_1 \max_{a \le s \le b}|f(s)|, \tag{23} \]

where the constant \(\beta_1=\alpha\varkappa_1\) does not depend on \(n\) or on \(f \in C\). In forming the system of equations (7), the values of the function \(f(s)\) are used only at the nodes \(s_i^{(n)}\) \((i=0,1,\ldots,n)\); therefore the approximation \(u_n(s)\) will not change if, in equation (1), we replace \(f(s)\) by any continuous function taking at the nodes \(s_i^{(n)}\) \((i=0,1,\ldots,n)\) the same values as \(f(s_i^{(n)})\). Hence it is clear that in fact, instead of (23), the stronger inequality holds

\[ \left\|u_n^{(m)}\right\| \le \beta_1 \max_{0\le i\le n}\left|f\left(s_i^{(n)}\right)\right| = \beta_1\left\|f^{(n)}\right\|. \]

Using (20), we write this inequality in the form

\[ \left\|B_n^{-1} f^{(n)}\right\|=\left\|b^{(n)}\right\|\le \beta_1\left\|f^{(n)}\right\|. \]

The vector \(f^{(n)}\) ranges over the whole space \(m_{n+1}\) if the function \(f(s)\) ranges over the whole space \(C\), and from the last inequality there follow the estimates \(\left\|B_n^{-1}\right\|\le \beta_1\) \((n=n_0,n_0+1,\ldots)\). On the basis of the equality \(\left\|u_n^{(m)}\right\|=\left\|B_n^{-1}f^{(n)}\right\|\), it is also easy to establish the estimate (22) of the norms \(\left\|B_n^{-1}\right\|\) from below: if the sequence \(\left\|B_n^{-1}\right\|\) \((n=n_0,n_0+1,\ldots)\) tended to zero (or contained a subsequence converging to zero), then for every right-hand side \(f(s)\) of equation (1) we would have \(\left\|u_n^{(m)}\right\|\to 0\), which, however, is impossible, since by Theorem 1 \(\left\|u_n^{(m)}\right\|\to \left\|u_0^{(m)}\right\|\).

Sufficiency. Let the sequence \(\psi_k(s)=\varphi_k^{(m)}(s)\) \((k=0,1,2,\ldots)\) be strongly minimal in the space \(L_\rho^2\), i.e. \(\lim_{n\to\infty}\lambda_1^{(n)}=\lambda_1>0\), and (see (19))

\[ \left\|D_n'\right\|=\left\|D_n\right\|=\frac{1}{\sqrt{\lambda_1^{(n)}}}\le \frac{1}{\sqrt{\lambda_1}} \qquad \left(D_n'\in [R_{n+1}\to R_{n+1}];\ n=1,2,\ldots\right). \]

Let \(\|\Gamma_n\|\le \dfrac{\sqrt{\lambda_1}}{2\beta_1}=r\). Then \(\|\Gamma_n'\|\le \|\Gamma_n\|\,\|D_n'\|\le \dfrac{1}{2\beta_1}\), and from (22) we conclude that the operator \(B_n+\Gamma_n'\) is invertible (and, consequently, the system of equations (7′) is uniquely solvable), and moreover

\[ \left\|(B_n+\Gamma_n')^{-1}\right\|\le 2\beta_1 \qquad \left((B_n+\Gamma_n')^{-1}\in [m_{n+1}\to R_{n+1}];\ n=n_0,n_0+1,\ldots\right). \]

Now from (21), with the aid of (20) and (20′), we find that

\[ \left\|u_n^{(m)}-\widetilde{u}_n^{(m)}\right\| = \left\|b^{(n)}-\widetilde{b}^{(n)}\right\| \le 2\beta_1\left(\|\Gamma_n'\|\,\left\|b^{(n)}\right\|+\left\|\delta^{(n)}\right\|\right) \le \]

\[ \le 2\beta_1\left( \frac{1}{\sqrt{\lambda_1}}\left\|u_n^{(m)}\right\|\,\|\Gamma_n\| + \left\|\delta^{(n)}\right\| \right), \]

i.e. the collocation method is stable.

Necessity. Below we shall prove the existence of such a sequence of free terms \(f_n(s)\) of equation (1) and such a sequence of error matrices \(\Gamma_n\) (\(\|\Gamma_n\|\to 0\) as \(n\to\infty\)) that, for \(\delta^{(n)}=0\), the corresponding approximations \(u_n(s)\) and \(\tilde u_n(s)\) satisfy the inequalities

\[ \|u_n^{(m)}-\tilde u_n^{(m)}\| \ge \frac{\beta_0}{2\sqrt{\lambda_1^{(n)}}}\, \|u_n^{(m)}\|\,\|\Gamma_n\| \qquad (n=n_0,\ n_0+1,\ldots), \]

where \(\beta_0\) (\(\beta_0>0\)) is the constant introduced by inequalities (22). If the sequence \(\psi_k(s)=\varphi_k^{(m)}(s)\) \((k=0,1,2,\ldots)\) is not strongly minimal in the space \(L_\rho^2\), i.e., if

\[ \frac{1}{\sqrt{\lambda_1^{(n)}}}\to\infty \quad \text{as } n\to\infty, \]

then these inequalities contradict condition (18), and the collocation method will be unstable.

If the free term of equation (1), \(f(s)\), ranges over the space \(C\), then the vector \(b^{(n)}\) ranges over the whole space \(R_{n+1}\). Taking into account relations (20), \((20')\), and (21), we reduce our problem to the following one: construct a sequence of vectors \(b^{(n)}\in R_{n+1}\) and a sequence of matrices \(\Gamma_n\) (\(\|\Gamma_n\|\to 0\) as \(n\to\infty\)) such that, for the vectors

\[ b^{(n)}-\tilde b^{(n)} = (B_n+\Gamma_n')^{-1}\Gamma_n D_n' b^{(n)} \tag{21'} \]

the inequalities

\[ \|b^{(n)}-\tilde b^{(n)}\| \ge \frac{\beta_0}{2\sqrt{\lambda_1^{(n)}}}\, \|b^{(n)}\|\,\|\Gamma_n\| \qquad (n=n_0,\ n_0+1,\ldots) \tag{24} \]

hold.

Subjecting the matrix \(\Gamma_n\) to the condition

\[ \|\Gamma_n\|\le \frac{\sqrt{\lambda_1^{(n)}}}{2\beta_1}, \tag{25} \]

we have, by virtue of (22) and (19),

\[ \|B_n^{-1}\Gamma_n'\| \le \|B_n^{-1}\|\,\|\Gamma_n\|\,\|D_n\| \le \frac{1}{2} \]

and

\[ \|(B_n+\Gamma_n')^{-1}\| = \|(I_n+B_n^{-1}\Gamma_n')^{-1}B_n^{-1}\| \ge \frac{\|B_n^{-1}\|}{\|I_n+B_n^{-1}\Gamma_n'\|} \ge \frac{\beta_0}{2} \tag{22'} \]

\[ (n=n_0,\ n_0+1,\ldots). \]

Choose a normalized vector \(b^{(n)}\in R_{n+1}\) so that

\[ \|D_n'b^{(n)}\|=\|D_n'\| = \frac{1}{\sqrt{\lambda_1^{(n)}}}. \]

Next, let the matrix \(\Gamma_n\) assign to the vector \(a^{(n)}=D_n'b^{(n)}\) the vector

\[ \frac{1}{n}\,c^{(n)}, \]

where \(c^{(n)}\) is some normalized vector of the space \(m_{n+1}\) (it will be fixed later). The matrix \(\Gamma_n\) will be uniquely determined if, in addition, we require that to every vector,

orthogonal to \(a^{(n)}\), to the zero vector; it is not difficult to see that

\[ \|\Gamma_n\|=\frac{1}{n}\sqrt{\lambda_1^{(n)}} . \tag{26} \]

Therefore, for sufficiently large \(n\) (let this be for \(n \ge n_0\)) condition (25) is fulfilled, and at the same time \((22')\) holds. We now choose, for each \(n\) \((n \ge n_0)\), a vector \(c^{(n)} \in m_{n+1}\) \((\|c^{(n)}\|=1)\) so that

\[ \|(B_n+\Gamma'_n)^{-1}c^{(n)}\|=\|(B_n+\Gamma'_n)^{-1}\| \ge \frac{\beta_0}{2}. \]

As a result, for the vectors \((21')\) we shall have
\(\|b^{(n)}-\tilde b^{(n)}\| \ge \dfrac{\beta_0}{2n}\) \((\|b^{(n)}\|=1)\), which, in view of (26), is equivalent to (24). Theorem 2 is proved.

Remark 2. Setting \(\Gamma_n=0\) in equality (21), we obtain, on the basis of (22) and \((20')\),

\[ \|u_n^{(m)}-\tilde u_n^{(m)}\| \le \beta_1\|\delta^{(n)}\| \quad (n=n_0,\ n_0+1,\ldots). \]

Thus, the collocation method is stable with respect to small errors in the column of free terms of the system of equations (7), regardless of whether the sequence \(\psi_k(s)=\varphi_k^{(m)}(s)\) \((k=0,1,2,\ldots)\) is strongly minimal in the space \(L_\rho^2\) or not. In other words, the instability of the collocation method in the case of a non-strongly-minimal sequence \(\{\varphi_k^{(m)}(s)\}\) is caused only by errors in the matrix of the system of equations (7). In this respect the collocation method differs, for example, from the Ritz method, in which instability in the case of a non-strongly-minimal coordinate sequence is caused equally by errors both in the matrix of the system of equations and by errors in the column of free terms.

References

1. Karpilovskaya E. B. Uspekhi Mat. Nauk, 8, No. 3 (55), 1953, pp. 111—118.
2. Kantorovich L. V. and Akilov G. P. Functional Analysis in Normed Spaces. Moscow, Fizmatgiz, 1959.
3. Karpilovskaya E. B. Dokl. Akad. Nauk SSSR, 151, No. 4, 1963, pp. 766—769.
4. Natanson I. P. Constructive Function Theory. Moscow—Leningrad, Gostekhizdat, 1949.
5. Mikhlin S. G. Vestnik LGU, No. 13, issue 3, 1961, pp. 40—51.
6. Yaskova G. N. and Yakovlev M. N. Some stability conditions for the Galerkin—Petrov method. Trudy Mat. Inst., 66, 1962, pp. 182—189.
7. Veliev M. A. Dokl. Akad. Nauk SSSR, 157, No. 1, 1964, pp. 16—18.
8. Mikhlin S. G. Dokl. Akad. Nauk SSSR, 157, No. 2, 1964, pp. 271—273.

Received by the editors
October 8, 1964

Tartu State University