Abstract Generated abstract
This paper studies stability of sequences of linear computational problems in Banach spaces under perturbations of both the operator and the right hand side. It gives necessary and sufficient conditions for stability in terms of uniform boundedness of the inverse operators and of the quantities obtained by applying perturbed inverse compositions to the exact solutions, with a sharper characterization for Hilbert spaces under an additional lower bound assumption. The results are applied to Ritz and Bubnov Galerkin processes, showing that stability of coefficient computation and approximate solutions is governed by strong minimality of the coordinate system, equivalently by a uniform positive lower bound for the smallest eigenvalues of the associated Gram matrices.
Full Text
S. G. Mikhlin
On the Stability of Certain Computational Processes
(Presented by Academician V. I. Smirnov on 15 II 1964)
Let \(X_n\) and \(Y_n\), \(n=1,2,\ldots\), be Banach spaces and let \(A_n\) be linear operators acting from \(X_n\) into \(Y_n\), where for every \(n\) the operator \(A_n^{-1}\) exists and is defined on the entire space \(Y_n\). Consider the computational process consisting in solving the sequence of equations
\[ A_n x^{(n)} = y^{(n)} . \tag{1} \]
Alongside equations (1), consider the sequence of equations
\[ (A_n+\Gamma_n) z^{(n)} = y^{(n)}+\delta^{(n)}, \tag{2} \]
where the operators \(\Gamma_n\) are also linear.
We shall say that the computational process (1) is stable (with respect to changes in the operator \(A_n\) and the free term \(y^{(n)}\)) if there exist constants \(p,q,r\), independent of \(n\), such that for \(\|\Gamma_n\|\le r\) and for arbitrary \(\delta^{(n)}\), equations (2) are solvable and the inequality holds
\(\eta^{(n)}=z^{(n)}-x^{(n)}\)
\[ \|\eta^{(n)}\|\le p\|\Gamma_n\|+q\|\delta^{(n)}\|. \tag{3} \]
Theorem 1. For the stability of the computational process (1), it is necessary and sufficient that, independently of \(n\), the norms of the operators \(A_n^{-1}\) and the elements \(A_n^{-1}B_nA_n^{-1}y^{(n)}=A_n^{-1}B_nx^{(n)}\) be bounded, where \(B_n\) is an arbitrary operator of unit norm acting from \(X_n\) into \(Y_n\).
Necessity. 1) Let \(\Gamma_n=0\). Then \(A_n\eta^{(n)}=\delta^{(n)}\) and
\(\|\eta^{(n)}\|\le q\|\delta^{(n)}\|\). Hence \(\|A_n^{-1}\|\le q\).
2) Let now \(\delta^{(n)}=0\) and \(\Gamma_n=\varepsilon B_n\), where \(\|B_n\|=1\) and \(\varepsilon\) is a constant, \(0<\varepsilon<r\). In this case \(\eta^{(n)}\) satisfies the equation
\[ \eta^{(n)}+\varepsilon A_n^{-1}B_n\eta^{(n)} = -\,\varepsilon A_n^{-1}B_nx^{(n)} . \]
Hence
\[ \|\eta^{(n)}\|\ge \frac{\varepsilon\|A_n^{-1}B_nx^{(n)}\|}{1+\varepsilon q}. \]
Comparing this with inequality (3), which in the present case has the form
\(\|\eta^{(n)}\|\le p\varepsilon\), we find that
\(\|A_n^{-1}B_nx^{(n)}\|\le p(1+\varepsilon q)\). Since \(\varepsilon\) is arbitrarily small, \(\|A_n^{-1}B_nx^{(n)}\|\le p\).
Sufficiency. Let \(\|A_n^{-1}\|\le C_1\), \(\|A_n^{-1}B_nx^{(n)}\|\le C_2\), where the constants \(C_1\) and \(C_2\) do not depend on \(n\). Put \(r=\beta C_1^{-1}\), where \(\beta\) is a constant, \(0<\beta<1\), and require that \(\|\Gamma_n\|\le r\). Form the equations
\[ (A_n+\Gamma_n) z_1^{(n)} = y^{(n)}, \qquad (A_n+\Gamma_n) z_2^{(n)} = \delta^{(n)}; \]
then \(\eta^{(n)}=(z_1^{(n)}-x^{(n)})+z_2^{(n)}\). It is easy to see that
\[ \|z_2^{(n)}\|\le \|(I_n+A_n^{-1}\Gamma_n)^{-1}\|\,\|\delta^{(n)}\|C_1 \le \frac{C_1}{1-\beta}\,\|\delta^{(n)}\|; \]
here \(I_n\) is the identity operator.
Further, putting \(\Gamma_n=\|\Gamma_n\|B_n,\ \|B_n\|=1\), we have
\[ z_1^{(n)}-x^{(n)}=-\|\Gamma_n\|(I_n+A_n^{-1}\Gamma_n)^{-1}A_n^{-1}B_nx^{(n)} \]
and, consequently,
\[ \|z_1^{(n)}-x^{(n)}\|\leq \frac{\|\Gamma_n\|}{1-\beta}\|A_n^{-1}B_nx^{(n)}\| \frac{C_2}{1-\beta}\|\Gamma_n\|; \]
inequality (3) is thus satisfied for the following values of the constants
\[ p=\frac{C_2}{1-\beta},\qquad q=\frac{C_1}{1-\beta},\qquad r=\frac{\beta}{C_1}. \]
If the quantity \(\|x^{(n)}\|=\|A_n^{-1}y^{(n)}\|\) is bounded, then for the stability of the computational process (1) it is necessary and sufficient that the norms \(\|A_n^{-1}\|\) be bounded. The quantity \(\|x^{(n)}\|\) will be bounded if, for example, \(X_n\), \(n=1,2,\ldots\), are subspaces of some Banach space \(X\), and in this space \(\lim x^{(n)}\) exists.
Theorem 2. If the spaces \(X_n\) are Hilbert spaces and the norms \(\|A_n^{-1}\|\) are bounded below by a positive constant independently of \(n\), then for the stability of process (1) it is necessary and sufficient that the quantities \(\|A_n^{-1}\|\) and \(\|x^{(n)}\|=\|A_n^{-1}y^{(n)}\|\) be bounded above independently of \(n\).
Theorem 2 will be proved if we establish that from the conditions
\[ \|A_n^{-1}B_nx^{(n)}\|\leq C_2,\qquad \|A_n^{-1}\|\geq C_3, \]
where \(C_2,C_3\) are positive constants, there follows the boundedness of the norms \(\|x^{(n)}\|\). Suppose the contrary, and let \(\|x^{(n_k)}\|\to\infty\). Choose an element \(t^{(n_k)}\in Y_{n_k}\) so that \(\|t^{(n_k)}\|=1\) and \(\|A_{n_k}^{-1}t^{(n_k)}\|\geq \frac12\|A_{n_k}^{-1}\|\). Construct an operator \(B_{n_k}\), \(\|B_{n_k}\|=1\), which, on elements of the form \(\lambda x^{(n_k)}\), acts according to the formula
\[ B_{n_k}\bigl(\lambda x^{(n_k)}\bigr)=\lambda\|x^{(n_k)}\|t^{(n_k)}, \]
and which annihilates the elements orthogonal to \(x^{(n_k)}\). Then
\[ \|A_{n_k}^{-1}B_{n_k}x^{(n_k)}\|\geq \frac12\|A_{n_k}^{-1}\|\,\|x^{(n_k)}\|\to\infty, \]
contrary to the condition.
Let us give several examples.*
Example 1. Let \(A\) be a positive definite operator acting in a Hilbert space \(H\), and suppose the problem of minimizing the functional
\[ F(u)=\|u\|_A^2-(u,f)-(f,u) \tag{4} \]
is solved by the Ritz process. Let \(\varphi_k,\ k=1,2,\ldots\), be coordinate elements subject to the usual conditions ([1]), and
\[ u_n=\sum_{k=1}^{n}a_k^{(n)}\varphi_k, \tag{5} \]
the Ritz approximate solution of the above variational problem. The vector \(x^{(n)}=(a_1^{(n)},a_2^{(n)},\ldots,a_n^{(n)})'\) is determined from the equation
\[ R_nx^{(n)}=y^{(n)}, \tag{6} \]
where \(R_n\) is the matrix \(\|[\varphi_k,\varphi_j]_A\|_{j,k=1}^{j,k=n}\); \(y^{(n)}=(f_1,f_2,\ldots,f_n)'\); \(f_k=(f,\varphi_k)\).
* On the terminology and notation, see [1].
Equation (6) falls under type (1) if one sets \(X_n = Y_n, E_n\), where \(E_n\) is an \(n\)-dimensional unitary space, and \(A_n = R_n\). It is not difficult to prove that \(\|R_n^{-1}\| \geq |\varphi_1|_A^2\), and then it follows from Theorem 2 that the process of computing the Ritz coefficients from equations (6) is stable if and only if the coordinate system is strongly minimal \({}^{(2)}\) in the space \(H_A\), i.e., if \(\lambda_1^{(n)} \geq \lambda_0 = \mathrm{const} > 0\), where \(\lambda_1^{(n)}\) is the smallest eigenvalue of the matrix \(R_n\); the sufficiency of this condition was proved in \({}^{(3)}\).
Example 2. Let \(Y_n = E_n\), and let \(X_n\) be the subspace of the space \(H_A\) that is the linear span of the elements \(\varphi_1, \varphi_2, \ldots, \varphi_n\). The approximate solution \(u_n\) of the variational problem (4) is determined from the equation
\[ (S_n^*)^{-1}u_n = y^{(n)}, \tag{7} \]
where \(S_n\) is the operator which assigns to the element \(u_n\) (formula (5)) the vector \(x^{(n)}\). Since \(u_n\) tends in the metric of \(H_A\) to the limit \((1)\), the norms \(|u_n|_A\) are bounded in the aggregate, and for the stability of the process (7) it is necessary and sufficient that the quantities \(\|S_n\|\) be bounded in the aggregate. The relation \((S_n^*)^{-1}S_n^{-1} = R_n\) holds; hence \(\|S_n\| = [\lambda_1^{(n)}]^{-1/2}\), and the necessary and sufficient condition for stability of the process (7) reduces to the strong minimality of the coordinate system in the space \(H_A\). By definition, the inequality characterizing the stability of the named process has the form
\[ |\eta_n|_A \leq p\|\Gamma_n\| + q\|\delta^{(n)}\|, \]
where \(\Gamma_n\) and \(\delta^{(n)}\) may be regarded as the errors of the operator \((S_n^*)^{-1}\) and of the vector \(y^{(n)}\), respectively.
Suppose that these errors arise only as a result of inexact computation of the scalar products \((f,\varphi_k)\) and the energy products \([\varphi_k,\varphi_j]_A\). Then the operator \(S_n^{-1}\) is free of error, as is seen from the formula
\[ S_n^{-1}x^{(n)} = u_n = \sum_{k=1}^{n} a_k^{(n)}\varphi_k. \]
Denoting by \(\overline{\Gamma}_n\) the error of the matrix \(R_n\), we have \(\Gamma_n = \overline{\Gamma}_n S_n\). Hence \(\|\Gamma_n\| \leq \|\overline{\Gamma}_n\|[\lambda_1^{(n)}]^{-1/2}\). If the coordinate system is strongly minimal in \(H_A\), then, putting \(p\lambda_0^{-1/2}=p_1,\ q=q_1\), we obtain the inequality established in \({}^{(4)}\)
\[ |\eta_n|_A \leq p_1\|\overline{\Gamma}_n\| + q_1\|\delta^{(n)}\|. \]
- Let the operator \(A\) be defined as above, and let the operator \(K\) be such that the product \(A^{-1}K\) can be extended to an operator that is completely continuous in the space \(H_A\). From Theorem 1 follow the theorems of the article \({}^{(4)}\), by virtue of which the processes of determining the vector of coefficients and the approximate solution in the Bubnov–Galerkin method for the equation
\[ (A+K)u=f \]
are stable if the coordinate system is strongly minimal in the space \(H_A\).
Received
13 II 1964
REFERENCES CITED
\({}^{1}\) S. G. Mikhlin, Variational Methods in Mathematical Physics, Moscow, 1957.
\({}^{2}\) S. G. Mikhlin, DAN, 135, No. 1 (1960).
\({}^{3}\) A. T. Taldykin, Matem. sbornik, 29 (71), 1 (1951).
\({}^{4}\) G. N. Yakovleva, M. N. Yakovlev, Tr. Matem. inst. im. V. A. Steklova AN SSSR, 66, 182 (1962).