Abstract Generated abstract
This paper studies coefficient stability for three point finite difference schemes approximating a one dimensional second order boundary value problem with possibly discontinuous coefficients. The authors define stability with respect to small integral perturbations of the scheme coefficients, establish bounds for the corresponding difference Green’s function, and derive necessary conditions for stability. They prove that, within the canonical class considered, coefficient stability is equivalent to conservativeness of the scheme, and that homogeneous conservative schemes satisfy the coefficient stability principle. The paper also identifies a unique “best” conservative canonical scheme with second integral order accuracy under stronger stability requirements, discusses quadrature based noncanonical variants, and notes limitations of second order asymptotics for discontinuous coefficients.
Full Text
MATHEMATICS
Corresponding Member of the Academy of Sciences of the USSR A. N. Tikhonov and A. A. Samarskii
ON THE COEFFICIENT-STABILITY OF DIFFERENCE SCHEMES
The question of the stability of the solution of difference boundary-value problems with respect to the coefficients of difference schemes (of coefficient-stability) is considered. It is shown that a necessary and sufficient condition for the coefficient-stability of a canonical scheme is its conservativeness.
1. Consider on the interval \(0 \leq x \leq 1\) the class of boundary-value problems
\[ L^{(p,q,f)}u \equiv \frac{d}{dx}\left[\frac{1}{p(x)}\frac{du}{dx}\right] - q(x)u + f(x) = 0,\quad 0 < x < 1, \]
\[ u(0)=\mu_1,\qquad u(1)=\mu_2. \tag{1} \]
The coefficients of the equation belong to the class \(Q_0\) of piecewise-continuous functions and satisfy the conditions:
\[ 0<K_1 \leq p(x)\leq K_2,\qquad 0\leq q(x)\leq K_2,\qquad |f(x)|\leq K_2, \tag{2} \]
where \(K_1\) and \(K_2\) are positive constants.
Let \(S_N=\{x_0=0,\ x_1=h,\ldots,\ x_i=ih,\ldots,\ x_N=Nh=1\}\) be a uniform difference grid with step \(h=\frac{1}{N}\), and let \(L_h^{(p,q,f)}y_i\) be a homogeneous three-point difference scheme corresponding to the operator
\[ L_h^{(p,q,f)}y_i = \frac{1}{h^2}\left[(y_{i+1}-y_i)/B_i^h-(y_i-y_{i-1})/A_i^h\right] -D_i^h y_i+F_i^h; \tag{3} \]
\[ A_i^h=A^h[\bar p_i(s)],\qquad B_i^h=B^h[\bar p_i(s)],\qquad -1<s<1,\qquad \bar p_i(s)=p(x_i+sh); \]
\[ D_i^h=D^h[q(x_i+sh)],\qquad F_i^h=F^h[f(x_i+sh)],\qquad -0.5<s<0.5. \]
The functionals \(A^h\), \(B^h\), \(D^h\), and \(F^h\) satisfy the conditions \(A_1, A_2, A_3\) of work \((^1)\), i.e., we consider the same initial class of difference schemes as in work \((^1)\). It is assumed here that \(D^h\) and \(F^h\) are linear functionals.
2. If \(B_i^h=A_{i+1}^h\), then the difference operator \(L_h\) is called conservative. A conservative operator can be written in the self-adjoint form
\[ L_h y_i \equiv \frac{1}{h^2}\Delta(\nabla y_i/A_i^h)-D_i^h y_i+F_i^h,\quad \text{where }\Delta y_i=y_{i+1}-y_i,\ \nabla y_i=y_i-y_{i-1}. \tag{3'} \]
Let us note that the difference scheme (3) can be made conservative by multiplication by the multiplier
\[ \mu_i=\prod_{s=1}^{i-1}(A_{s+1}^h/B_s^h). \tag{4} \]
As a result, we obtain a conservative, generally speaking, nonhomogeneous scheme.
- The difference Green’s function \(G_{i,k}\) is defined by the conditions
\[ L_h^{(p,q)}G_{i,k}=-\frac{\delta_{i,k}}{h},\qquad G_{0k}=G_{Nk}=0,\qquad \delta_{ik}= \begin{cases} 1, & i=k,\\ 0, & i\ne k. \end{cases} \tag{5} \]
The solution of the boundary-value problem
\[ L_h^{(p,q)}z_i=-\varphi_i,\qquad 0<i<N,\qquad z_0=0,\qquad z_N=0 \tag{6} \]
is given by the formula
\[ z_i=\sum_{k=1}^{N-1}G_{ik}\varphi_k h. \tag{7} \]
The Green’s function \(G_{ik}\) satisfies the following “symmetry” condition:
\(\mu_iG_{ik}=\mu_kG_{ki}\), where \(\mu_i\) is given by formula (4). For the conservative operator \(L_h^{(p,q)}\), \(B_s^h=A_{s+1}^h\), \(\mu_i=1\), and we obtain the symmetry condition \(G_{ik}=G_{ki}\).
Lemma 1. If the coefficients \(p(x), q(x)\) of the class \(Q_0\) satisfy conditions (2), and \(L_h^{(p,q)}\) is the initial difference scheme of the form (3), then the difference Green’s function \(G_{ik}\), defined by conditions (5), and its first difference quotients
\[ (G_{i,k+1}-G_{i,k})/h \qquad (0\le i\le N,\; 0\le k\le N-1); \]
\[ (G_{i+1,k}-G_{i,k})/h \qquad (0\le i\le N-1,\; 0\le k\le N) \]
are bounded in absolute value by a constant depending only on \(K_1, K_2\).
- In solving difference boundary-value problems it may turn out that, for one reason or another, the coefficients of the difference equations are determined inaccurately. However, it is desirable that under a small distortion of the coefficients the solution of the problem should change little.
Let \(y_i\) and \(\widetilde y_i\) be solutions of the difference boundary-value problems
\[ L_h^{(p,q,f)}y_i=0,\qquad 0<i<N,\qquad y_0=\mu_1,\qquad y_N=\mu_2, \tag{8} \]
\[ \widetilde L_h^{(p,q,f)}\widetilde y_i=0,\qquad \widetilde y_0=\mu_1,\qquad \widetilde y_N=\mu_2, \]
\[ \widetilde L_h^{(p,q,f)}\widetilde y_i =h^{-2}\bigl(\Delta y_i\,|\widetilde B_i^h-\nabla y_i\,|\widetilde A_i^h\bigr) -\widetilde D_i^h\widetilde y_i+\widetilde F_i^h. \tag{9} \]
Here the coefficients of the equation are distorted either through distortion of the coefficients of the differential equation, or through inaccuracy in the computation of the functionals \(A^h, B^h, D^h\), and \(F^h\), or, finally, as a result of both of the indicated causes.
We shall say that the difference scheme (3) satisfies the principle of coefficient-stability if, from the conditions
\[ \sum_{i=1}^{N-1}|\widetilde A_i^h-A_i^h|h=\rho(h),\qquad \sum_{i=1}^{N-1}|\widetilde B_i^h-B_i^h|h=\rho(h), \]
\[ \sum_{i=1}^{N-1}|\widetilde D_i^h-D_i^h|h=\rho(h),\qquad \sum_{i=1}^{N-1}|\widetilde F_i^h-F_i^h|h=\rho(h), \tag{10} \]
where \(\rho(h)\to0\) as \(h\to0\), there follows convergence of the solution \(\widetilde y_i\) of the difference boundary-value problem (9) to the solution \(u(x)\) of problem (1), i.e.,
\[ |\widetilde y_i-u(x_i)|\le \rho_0(h)\to0 \qquad \text{as } h\to0. \tag{11} \]
Hence, in particular, it follows that for a coefficient-stable scheme
\[ |y_i-u(x_i)|\leqslant \rho_1(h),\qquad |y_i-\widetilde y_i|\leqslant \rho_2(h), \]
where \(\rho_1(h), \rho_2(h)\to 0\) as \(h\to 0\).
If in conditions (10) and (11) one replaces them by
\[ \rho(h)=O(h^n),\qquad \rho_0(h)=O(h^n), \tag{12} \]
then we obtain the principle of coefficient-stability of \(n\)-th order.
5. We formulate a necessary condition for coefficient-stability.
Let \(p(x)\) have a discontinuity at the point \(\xi=x_n+\theta h,\; 0\leqslant \theta\leqslant 1,\; x_n=nh\), so that \(p_\ell=p(\xi-0)\ne p_r=p(\xi+0)\). Introduce the function \(\widetilde p(x,h)\), coinciding with \(p(x)\) everywhere except on the intervals \((x_n,x_{n+1})\) and \((x_{n+1},x_{n+2})\). Then for coefficient-stability of a scheme \(\dot L_h^{(p,q,f)}\) of the form (3), it is necessary that the condition
\[ \widetilde B_n^h\widetilde B_{n+1}^h\widetilde B_{n+2}^h/p_r - \widetilde A_n^h\widetilde A_{n+1}^h\widetilde A_{n+2}^h/p_\ell = \rho(h)\to 0 \quad \text{as } h\to 0 \tag{13} \]
be satisfied.
It is not difficult to notice that the necessary condition for convergence in the class of discontinuous coefficients, obtained earlier in works \((^3,^4)\), is a consequence of the necessary condition of coefficient-stability (13) (for \(\widetilde p\equiv p\)).
6. Lemma 2. Every conservative scheme \(\dot L_h^{(p,q,f)}\) from the original family of schemes satisfies the necessary condition of coefficient-stability (13).
Lemma 3. Let \(y_i,\widetilde y_i\) be solutions of the boundary-value problems
\[ L_h y_i=0,\qquad y_0=\mu_1,\qquad y_N=\mu_2;\qquad \widetilde L_h\widetilde y_i=0,\qquad \widetilde y_0=\mu_1,\qquad \widetilde y_N=\mu_2, \]
where \(L_h,\widetilde L_h\) are conservative difference operators of the form \((3')\), whose coefficients satisfy the conditions
\[ 0<K_1\leqslant A_i^h\leqslant K_2,\qquad 0\leqslant D_i^h\leqslant K_2,\qquad |F_i^h|\leqslant K_2. \tag{2'} \]
Then the inequality holds
\[ |y_i-\widetilde y_i|_{(0\leqslant i\leqslant N)} \leqslant C\left\{ \sum_{k=1}^{N}|\widetilde A_k^h-A_k^h|h + \sum_{k=1}^{N-1}|\widetilde D_k^h-D_k^h|h + \sum_{k=1}^{N-1}|\widetilde F_k^h-F_k^h|h \right\}, \tag{14} \]
where \(C\) is a constant depending only on \(K_1\) and \(K_2\).
An analogous lemma holds for problem (1).
Choosing as \(\widetilde L_h\) the exact scheme \(\widetilde L_h^{(p,q,f)}\) (see (2)), and as \(L_h\) a conservative scheme \(\dot L_h^{(p,q,f)}\) from the original family of schemes and relying on Lemma 3, it is not difficult to prove the theorem (cf. (1)).
Theorem 1. If a conservative scheme \(\dot L_h^{(p,q,f)}\) from the original family has, in some class \(C_{m_k,m_q,m_f}\), \(n\)-th integral order of accuracy, then it has this same \(n\)-th order of accuracy for coefficients from the class \(C_{n-1}^{(1)}\), i.e., for \(p\in C_{n-1}^{(1)},\; q\in C_{n-1}^{(1)},\; f\in C_{n-1}^{(1)}\).
7. We now consider the canonical scheme (see (1))
\[ L_h^{(p,q,f)}y_i = h^{-2}\,[\Delta y_i/B_i-\nabla y_i/A_i] - D_i y_i + F_i, \tag{15} \]
whose functionals do not depend on \(h_3\), and require that it satisfy the necessary condition (13).
Theorem 2. If the canonical difference scheme (15) from the original family of schemes satisfies the necessary condition of coefficient-stability (13), then it is conservative, i.e. \(B_i=A_{i+1}\) or \(B[\psi(s)]=A[\psi(1+s)]\).
\(*\) \(C_m^\gamma\) \((0\leqslant \gamma\leqslant 1)\) is the class of functions having on the segment \([0,1]\) a continuous derivative of order \(m\), satisfying a Hölder condition of order \(\gamma\).
Relying on Theorem 2 and Lemmas 2 and 3, one can verify that:
Theorem 3. Every homogeneous conservative scheme from the original family of schemes satisfies the principle of coefficient-stability.
As a result we arrive at the following basic theorem.
Theorem 4. A necessary and sufficient condition for the coefficient-stability of the canonical scheme \(L_h^{(p,q,f)}\) is its conservativeness.
Theorem 5. Every conservative scheme \(L_h^{(p,q,f)}\) has first integral order of accuracy in the class \(Q_1^0\).
§ 8. Let us now require that the difference scheme \(L_h^{(p,q,f)}\) satisfy the necessary conditions of coefficient-stability of rank 2.
Theorem 6. There exists a unique canonical scheme (“the best conservative scheme”) having second integral order of accuracy in \(Q_1^{(1)}\) and satisfying the principle of coefficient-stability of rank 2; this scheme \(L_h^{(p,q,f)}\) is conservative and is determined by means of the functionals
\[ A[\psi]=\int_{-1}^{0}\psi(s)\,ds,\qquad D[\psi]=F[\psi]=\int_{-0.5}^{0.5}\psi(s)\,ds . \tag{16} \]
We note that in the proof of this theorem, in particular, Lemma 1 is used.
§ 9. Replacing the integral defining \(A[\psi]\) in formula (16) by a scheme based on some quadrature formula, we obtain, instead of the best canonical scheme \(L_h^{(p)}\), a noncanonical scheme
\[ \widetilde{L}_h^{(p)}y_i=\frac{1}{h^2}\Delta(\nabla y_i/\widetilde{A}_i^h), \qquad \text{where }\ \widetilde{A}_i^h=\widetilde{A}^{h_1}[p(x_i+sh)], \]
\[ \widetilde{A}^{h_1}[\psi(s)]=\sum_{j=1}^{J}a_j\psi(s_j),\qquad s_j=-1+jh_1,\qquad h_1=1/J. \]
Theorem 7. In order that the noncanonical scheme \(\widetilde{L}_h^{(p)}\) defined above have second integral order of accuracy in the class \(Q_1^{(1)}\), it is necessary and sufficient that \(h_1/h=O(1)\) as \(h\to0\) \((N\to\infty)\).
An analogous theorem also holds for the scheme \(\widetilde{L}_h^{(p,q,f)}y_i=\widetilde{L}_h^{(p)}y_i-\widetilde{D}_i^h y_i+\widetilde{F}_i^h\), whose functionals \(\widetilde{D}^{h_1}\) and \(\widetilde{F}^{h_1}\) are computed by analogy with the functional \(\widetilde{A}^{h_1}\).
§ 10. In work [1] we consider an asymptotic expansion for the solution of a difference boundary-value problem in the case of discontinuous coefficients. If \(p(x)\), \(q(x)\), and \(f(x)\) are functions of the class \(Q_2^{(0)}\), and \(L_h^{(p,q,f)}\) is the best canonical scheme, then the solution of problem (8) can be represented in the form
\[ y_i=u(x_i)+h^2Y(x_i,h)+O(h^4), \]
where \(Y(x,h)=O(1)\) and is a function having no limit as \(h\to0\). Hence it follows that, in the case of discontinuous coefficients, the solution of the difference boundary-value problem (8) does not have asymptotics of second order as \(h\to0\).
Received
31 XII 1959
REFERENCES
- A. N. Tikhonov, A. A. Samarskii, DAN, 131, No. 4 (1960).
- A. N. Tikhonov, A. A. Samarskii, DAN, 131, No. 3 (1960).
- A. N. Tikhonov, A. A. Samarskii, DAN, 108, No. 3 (1956).
- A. N. Tikhonov, A. A. Samarskii, DAN, 122, No. 4 (1959).
* \(Q_m^\gamma\) \((0\le \gamma\le 1)\) is the class of functions having on \([0,1]\) \(m\) piecewise-continuous derivatives, with the \(m\)-th derivative satisfying, in the intervals of its discontinuity, a Hölder condition of order \(\gamma\).