Abstract Generated abstract
This paper studies the stability of grid, or net, methods for elliptic boundary value problems under small perturbations of the discrete operator, rather than only perturbations of the right-hand side. Using a variational construction of the discrete Dirichlet problem, Friedrichs extension, and Kantorovich’s theory of approximate methods, it formulates stability in norms associated with the discrete energy space and proves a uniform stability theorem for a non-self-adjoint elliptic problem. The paper also identifies subspaces of mesh matrices corresponding to first-order and second-order operator perturbations, gives equivalent scaled matrix norms for them, and derives corresponding error estimates for the perturbed solutions. The results are stated to extend, with natural modifications, to Neumann problems and strongly elliptic second-order systems.
Full Text
Yu. K. Dem’yanovich
STABILITY OF THE METHOD OF NETS FOR ELLIPTIC PROBLEMS
(Presented by Academician V. I. Smirnov on 12 II 1965)
The stability of the method of nets has been studied \((^1)\) only with respect to small changes in the right-hand side of the equation, although the stability of other approximate methods, for example the Ritz method, has been investigated \((^{2-4})\) also with respect to small additions to the operator. Examples of unstable schemes are given in \((^{10})\).
The purpose of the present work is to investigate the stability of the method of nets for elliptic problems with respect to small changes in the net operator. From the stability considered here there follows stability in the sense of S. G. Mikhlin \((^{2,4})\), studied by him in the Ritz method, as well as stability with respect to changes of the net operator in certain subspaces of the linear space of matrices. The possibility of considering stability with respect to a change of the net operator in a certain subspace was brought to my attention by Prof. S. G. Mikhlin, to whom I express my sincere gratitude.
We shall use throughout the notation of note \((^5)\).
\(1^\circ.\) Let the finite \(n\)-dimensional domain \(\Omega\) satisfy the following condition:
\((*)\) there exist \(\widetilde N\) unit vectors \(m_1,\ldots,m_{\widetilde N}\), belonging to \(n\)-dimensional Euclidean space, and also positive numbers \(k\) and \(h_0\), such that for \(h<h_0\) the boundary strip \((^6)\) of width \(h\) lies in the union
\[ \bigcup_{i=1}^{\widetilde N}\left(\Omega\setminus \Omega_{k h m_i}\right), \]
where by \(\Omega_t,\ t=(t_1,\ldots,t_n)\), is denoted the result of translating the domain \(\Omega\) by the vector \(t\).
Remark. Condition \((*)\) is fulfilled if the boundary of the domain \(\Omega\) is twice continuously differentiable, and also in the case of a domain of particular form \(|\Omega_h|=\Omega\).
By \(|\Omega_h'|\) we shall denote the greatest union of cubes of the net contained in the domain \(\Omega\), and by \(\Omega_h'\) the set of nodes \(x_0\) of the net lying in the interior of \(|\Omega_h'|\).
Let \(\overline X\) be the set of all net functions \(v(x_0)\) equal to zero outside \(\Omega_h'\), and let \(\psi\) be the operation of polylinear \((^7)\) extension of the net function \(v\): \(\widetilde u=\psi v\).
We construct the net system for the Dirichlet problem, formulated in \((^5)\), from the problem of minimizing the functional \(F(u)\) on the space \(\widetilde X\) of functions of the form \(\widetilde u=\psi v,\ v\in \overline X\):
\[ \overline A_0 v=\overline f,\qquad v\in \overline X, \tag{1} \]
where
\[ \overline A_0=\sum_{\alpha,\beta\in A}(-1)^{|\alpha|}\overline D_h^{\alpha} A_{\alpha}^{\beta} D_h^{\beta}, \tag{2} \]
\[ \overline f=\sum_{\alpha\in A}(-1)^{|\alpha|}\overline D_h^{\alpha} f^{\alpha},\qquad \alpha\setminus e_i= \begin{cases} \alpha, & \text{if } \alpha_i=0,\\ \alpha-e_i, & \text{if } \alpha_i=1. \end{cases} \]
\[ A_\alpha^\beta(x_0)=\frac{1}{h^n}\int_{\Pi_{x_0}} \left(\sum_{i,j=1}^n a_{ij} w_{\alpha<e_i} w_{\beta>e_j}+a w_\alpha w_\beta\right)dx, \]
\[ f^\alpha(x_0)=\frac{1}{h^n}\int_{\Pi_{x_0}} w_\alpha f\,dx,\qquad \Pi_{x_0}\subset |\Omega'_h|; \]
\[ A_\alpha^\beta(x_0)=f^\alpha(x_0)=0,\qquad \text{if } \Pi_{x_0}\not\subset |\Omega'_h|. \]
With this method of construction, there is unique solvability of system (1) and the convergence-rate estimates indicated in note (5).
Consider the non-self-adjoint problem:
\[ A_0u+\lambda Tu=f,\qquad u\in \dot W_2^1(\Omega), \tag{3} \]
where
\[ A_0u\equiv -\sum_{i,k=1}^n \frac{\partial}{\partial x_i} \left(a_{ik}\frac{\partial u}{\partial x_k}\right)+au, \]
\[ Tu\equiv \sum_{i=1}^n a_i\frac{\partial u}{\partial x_i}+a_{n+1}u, \qquad f\in L_2(\Omega), \]
\(a_i\) are measurable and bounded functions in the domain \(\Omega\), while the assumptions of note (5) are retained with respect to the coefficients \(a_{ik}\) and \(a\). We shall also assume that the operator \(A_0\) is extended to a self-adjoint one in the sense of Friedrichs.
In what follows we shall use L. V. Kantorovich’s general theory of approximate methods (8). As the basic space \(X\) we take the space \(H_{A_0}\) (9) and consider the approximate equation
\[ \tilde u+\lambda P A_0^{-1}T\tilde u=P A_0^{-1}f,\qquad \tilde u\in \tilde X, \tag{4} \]
where \(P\) is the operator of orthogonal projection in \(H_{A_0}\) onto the subspace \(\tilde X\). From the results of note (5) follows the fulfillment of the sufficient conditions I–III for applicability of the above-mentioned theory ((8), p. 488).
Equation (4) can be written in the form
\[ \bar A_0 v+\lambda \bar T v=\bar f,\qquad v\in \bar X, \tag{5} \]
where
\[ \bar T=\sum_{\alpha,\beta\in A}(-1)^{|\alpha|}\bar D_h^\alpha a_\beta^\alpha D_h^\beta, \tag{6} \]
\[ a_\beta^\alpha(x_0)=\frac{1}{h^n}\int_{\Pi_{x_0}} \left(\sum_{i=1}^n w_{\beta>e_i} a_i+w_\beta a_{n+1}\right)w_\alpha\,dx. \]
For brevity, henceforth we shall assume that \(a\equiv a_{n+1}\equiv 0\).
\(2^\circ\). In the linear space \(\bar X\) we introduce the scalar product in two ways:
\[ (v,v')_0=h^n\sum_{x_0} v(x_0)v'(x_0), \tag{7} \]
\[ (v,v')_1=h^n\sum_{x_0} \left\{v(x_0)v'(x_0)+\sum_{i=1}^n D_h^{e_i}v(x_0)\cdot D_h^{e_i}v'(x_0)\right\}; \tag{7'} \]
here the summation is extended over all nodes of the grid. The corresponding norms will be denoted by the symbols \(\|\cdot\|_0\) and \(\|\cdot\|_1\). The normalized spaces obtained in this way will be denoted by \(\bar X_0\) and \(\bar X_1\), respectively.
We shall not associate the norm of the linear operation \(\bar A\), acting in \(\bar X\), in the usual way with the norms of the spaces \(\bar X_0\) and \(\bar X_1\), but by definition set
\[ \|\bar A\|=\sup_{v,v'\in \bar X}\frac{|(\bar A v,v')_0|}{\|v\|_1\|v'\|}. \]
The space of all linear operations in \(\bar X\), normed in this way, will be denoted by \(\mathfrak A\).
Alongside system (5), consider the system
\[ (\bar A_0+\lambda \bar T+\bar \Gamma)v=\bar f+\bar\delta,\qquad v\in \bar X, \tag{5′} \]
where \(\bar \Gamma\in \mathfrak A,\ \bar\delta\in \bar X\).
Suppose that for \(h<h_0\) there exists a unique solution \(v_*\) of system (5). We shall say that the grid method (5) is stable if there exist positive constants \(\varepsilon, C_1\), and \(C_2\), independent of \(h\), such that from the relations \(\bar\Gamma\in\mathfrak A,\ \|\bar\Gamma\|<\varepsilon,\ h<h_0\) there follows the existence of a unique solution \(v_*'\) of system (5′) and the estimate
\[ \|v_*'-v_*\|_1\leq C_1\|\bar\Gamma\|+C_2\|\bar\delta\|_0. \tag{8} \]
Remark. In view of the obvious inequalities
\[ \|\bar\Gamma\|\leq \|\bar\Gamma\|_{[\bar X_1\to \bar X_0]}\leq \|\bar\Gamma\|_{[\bar X_0\to \bar X_0]}, \]
relation (8) implies stability in the sense of S. G. Mikhlin \((^{2,4})\).
Theorem 1. Under the assumptions formulated above concerning the domain \(\Omega\) and problem (3), the grid method (5) is stable.
We shall represent linear transformations in \(\bar X\) in the form of matrices written in the basis \(\{v_{y_0}\}_{y_0\in\Omega_h'}\) of the space \(\bar X\), where
\[ v_{y_0}(x_0)= \begin{cases} 0, & \text{if } x_0\ne y_0,\\ 1, & \text{if } x_0=y_0. \end{cases} \]
In what follows we shall use the following notation:
\[ \alpha\cap\beta=(\alpha_1\beta_1,\ldots,\alpha_n\beta_n),\qquad \alpha\cup\beta=\alpha+\beta-\alpha\cap\beta. \]
A basis of the linear span \(\mathfrak B_1\) of all matrices of the form (6) is the collection of matrices \(\mathcal E_{z_0}^{\,i}\), \(i=1,\ldots,n,\ z_0\in\Omega_h'\), with elements \(a_{x_0,y_0}^{z_0,i}\), computed by the formula
\[ a_{x_0,y_0}^{z_0,i}= \begin{cases} \dfrac{(-1)^{1-\beta_i}}{h\cdot 3^{\,n-1}}\cdot 2^{|\alpha\cap\beta\cup e_i|-|\alpha\cup\beta\cup e_i|-1}, & \text{if } \alpha=\dfrac{x_0-z_0}{h}\in A,\ \beta=\dfrac{y_0-z_0}{h}\in A,\\[1.2em] 0 & \text{in the remaining cases.} \end{cases} \]
Introduce in \(\mathfrak B_1\) the norm as follows:
\[ \|\bar\Gamma\|^*=h\max_{x_0,y_0\in\Omega_h'}|\gamma_{x_0,y_0}|,\qquad \bar\Gamma=(\gamma_{x_0,y_0})\in\mathfrak B_1. \]
Theorem 2. Under the assumptions of Theorem 1, if \(h<h_0,\ \bar\Gamma\in\mathfrak B_1,\ \|\bar\Gamma\|^*<\varepsilon^*\), the inequality holds:
\[ \|v_*'-v_*\|_1\leq C_1^*\|\bar\Gamma\|^*+C_2^*\|\bar\delta\|_0. \]
A basis of the linear space \(\overline{\mathfrak{B}}_2\) of mesh matrices (2) is the collection of matrices \(\mathcal{E}_{z_0}^{\,i,j}\) \((i,j=1,\ldots,n;\ \Pi_{z_0}\subset |\Omega_h'|)\) with elements \(a_{x_0,y_0}^{\,i,j,z_0}\), \(x_0,y_0\in \Omega_h'\), computed by the formula
\[ a_{x_0,y_0}^{\,i,j,z_0} = \begin{cases} \left(\dfrac{3}{4}\right)^{\varepsilon_{ij}} \dfrac{(-1)^{\alpha_i+\beta_j}}{3^{n-1}h^2} \cdot 2^{|\alpha\cap\beta\cup e_i\cup e_j|-|\alpha\cup\beta\cup e_i\cup e_j|}, \\[6pt] \qquad\text{if }\alpha=\dfrac{x_0-z_0}{h}\in A,\quad \beta=\dfrac{y_0-z_0}{h}\in A,\\[6pt] 0\quad \text{in all other cases}, \end{cases} \]
where
\[ \varepsilon_{ij} = \begin{cases} 0 & \text{for } i=j,\\ 1 & \text{for } i\ne j. \end{cases} \]
The norm induced by the space \(\mathfrak{A}\) in \(\overline{\mathfrak{B}}_2\) is equivalent to the norm
\[ \|\overline{\Gamma}\|^{**} = h^2\max_{x_0,y_0\in\Omega_h'}|\gamma_{x_0,y_0}|, \qquad \overline{\Gamma}\in\overline{\mathfrak{B}}_2, \]
in the sense that, with positive constants \(C'\) and \(C''\) independent of \(h\), the inequality
\[ C'\|\overline{\Gamma}\|\le \|\overline{\Gamma}\|^{**}\le C''\|\overline{\Gamma}\|, \qquad \overline{\Gamma}\in\overline{\mathfrak{B}}_2. \]
holds.
Theorem 3. Under the conditions of Theorem 1, for \(h<h_0\), \(\overline{\Gamma}\in\overline{\mathfrak{B}}_2\), \(\|\overline{\Gamma}\|^{**}<\varepsilon^{**}\), the following estimate is valid:
\[ \|v_*'-v_*\|_1 \le C_1^{**}\|\overline{\Gamma}\|^{**} + C_2^{**}\|\overline{\delta}\|_0. \]
3°. The results formulated above, with obvious changes, carry over to the case of the Neumann problem, and also to a strongly elliptic system of second-order differential equations.
Leningrad State University
named after A. A. Zhdanov
Received
8 II 1965
CITED LITERATURE
- S. K. Godunov, V. S. Ryabenkii, Introduction to the Theory of Difference Schemes, Moscow, 1962.
- S. G. Mikhlin, DAN, 135, No. 1 (1960).
- N. Y. Yaskova, M. N. Yakovlev, Tr. Matem. inst. im. V. A. Steklova AN SSSR, 66, 182 (1962).
- S. G. Mikhlin, DAN, 157, No. 2 (1964).
- Yu. K. Demyanovich, DAN, 159, No. 2 (1964).
- S. L. Sobolev, Some Applications of Functional Analysis in Mathematical Physics, Leningrad, 1950.
- O. A. Ladyzhenskaya, The Mixed Problem for a Hyperbolic Equation, 1953.
- L. V. Kantorovich, G. P. Akilov, Functional Analysis in Normed Spaces, 1959.
- S. G. Mikhlin, The Problem of the Minimum of a Quadratic Functional, 1952.
- A. N. Tikhonov, A. A. Samarskii, DAN, 149, No. 3 (1963).