Stability of difference schemes

One of the important concepts in the theory of difference (grid) methods, characterizing the continuous dependence of the solution of a difference scheme on the input information. More precisely, suppose that a difference scheme (a difference or grid analogue of the original problem) is constructed on a set of grids , with , in the space of the independent variable for the original problem, where the parameter is an element of a certain normed linear space and characterizes the concrete grid being used. Suppose that to each such grid corresponds an -dimensional linear space and an operator equation in (a system of difference equations)

(1)

for which and the operator is given. Usually is connected with the dimensions of a cell of the grid and increases without bound as . Let and be elements of the normed spaces and , while the operator is linear. Then the difference scheme is said to be stable if: 1) for any , exists; and 2) there exists a constant , not depending on and such that

(2)

This definition is equivalent to the well-posedness (correctness) of (1): A solution of (1) exists and is unique for any right-hand side and its dependence on is uniformly continuous (in ) in the sense of the spaces and . In the language of a priori estimates this means that there exists a constant , not depending on , such that for any solution (1) there holds the a priori estimate

(3)

Thus, if for a stable difference scheme, for one reason or another (e.g. by means of an approximate solution of (1)), one actually determines not the function in (1) but a function of the perturbed equation , then it is easy to find an upper estimate for the error:

(4)

Moreover, if the difference scheme is stable and approximates the original problem in the sense of the space , then it is convergent, with an estimate of the error:

(5)

where is the error of the scheme and is the error of the approximation (cf. [1]–[7]). The theorem mentioned explains the reason why is considered as an element of a normed space : the error of approximation depends essentially on the choice of . Therefore, for a fixed space a stability theorem of type (3) should be used with the weakest norm in which the order of approximation increases. And for a fixed it is appropriate to study (1) by using the strongest norm . In this relation there is a complete analogy with the problem of studying the well-posedness of the original boundary value problem. Therefore the spaces and themselves are usually constructed as grid analogues of well-known function spaces (e.g. , , , etc., cf. [3]–[5]) and they admit a corresponding passage to the limit as . For examples of the choice of such grid spaces, for different methods of studying the stability of difference schemes in these spaces, and other similar results cf. [1]–[15]. In projection-grid methods (finite-element methods) for stationary problems the most widespread is the means of studying the convergence of the basic error estimates by the distance of the solution from the approximating subspace (cf. [3]–[5], [7], [10]–[13]). Then the stability theorems of type (3) are only needed to obtain the estimate (4) and their study for and , which now coincides with Euclidean spaces of grid functions, often invokes the traditional algebraic approach connected with studying the condition number of the matrix (cf. [10]–[12]).

In non-stationary problems the role of the independent variable is essentially different from the role of the space variables, and this circumstance forces one to consider separately a time grid and a grid for the space variables . In the same way one defines a specific difference scheme for non-stationary problems connected with a stratification (cf. [1]–[6]). For simplicity of description it is here assumed that is defined by the step , i.e.

while the grid is defined by the step vector in the space variables, , . Then the grid in (1) is defined by , where and the space consists of the vectors , where each lies in the linear space of grid functions given on . Therefore the norms in the spaces and encountered in (2)–(5) are usually defined by different norms and for the linear space of grid functions given on . For example, as one often chooses an expression of the type , , etc. (cf. [1]–[6]). The most detailed study of these cases has been when and are Euclidean or unitary spaces and where it was possible to obtain estimates of the type (3) by relatively simple means. E.g. consider a linear one-level difference scheme of the form

(6)

where the vectors and are defined by initial conditions and the right-hand sides of the equations, and where the operators and in the Euclidean space are such that , , where the non-negative constants and do not depend on the grid. Then the following a priori estimate holds for the solution of (6):

(7)

Very often the analysis of such schemes, after expressing it in the canonical form

leads to a basic study of the properties of the transition operator (where is the identity operator) under the assumption that there is a certain relatively simple information-type operator inequality for and in the Euclidean space . E.g. if , and , then (cf. [3], [6]) there exists a constant such that

(8)

where . Similar results have been obtained for a sufficiently large class of difference schemes, including certain multi-step schemes (cf. [6]). For this, certain special cases of stability have been studied (stability with respect to the initial conditions, or with respect to the right-hand side) and their interdependence. There are results connected with necessary conditions similar to stability or related to it (cf. [3], [6]). An application of the energy inequality (cf. [4], [5]) instead of (8) leads one, under related conditions, to estimates of the form

(9)

which reduce to stability in a certain relatively stronger norm for , and allows one to pass to the limit in this estimate. Such estimates are often encountered in the theory of evolution equations. Similar estimates have also been obtained for a very large class of schemes (cf. [4], [5], [13]).

For a study of the stability of difference schemes one distinguishes conditionally-stable difference schemes for explicit schemes for the heat equation, in which one has stability only under conditions like , and absolutely-stable schemes in which the steps for the time and space variables can be changed independently of each other without affecting stability. Schemes of this type are often preferred, if they do not require the solution of a complicated system at each step. Alternating-directions implicit schemes, splitting schemes, schemes with splitting operators and additive schemes, cf. [1]–[6], [13], lead to such economic difference schemes for multi-dimensional problems.

Stability theorems with estimates of the type (3), (9) are also used in cases where the degree of approximation and the estimate (5) cannot be considered, but the corresponding prolongations of solutions of the grid problems are constructed and, basically, a theorem on compact convergence to the solution of the original problem has been established (cf. [4], [5]). The study of various a priori estimates and the compactness principle mentioned are particular characteristics for complicated non-linear problems, in which the solution may be non-unique, and the convergence is established only for certain solutions of the original problem. Sometimes the study of non-linear problems of mathematical physics is, because of the complexity of these problems, changed to a study of linearizations of the equations, and for difference schemes main attention has been paid to grid analogues of important physical conservation laws (cf. [8]). For weak non-linear problems the study of the correctness of difference schemes has often been worked out in the sufficient completeness which is characteristic for the linear case (cf. [5]–[7] and Non-linear boundary value problem, numerical methods).

In the case of the Cauchy problem for ordinary differential equations a study of the stability of difference schemes has often been reduced in model situations to the study of the roots of the characteristic equation (cf. [2], [14], [15]).

References

[1]	A.R. Mitchell, "Computational methods in partial differential equations" , Wiley (1969)
[2]	I.S. Berezin, N.P. Zhidkov, "Computing methods" , Pergamon (1973) (Translated from Russian)
[3]	S.K. Godunov, V.S. Ryaben'kii, "The theory of difference schemes" , North-Holland (1964) (Translated from Russian)
[4]	E.G. D'yakonov, "Minimization of computational work. Asymptotically-optimal algorithms" , Moscow (1989) (In Russian)
[5]	E.G. D'yakonov, "Difference methods for solving boundary value problems" , 1–2 , Moscow (1971–1972) (In Russian)
[6]	A.A. Samarskii, A.V. Gulin, "Stability of difference schemes" , Moscow (1973) (In Russian)
[7]	A.A. Samarskii, V.B. Andreev, "Méthodes aux différences pour équations elliptiques" , MIR (1978) (Translated from Russian)
[8]	A.A. Samarskii, Yu.P. Poppov, "Difference methods for the solution of problems in gas dynamics" , Moscow (1980) (In Russian)
[9]	O.A. Ladyzhenskaya, "The mathematical theory of viscous incompressible flows" , Gordon & Breach (1963) (Translated from Russian)
[10]	O. Axelson, V.A. Barker, "Finite element solution of boundary value problems. Theory and computation" , Acad. Press (1984)
[11]	W. Hackbusch, "Theorie und Numerik elliptischer Differentialgleichungen" , Teubner (1986)
[12]	G. Strang, J. Fix, "An analyse of the finite element method" , Prentice-Hall (1973)
[13]	G. Fairweather, "Finite element Galerkin methods for differential equations" , M. Dekker (1978)
[14]	N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[15]	Yu.V. Rakitskii, S.M. Ustinov, I.G. Chernorustskii, "Computational methods for the solution of stiff systems" , Moscow (1979) (In Russian)

References

[a1]	L. Lapidus, G.F. Pinder, "Numerical solution of partial differential equations in science and engineering" , Wiley (1982)