UDC 518.1

MATHEMATICS

A. A. SAMARSKII

ON THE THEORY OF DIFFERENCE SCHEMES

(Presented by Academician M. V. Keldysh, 19 IV 1965)

Difference schemes are considered for the abstract Cauchy problem (1) in Banach and Hilbert spaces. Special attention is devoted to sufficient conditions for the well-posedness of schemes.

1. Let \(H\) be a Banach space; let \(A(t)\) be a linear (unbounded) operator depending on \(t\), \(0 \leq t \leq T\), with domain of definition \(D(A)\) dense in \(H\) and range \(\Delta(A) \subset H\). Consider the Cauchy problem

\[ du/dt + A(t)u = f(t),\quad 0 \leq t \leq T,\quad u(0)=u_0,\quad u_0 \in D(A). \tag{1} \]

The unknown function \(u=u(t)\) and the prescribed function \(f(t)\) are defined on the interval \(0 \leq t \leq T\) and take values in \(H\), and the derivative \(du/dt\) is understood in the strong sense. Boundary conditions are taken into account by the requirement \(u(t)\in D(A)\). We shall assume that problem (1) is well posed.

1. Difference schemes for problem (1) with \(f=0\) were studied in \((^1)\). The approximate solution was considered in the same space \(H\) as the solution \(u=u(t)\) of the original problem (1). Sufficient conditions for the well-posedness of the schemes were obtained only for special cases (the Cauchy problem, equations with constant coefficients) by spectral methods. (A treatment of difference schemes for (1) differing from \((^1)\) is given in \((^4)\).) The methods of \((^1,^2)\) are unsuitable for equations with variable and, in particular, discontinuous coefficients.

We study difference schemes defined not in \(H\), but in another space, which is an analogue of the space of grid functions. This approach makes it possible to obtain sufficient conditions for the well-posedness of schemes, using only such general properties of operators (as, for example, semiboundedness from below) which are easily verified directly.

Let \(\{H_N,\, N=1,2,\ldots\}\) be a sequence of Banach spaces with norm \(\|\cdot\|_N\), and let \(P_N\) be a linear operator projecting \(H\) onto \(H_N\) (\(P_Nu=u_N\in H_N\), if \(u\in H\)) and suppose that the closure condition

\[ \lim_{N\to\infty}\|P_Nu\|_N=\|u\| \]

is satisfied for every \(u\in H\), where \(\|\cdot\|\) is the norm in \(H\).

As \(P_N\) one may take the operator of averaging over a neighborhood of a grid node \(\omega_N\) (for \(H=L_2\) and \(H_N=L_2(\omega_N)\)), the operator of taking the value at a grid node (for \(H=C\), \(H_N=C(\omega_N)\)), etc. The choice of \(P_N\) depends on the norms in \(H\) and \(H_N\).

On the interval \(0 \leq t \leq T\) introduce the grid \(\omega_\tau=\{t^j=j\tau;\ j=0,1,\ldots,\ldots,[T/\tau]\}\) with step \(\tau\). Consider two-layer schemes relating the values of the desired function on two time layers \(t=t^j\) and \(t=t^{j+1}\). Any two-layer linear scheme can be represented in the form

\[ R_N y = S_N \check{y}+\tau\varphi(t),\quad 0<t\in\omega_\tau,\quad y(0)=P_Nu_0, \tag{2} \]

where \(R_N=R_N(t,\tau)\), \(S_N=S_N(t,\tau)\) are linear operators depending on \(t,\tau,N\) and acting from \(H_N\) into \(H_N\); \(\varphi=\varphi_{N,\tau}(t)\in H_N\) is a given func-

condition, \(y = y_{N,\tau}(t) \in H_N\) is the unknown function, defined for \(t \in \omega_\tau\); we have denoted

\[ y = y_{N,\tau}(t^{j+1}) = y_{N,\tau}^{j+1}, \qquad \check y = y_{N,\tau}(t^j) = y_{N,\tau}^{j}, \qquad \varphi = \varphi(t) = \varphi_{N,\tau}^{j+1}. \]

In what follows we shall omit the index \(N,\tau\).

Problem (2) is posed correctly (we shall say that “scheme (2) is correct”) (see (3)) if, for sufficiently large \(N \ge N_0\) and sufficiently small \(\tau \le \tau_0\), it is solvable for arbitrary \(\varphi(t) \in H_N,\ t \in \omega_\tau\), and \(y(0) \in H_N\), and its solution depends continuously, uniformly in \(N\) and \(\tau\), on the initial data \(y(0)\) and on the right-hand side \(\varphi(t)\) (“the scheme is stable with respect to the initial data and the right-hand side”):

\[ \max_{\omega_\tau} \|y(t)\|_N \le M_1' \|y(0)\|_N + M_2' \max_{\omega_\tau} \|\varphi(t)\|_N, \]

where \(M_1'\), \(M_2'\) are positive constants independent of \(N\) and \(\tau\).

For correctness of scheme (2) it is sufficient to require that the inverse operator \(R_N^{-1}(t)\) exist for every \(t \in \omega_\tau\), acting from \(H_N\) into \(H_N\), and that the conditions

\[ \|R_N^{-1}(t)S_N(t)\|_N \le 1 + c_1\tau, \qquad \|R_N^{-1}(t)\| \le c_2 \quad \text{for all } t \in \omega_\tau, \tag{3} \]

be satisfied, where \(c_1\) and \(c_2\) are positive constants independent of \(\tau\) and \(N\). In this case, for the solution of problem (2) the estimate

\[ \|y^j\|_N \le e^{c_1 t^j} \left\{\|y(0)\|_N + c_2 \sum_{j'=1}^{j} \tau \|\varphi^{j'}\|_N\right\} \quad \text{for all } t^j \in \omega_\tau \tag{4} \]

is valid.

3. The notions of convergence and approximation are introduced in the natural way. Let \(y^j = y_{N,\tau}^j \in H_N\) be the solution of the difference problem (2), and \(u^j = u(t^j)\) the solution of problem (1). The characteristic of scheme (2) is the error \(z^j = y^j - P_N u^j \in H_N\), defined for \(t^j \in \omega_\tau\).

The solution of problem (2) converges to the solution of problem (1) (“scheme (2) converges”) uniformly in \(t\) as \(\tau \to 0\) and \(N \to \infty\), if

\[ \|y^j - P_N u^j\|_N \le \rho_1(\tau) + \rho_2(1/N) \quad \text{for all } t^j \in \omega_\tau, \tag{5} \]

where \(\rho_1(\tau) \ge 0\), \(\rho_2(1/N) \ge 0\) do not depend on \(t^j\), and \(\rho_k(\xi) \to 0\) as \(\xi \to 0\), \(k = 1,2\).

To each space \(H_N\) we assign a positive number \(h_N\) (the step) such that the sequence \(\{h_N\}\) tends to zero as \(N \to \infty\).

We shall say that scheme (2) has \(n\)-th order of accuracy with respect to \(\tau\) and \(k\)-th order of accuracy with respect to \(h_N\) (“scheme (2) converges with rate \(O(\tau^n) + O(h_N^k)\),” or “scheme (2) has accuracy \(O(\tau^n) + O(h_N^k)\)”), if, for sufficiently small \(\tau \le \tau_0\) and \(h_N \le h_0\),

\[ \|y^j - P_N u^j\|_N \le M_1 \tau^n + M_2 h_N^k \quad \text{for all } t^j \in \omega_\tau. \tag{6} \]

Here and below \(M_s\) \((s = 1,2,\ldots)\) are positive constants independent of \(\tau\) and \(h_N\). Substituting \(y = z + P_N u\) into (2), we obtain:

\[ R_N z = S_N \check z + \tau\psi, \qquad 0 < t \in \omega_\tau, \qquad z(0) = 0. \tag{7} \]

Here

\[ \psi = \psi(u) = \varphi - \frac{1}{\tau}\left(R_N P_N u - S_N P_N \check u\right) \]

is the error of approximation of equation (1) by scheme (3), taken on the solution \(u = u(t)\) of equation (1).

If

\[ \|\psi^j\|_N \le \rho_1'(\tau) + \rho_2(1/N) \quad \text{for } t^j \in \omega_\tau, \]

then it is said that scheme (2) approximates equation (1) in the class of its solutions.

Scheme (2) approximates equation (1) with order \(n\) with respect to \(\tau\) and \(k\)

with respect to \(h_N\) (has approximation error \(O(\tau^n)+O(h_N^k)\)), if

\[ \|\psi^j\|_N \le M_3\tau^n+M_4h_N^k \quad\text{or}\quad \|\psi^j\|_N=O(\tau^n)+O(h_N^k) \quad\text{for } t^j\in\omega_\tau. \]

The following theorem is obvious (cf. \((^{1-3})\)): from the correctness and approximation there follows the convergence of the difference scheme (2); the order of accuracy of scheme (2) is determined by the order of the approximation error in the class of solutions \(u=u(t)\) of equation (1).

1. The greatest difficulties in the theory of difference schemes are connected with finding sufficient conditions for the correctness of schemes. In \((^1,{}^2)\) conditions are given for equations with constant coefficients and for the periodic Cauchy problem.

We shall use the method of energy inequalities for schemes defined in the Hilbert space \(H_N\) with scalar product \((y,v)_N\) and norm \(\|y\|_N=\sqrt{(y,y)_N}\).

Any two-level scheme (2) can be written in the form

\[ C_N y_t + A_N(\sigma y+(1-\sigma)\check y)=\varphi, \qquad y_t=(y-\check y)/\tau, \tag{8} \]

where \(\sigma\) is an arbitrary real parameter; \(A_N=A_N(t,\tau,\sigma)\) and \(C_N=C_N(t,\tau,\sigma)\) are linear operators whose domain of definition and range coincide with \(H_N\) for all \(t\in\omega_\tau\). Most often encountered are the schemes

\[ y_t + A_N(\sigma y+(1-\sigma)\check y)=\varphi, \qquad 0<t\in\omega_\tau,\quad y(0)=P_Nu_0. \tag{9} \]

Comparing (9) with (2), we see that \(R_N=E+\sigma\tau A_N,\; S_N=E-(1-\sigma)\tau A_N\), where \(E\) is the identity operator.

The following theorems hold:

Theorem 1. Scheme (9) is correct if \(\sigma\ge 0.5\) and \(A_N\) is positive, i.e. \((A_Ny,y)_N\ge 0\) for all \(y\in H_N\); in this case estimate (4) is valid with \(c_1=0,\; c_2=1\).

Theorem 2. Scheme (9) is correct if \(\sigma\ge 0.5\), \(A_N\) is semibounded, i.e. \((A_Ny,y)_N\ge -M_5\|y\|_N^2\), and \(\tau\le\tau_0(M_5)\) is sufficiently small.

Theorem 3. Scheme (9) is correct if \(A_N\) is a finite-dimensional positive self-adjoint \(\bigl((A_Ny,v)_N=(y,A_Nv)_N\) for any \(y,v\in H_N\bigr)\) operator and
\[ \sigma\ge\sigma_\varepsilon=0.5-(1-\varepsilon)/\tau\|A_N(t)\|_N, \]
where \(\varepsilon\in(0,1]\) is any number; estimate (4) is valid with \(c_1=0,\; c_2=1/\varepsilon\).

Theorem 4. Scheme (9) is stable with respect to the initial data in the norm
\[ \|y\|_{A_N}=\sqrt{(A_N(t)y,y)_N}, \]
if \(A_N\) is a self-adjoint positive \(\bigl((A_Ny,y)_N>0\bigr)\) operator satisfying the Lipschitz condition in \(t\), i.e.
\[ \left|(A_N(t)y,y)_N\right|\le M_0(\check A_Ny,y)_N, \]
and \(\sigma\ge\sigma_\varepsilon\).

A priori estimates for the solution of (9) in terms of \((A^{-1}\varphi,\varphi)_N\) have also been obtained.

For the general scheme (8) we indicate only one result. Scheme (8) is correct if: a) \(\sigma\ge 0.5\); b) \(A_N\) is a self-adjoint, positive \(\bigl((A_Ny,y)_N>0\bigr)\) operator satisfying the Lipschitz condition in \(t\); c)
\[ (C_Ny,y)_N\ge 0,\qquad (C_Ny_t,y_t)_N\ge \varepsilon\|y_t\|^2-M_7\bigl(\|y\|_{A_N}^2+\|\check y\|_{\check A_N}^2\bigr), \]
where \(\varepsilon\in(0,1]\) is any number. For the solution of equation (8), for sufficiently small \(\tau\le\tau_0(M_7)\), the estimate

\[ \|y^j\|_{A_N^j} \le M_8\left(\|y(0)\|_{A_N(0)}+\frac{1}{\varepsilon} \sum_{j'=1}^{j}\tau\|\varphi^{j'}\|_N\right) \quad\text{for all } t^j\in\omega_\tau. \tag{10} \]

follows.

From this, in particular, follows the stability of splitting schemes for equations of parabolic type (see \((^5)\)).

1. It is known that in a number of cases (nonuniform grids, discontinuous coefficients \((^4)\)) the solution of a difference equation and its right-hand side should be estimated in different spaces. Estimates of this kind can be obtained for operators \(A_N\) of a special form.

Let \(H_N\) and \(H_{N,1}\) be Euclidean spaces with scalar products \((y,z)_N\) and \((v,w]_{N}\), respectively; \(T_N\) a linear operator from \(H_N\) into \(H_{N,1}\); \(T_N^*\) a linear operator from \(H_{N,1}\) into \(H_N\), adjoint to \(T_N\) in the following sense: \((T_N y, v]_{N} = (y, T_N^* v)_N\) for any \(y \in H_N,\ v \in H_{N,1}\).

The operators \(T_N\) and \(T_N^*\) have uniformly bounded inverse operators \(T_N^{-1}\) and \(T_N^{*-1}\). Consider operators \(A_N\) of “conservative” (“divergence”) form
\[ A_N = T_N^* S_N T_N, \]
where \(S_N = S_N(t,\tau)\) is a linear operator acting from \(H_{N,1}\) into \(H_{N,1}\). If \(S_N\) is a positive definite operator, i.e. \((S_N v, v]_{N} \geq M_9 \|v\|_{N}^{2}\), \(\|v\|_{N}^{2}=(v,v]_{N}\), then for \(\sigma \geq 0.5\) an estimate of the form (4) is valid, where \(\|\varphi\|_{N}\) should be replaced by the norm \(\|(T_N^*)^{-1}\varphi\|_{N}\), and also an a priori estimate for \(\|T_N y\|_{N}\).

From these estimates, in particular, follow the main results of the works \({}^{(4)}\) on the theory of difference schemes for parabolic equations in the case of nonuniform grids and discontinuous coefficients (as well as a number of new results). The “multidimensional” case is studied similarly:
\[ A_N=\sum_{\alpha=1}^{m} T_{N,\alpha}^{*} S_{N,\alpha} T_{N,\alpha}. \]

6. Conditions of well-posedness have been obtained for three-level schemes for equation (1).

Three-level and four-level schemes have been investigated for the second-order equation
\[ d^{2}u/dt^{2}+A(t)u=f(t),\qquad 0<t\leq T,\qquad u(0)=u_0,\qquad du/dt(0)=\bar u_0. \]

Thus, for example, for the well-posedness of the three-level scheme
\[ y_{\bar t t}+0.5 A_N(y+\check y)+(\sigma-0.5)\tau^{2}A_N y_{\bar t t}=\varphi, \]
\[ (\check y=y^{j-1},\quad \bar y=y^{j},\quad y=y^{j+1},\quad y_{\bar t t}=(y-2\bar y+\check y)/\tau^{2}) \]
it is sufficient that: 1) \(\sigma \geq 0.25-(1-\varepsilon)/\tau^{2}\|A_N\|_{N}\), \(\varepsilon \in [0,1]\) is arbitrary; 2) \((A_Ny,y)_N>0\); 3) \(A_N\) is a self-adjoint operator satisfying the Lipschitz condition with respect to \(t\).

The author expresses gratitude to A. N. Tikhonov for useful discussion of the results.

Received
30 III 1965

References

1. P. D. Lax, R. D. Richtmyer, Comm. Pure and Appl. Math., 9, 267 (1956).
2. R. D. Richtmyer, Difference Methods for Solving Boundary-Value Problems, Moscow, 1960.
3. V. S. Ryabenkii, A. F. Filippov, On the Stability of Difference Equations, Moscow, 1956.
4. L. I. Yakut, Proceedings of the Seminar on Functional Analysis, Voronezh, issue 7, 1963, p. 160.
5. A. A. Samarskii, Zhurn. vychislit. matem. i matem. fiz., No. 6, 972 (1961); No. 4, 603 (1962); No. 2, 266 (1963).
6. E. G. D’yanonov, Zhurn. vychislit. matem. i matem. fiz., No. 2, 278 (1964); No. 5, 935 (1964).