Abstract Generated abstract
The paper studies finite difference approximations for first order symmetric systems of partial differential equations with Friedrichs-type boundary conditions. It formulates the continuous boundary-value problem, derives an a priori energy estimate under positivity assumptions on the coefficients and boundary operators, and then constructs two basic difference schemes based on staggered unknowns and auxiliary boundary relations. Stability estimates analogous to the continuous estimate are proved for both schemes, yielding convergence in the class of generalized solutions, with first order accuracy for the first scheme and second order accuracy for the second under sufficient smoothness.
Full Text
UDC 518:517.944/947
MATHEMATICS
S. M. SHUGRIN
DIFFERENCE SCHEMES FOR SYMMETRIC DIFFERENTIAL EQUATIONS
(Presented by Academician S. L. Sobolev, 15 III 1967)
1. We consider equations of the form
\[ \partial(Au)/\partial x+\partial(Bu)/\partial y+Cu=f \quad (a\leq x\leq b,\ c\leq y\leq d), \tag{1} \]
where \(u, f\in R^n\), a real Euclidean space; \(A=A(x,y)\), \(B=B(x,y)\), \(C=C(x,y)\) are matrices; \(A,B\) are symmetric.
We describe the formulation of the boundary conditions. Let \(x=a\), with \(y\) fixed. Represent \(A\) in the form \(A=A^+-A^-\); \(A^+, A^-\) are symmetric; \(A^+\geq 0\), \(A^-\geq 0\); \(A^+A^-=A^-A^+=0\) \((^1)\). The space \(R\) can be represented in the form \(R=R^+\oplus R^-\oplus R^0\), where \(R^+=A^+R\), \(R^-=A^-R\). Correspondingly, \(u\) can be written in the form \(u=u^+ + u^- + u^0\), \(u^+\in R^+\), \(u^-\in R^-\), \(u^0\in R^0\).
We shall consider boundary conditions of the form
\[ u^+=\theta_a u^-+\varphi_a, \tag{2} \]
where \(\theta_a=\theta_a(y)\) is a matrix from \(R^-\to R^+\), \(\varphi_a=\varphi_a(y)\in R^+\). For \(x=b\) the boundary conditions have the form
\[ u^-=\theta_b u^+ + \varphi_b. \tag{3} \]
Here the decomposition of the space \(R\) is constructed with the aid of the matrix \(A(b,y)\). Boundary conditions for \(y=c,d\) are posed analogously. For the decomposition of the space \(R\), the matrix \(B\) is then used.
The boundary conditions described apparently coincide, up to terminology, with the boundary conditions adopted by Friedrichs \((^2)\).
For the problem posed it is easy to obtain an a priori estimate. To simplify the exposition we shall assume that the boundary conditions are homogeneous \((\varphi=0)\). We shall also assume that the inequalities
\[ \partial A/\partial x+\partial B/\partial y+(C+C')\geq 2\alpha E \quad (\alpha=\mathrm{const},\ \alpha>0); \tag{4} \]
\[ [A^+-\theta'A^-\theta]_{x=b}\geq 0,\qquad [A^- - \theta'A^+\theta]_{x=a}\geq 0, \]
\[ [B^+-\theta'B^-\theta]_{y=d}\geq 0,\qquad [B^- - \theta'B^+\theta]_{y=c}\geq 0. \tag{5} \]
hold. The prime denotes transposition, \(E\) is the identity matrix.
Multiply (1) scalarly by \(u\) and use the equality
\[ (u,\partial(Au)/\partial x) = \tfrac12 \partial(u,Au)/\partial x + \tfrac12 (u,\partial A/\partial x\, u) \tag{6} \]
and the analogous equality for \(B\). From (4)—(6) it follows easily that
\[ \iint_{\substack{a\leq x\leq b\\ c\leq y\leq d}} (u,u)\,dx\,dy \leq \frac{1}{\alpha^2} \iint_{\substack{a\leq x\leq b\\ c\leq y\leq d}} (f,f)\,dx\,dy. \tag{7} \]
2. Below two basic difference schemes will be described. The starting point in both cases is the difference equation
\[ \left(A_{n+1}^{m+1/2}u_{n+1}^{m+1/2}-A_n^{m+1/2}u_n^{m+1/2}\right)/\Delta x +\left(B_{n+1/2}^{m+1}u_{n+1/2}^{m+1}-B_{n+1/2}^{m}u_{n+1/2}^{m}\right)/\Delta y +C_{n+1/2}^{m+1/2}u_{n+1/2}^{m+1/2}=f_{n+1/2}^{m+1/2}. \tag{8} \]
Here \(n=0,1,\ldots,N;\ m=0,1,\ldots,M;\ N\Delta x=|b-a|;\ M\Delta y=|d-c|;\)
\(A_n^{m+1/2}=A[a+n\Delta x,c+(m+1/2)\Delta y]\), etc. The principal unknowns are taken to be \(u_{n+1/2}^{m+1/2}\).
In order to obtain a complete system of algebraic equations, one must specify the relation between the quantities \(u_{n+1}^{m+1/2}\), \(u_n^{m+1/2}\), \(u_{n+1/2}^{m+1}\), \(u_{n+1/2}^{m}\), and \(u_{n+1/2}^{m+1/2}\), as well as the boundary conditions. For \(x=a\) the boundary conditions have the form:
\[ (u^+)_{0}^{m+1/2}=(\theta_a)^{m+1/2}\cdot (u^-)_{0}^{m+1/2}+(\varphi_a)^{m+1/2}. \]
The boundary conditions for \(x=b,\ y=c,d\) are set analogously.
Let us proceed to eliminate the “auxiliary” unknowns.
a) First basic scheme. Using the matrix \(A_n^{m+1/2}\), construct the decomposition
\[ u_n^{m+1/2}=(u^+)_n^{m+1/2}+(u^-)_n^{m+1/2}+(u^0)_n^{m+1/2}. \]
At the point \((m+1/2,n+1/2)\) write two decompositions:
\[ \begin{aligned} u_{n+1/2}^{m+1/2} &=(u_n^+)_{n+1/2}^{m+1/2}+(u_n^-)_{n+1/2}^{m+1/2}+(u_n^0)_{n+1/2}^{m+1/2} &&\text{(using }A_n^{m+1/2}\text{)},\\ u_{n+1/2}^{m+1/2} &=(u_{n+1}^+)_{n+1/2}^{m+1/2}+(u_{n+1}^-)_{n+1/2}^{m+1/2}+(u_{n+1}^0)_{n+1/2}^{m+1/2} &&\text{(using }A_{n+1}^{m+1/2}\text{)}. \end{aligned} \tag{9} \]
The relation between the quantities \(u_n^{m+1/2}\), \(u_{n+1}^{m+1/2}\), \(u_{n+1/2}^{m+1/2}\) is specified by the equalities
\[ (u^+)_{n+1}^{m+1/2}=(u_{n+1}^+)_{n+1/2}^{m+1/2},\qquad (u^-)_{n}^{m+1/2}=(u_n^-)_{n+1/2}^{m+1/2}. \]
The relation between the vectors \(u_{n+1/2}^{m+1}\), \(u_{n+1/2}^{m}\), \(u_{n+1/2}^{m+1/2}\) is specified analogously. For the decomposition of the space \(R\), the matrices \(B_{n+1/2}^{m+1}\), \(B_{n+1/2}^{m}\) are used.
b) Second basic scheme. Put
\[ u_n^{m+1/2}=\frac12\left(u_{n+1/2}^{m+1/2}+u_{n-1/2}^{m+1/2}\right),\qquad u_{n+1/2}^{m}=\frac12\left(u_{n+1/2}^{m+1/2}+u_{n+1/2}^{m-1/2}\right). \tag{10} \]
In this case “extra” unknowns are introduced:
\(u_{-1/2}^{m+1/2}\), \(u_{N+1/2}^{m+1/2}\), \(u_{n+1/2}^{-1/2}\), \(u_{n+1/2}^{M+1/2}\).
To obtain a complete system of algebraic equations it is necessary to use difference boundary conditions (cf. (9))
\[ \begin{aligned} (u_0^-)_{-1/2}^{m+1/2}&=(u_0^-)_{1/2}^{m+1/2},& (u_0^0)_{-1/2}^{m+1/2}&=(u_0^0)_{1/2}^{m+1/2},\\ (u_N^+)_{N+1/2}^{m+1/2}&=(u_N^+)_{N-1/2}^{m+1/2},& (u_N^0)_{N+1/2}^{m+1/2}&=(u_N^0)_{N-1/2}^{m+1/2}. \end{aligned} \tag{11} \]
The difference boundary conditions for \(y=c,d\) are set analogously. We note that, as a rule, the order of the difference equation is higher than the order of the differential equation. Therefore the difference boundary conditions (11) are superfluous from the point of view of the differential equations. For example, for the equation \(u_x+u_y=0\) it is sufficient to set boundary conditions at \(x=a\) and \(y=c\) (conditions of type (2)). For the difference analogue of this equation one has also to set difference boundary conditions of type (11) at \(x=b\) and \(y=d\). A similar scheme with difference boundary conditions was already proposed by S. K. Godunov \((^3)\).
It is clear that in one direction one of the described schemes may be used, and in the other direction another. This is convenient, for example, in the computation of evolutionary problems. Other hybrid schemes are also possible, but we shall not dwell on this.
- We shall prove the stability of the schemes described under assumptions analogous to those adopted in Sec. 1. Let \(\varphi=0\) and let the inequalities hold (cf. (4), (5))
\[ (A_{n+1}^{m+1/2}-A_n^{m+1/2})/\Delta_x+ (B_{n+1/2}^{m+1}-B_{n+1/2}^m)/\Delta_y+ (C+C')_{n+1/2}^{m+1/2}\ge 2aE; \tag{12} \]
\[ \begin{aligned} &[A^+-\theta_b' A^-\theta_b]_N^{m+1/2}\ge 0, \qquad [A^- - \theta_a' A^+\theta_a]_0^{m+1/2}\ge 0,\\ &[B^+-\theta_d' B^-\theta_d]_{n+1/2}^{M}\ge 0, \qquad [B^- - \theta_c' B^+\theta_c]_{n+1/2}^{0}\ge 0. \end{aligned} \tag{13} \]
Multiply (8) scalarly by \(u_{n+1/2}^{m+1/2}\) and use the following equalities, analogous to equality (6).
For scheme a)
\[ \left( u_{n+1/2},\, \frac{A_{n+1}u_{n+1}-A_nu_n}{\Delta} \right) = \]
\[ = \frac{(u_{n+1},A_{n+1}u_{n+1})-(u_n,A_nu_n)}{2\Delta} + \left( u_{n+1/2},\, \frac{A_{n+1}-A_n}{2\Delta}u_{n+1/2} \right) - \]
\[ - \frac{1}{2\Delta} \bigl([u_{n+1}-u_{n+1/2}],\,A_{n+1}[u_{n+1}-u_{n+1/2}]\bigr) + \]
\[ + \frac{1}{2\Delta} \bigl([u_n-u_{n+1/2}],\,A_n[u_n-u_{n+1/2}]\bigr). \]
In view of (9), the last two terms are nonnegative.
For scheme b)
\[ \left( u_{n+1/2},\, \frac{ A_{n+1}\dfrac{u_{n+1/2}+u_{n+1/2}}{2} - A_n\dfrac{u_{n+1/2}+u_{n-1/2}}{2} }{\Delta} \right) = \]
\[ = \frac{(u_{n+1/2},A_{n+1}u_{n+1/2})-(u_{n-1/2},A_nu_{n+1/2})}{2\Delta} + \left( u_{n+1/2},\, \frac{A_{n+1}-A_n}{2\Delta}u_{n+1/2} \right). \]
After summation over \(m,n\), in both cases we obtain
\[ \sum_{m,n}(u,u)_{n+1/2}^{m+1/2}\,\Delta_x\Delta_y \le \frac{1}{a^2} \sum_{m,n}(f,f)_{n+1/2}^{m+1/2}\,\Delta_x\Delta_y. \tag{14} \]
Inequalities analogous to (7), (14) can also be proved under weaker assumptions. Using (14), one can prove convergence of the described schemes in the class of generalized solutions. If the coefficients of equation (1), \(f\), and the solution are sufficiently smooth, then the first scheme has first order of accuracy, and the second has second order of accuracy.
The results obtained are easily extended to domains composed of a finite number of rectangles, and to the multidimensional case.
I express my gratitude to A. L. Krylov for a number of useful comments in connection with the present work.
Institute of Hydrodynamics
Siberian Branch of the Academy of Sciences of the USSR
Received
4 III 1967
REFERENCES
- F. Riesz, B. Sz.-Nagy, Lectures on Functional Analysis, IL, 1960.
- K. O. Friedrichs, Proceedings of the Soviet-American Symposium on Partial Differential Equations, Novosibirsk, 1963.
- S. K. Godunov, Difference Methods for Solving Equations of Gas Dynamics, Novosibirsk, 1962.