Difference schemes, theory of

The branch of numerical mathematics studying methods for finding approximate solutions to differential equations by replacing them by finite-difference equations (difference schemes).

The theory of difference schemes studies methods for constructing difference schemes, investigates the correctness of difference problems and the convergence of the solution of a difference problem to the solution of the original differential problem, and deals with the justification of algorithms for the solution of difference problems. A finite-difference method (also called a grid method) is a universal computing method enabling one to effectively solve complicated problems in mathematical physics, including non-linear problems. A distinctive feature of the contemporary theory of difference schemes is the orientation towards the construction and investigation of methods suitable for a computer.

Basic concepts.

A finite-difference method is applied in the theory of differential equations as an effective means for proving existence theorems. The problems in the theory of difference schemes are essentially quite different when the aim is mathematical computation. When finding an approximate solution to some problem in mathematical physics it is assumed in advance that this problem is well-posed; furthermore, the basic aim of the theory of difference schemes becomes that of finding and justifying the best method for solving the original differential equation, and of formulating general principles for constructing difference schemes with given properties for a wide class of problems in mathematical physics.

Below the basic concepts with which the theory of difference schemes operates — the concepts of approximation, stability and convergence — are presented for a fairly general example and one possible approach to the construction of a theory of difference schemes is illustrated.

Suppose one has to find the solution, in an $ n $- dimensional region $ G $ with boundary $ \Gamma $, of a differential equation

$$ \tag{1 } Lu ( x) = f ( x),\ \ x = ( x _ {1} \dots x _ {n} ) \in G, $$

with additional (boundary, initial) conditions

$$ \tag{2 } lu ( x) = \mu ( x),\ \ x \in \Gamma , $$

where $ L $ and $ l $ are linear differential operators and $ f $, $ \mu $ are given functions. Let the problem (1), (2) be well-posed in a certain class of functions (that is, its solution $ u $ exists and depends uniquely and continuously on the input data $ f $ and $ \mu $). In a finite-difference method the region $ \overline{G}\; = G + \Gamma $ is replaced by a discrete set of points — the grid $ \overline{ {G _ {h} }}\; = G _ {h} + \Gamma _ {h} $. The parameter $ h = ( h _ {1} \dots h _ {n} ) $, the step of the grid, characterizes the density of the grid and usually, as $ | h | \rightarrow 0 $, the sequence of grids $ G _ {h} $ tends to fill the whole region $ \overline{G}\; $. The derivatives entering into (1), (2) are approximated on the grid $ \overline{ {G _ {h} }}\; $ by the corresponding difference relations. As a result a system of linear algebraic equations

$$ \tag{3 } L _ {h} y _ {h} ( x) = \ \phi _ {h} ( x),\ \ x \in G _ {h} ; \ \ l _ {h} y _ {h} ( x) = \ \chi _ {h} ( x),\ \ x \in \Gamma _ {h} , $$

is obtained, where $ y _ {h} $ is the unknown grid function, $ \phi _ {h} $, $ \chi _ {h} $ are given grid functions and $ L _ {h} $, $ l _ {h} $ are difference operators. The family of equations (3), which depends on the parameter $ h $, is called a difference scheme. Although equation (3) is obtained by approximating the original problem (1), (2), it can be considered as an independent mathematical object. The problem (1), (2) being well-posed does not imply, generally speaking, that the difference problem (3) is a well-posed (correct). Therefore, investigating the well-posedness of problem (3) is a first problem in the theory of difference schemes. In addition one studies, in the theory of difference schemes, whether the solution $ y _ {h} $ of the difference problem converges, as $ h \rightarrow 0 $, to the solution $ u $ of the original differential problem. Well-posedness and convergence are closely connected.

Let the set of grid functions on $ \overline{ {G _ {h} }}\; $ form the vector space $ H _ {h} $ and let the operators $ L _ {h} $ and $ l _ {h} $ act on this space. Introduce the norms $ \| \cdot \| _ {(} 1h) $, $ \| \cdot \| _ {(} 2h) $, $ \| \cdot \| _ {(} 3h) $ in the spaces of solutions $ y _ {h} $ and right-hand sides $ \phi _ {h} $, $ \chi _ {h} $.

The difference problem (3) is said to be well-posed (correct) if for all sufficiently small $ | h | $ and for any $ \phi _ {h} , \chi _ {h} \in H _ {h} $ a unique solution exists and if the estimate

$$ \tag{4 } \| y _ {h} \| _ {(} 1h) \leq \ M ( \| \phi _ {n} \| _ {(} 2h) + \| \chi _ {h} \| _ {(} 3h) ) $$

is satisfied for some constant $ M $ not depending on $ h $. The latter property is called stability of the difference scheme and indicates that the solution depends uniformly, with respect to $ h $, on the input data. Estimates on the solution of the difference problem in terms of known right-hand sides of type (4) are called a priori estimates. Obtaining a priori estimates is at the basis of the theory of difference schemes.

To estimate the error, the solution of problem (3) is presented as a sum

$$ y _ {h} ( x) = \ u _ {h} ( x) + z _ {h} ( x), $$

where $ u _ {h} $ is the projection of the solution $ u $ of the problem (1), (2) onto the space $ H _ {h} $ and $ z _ {h} $ is the error of the approximate solution. Since problem (3) is linear, one obtains for the error $ z _ {h} $:

$$ \tag{5 } L _ {h} z _ {h} ( x) = \psi _ {h} ( x),\ \ x \in G _ {h} ; \ \ l _ {n} z _ {h} ( x) = \nu _ {h} ( x),\ \ x \in \Gamma _ {h} , $$

where

$$ \psi _ {h} ( x) = \ \phi _ {h} ( x) - L _ {h} u _ {h} ( x); \ \ \nu _ {h} ( x) = \ \chi _ {h} ( x) - l _ {h} u _ {h} ( x); $$

the functions $ \psi _ {h} $ and $ \nu _ {h} $ are called the errors of approximation, or local discretization errors, of the difference scheme (3) for equation (1) and the additional conditions (2), respectively. It is said that the scheme (3) is an $ m $- th order approximation to the problem (1), (2) if

$$ \| \psi \| _ {(} 2h) = \ O ( | h | ^ {m} ),\ \ \| \nu \| _ {(} 3h) = \ O ( | h | ^ {m} ),\ \ m > 0. $$

The scheme (3) has $ m $- th order accuracy, or converges at the rate $ O (| h | ^ {m} ) $, if

$$ \| y _ {h} - u _ {h} \| _ {(} 1h) = \ O ( | h | ^ {m} ). $$

Only one approximation is insufficient, generally speaking, for the convergence of the difference scheme: it is necessary to require further that the difference problem (3) be well-posed. Namely, the following assertion is true: If the difference scheme (3) is well-posed and has $ m $- th order approximation, then it converges at the rate $ O ( | h | ^ {m} ) $( see [28]).

Other approaches to the construction of a theory of difference schemes are possible. Thus, in Lax's theory (see [8]) convergence of difference schemes is studied not in spaces of grid functions but in the solution space of the original differential problem; here the so-called equivalence theorem is proved: If the original problem (1), (2) is well-posed and the scheme (3) approximates problem (1), (2), then stability is necessary and sufficient for convergence. Other versions of the connection between stability and convergence are possible (see, for example, [9]). There has been some research also into the convergence of difference schemes in generalized solution spaces (see [10]).

Requirements for difference schemes.

For calculations on a modern computer it is not always sufficient to require that a difference scheme be convergent as $ | h | \rightarrow 0 $. To be able to use an actual grid with a finite grid step requires the existence of a number of additional properties of the scheme. They amount to the fact that the difference scheme, besides having the usual approximation and stability properties, should also be a good model of the characteristic properties of the original differential equation. In addition, the difference scheme should satisfy definite conditions so that the computing algorithms are sufficiently simple in practice. Some of these additional requirements are considered below.

A uniform difference scheme (see [1], [11]) is understood to be a difference scheme of a type which does not depend either on the choice of the practical problem from a given class or on the choice of the difference grid. At all nodes of the grid for any problem from the given class the difference equations have the same form. Schemes related to uniform difference schemes are, in particular, transparent computation schemes for solving equations with rapidly changing or discontinuous coefficients. In transparent computation schemes the points of discontinuity in the coefficients do not have to be specified explicitly and the computation is carried out using the same formulas. Transparent computation schemes are widely used for calculating difference solutions to the equations in gas dynamics (see [1], [5], [12]).

A difference scheme may be conservative; this means that the given difference scheme has the same conservation law on the grid as the original differential equation. In particular, if $ L $ is a self-adjoint operator and the scheme (3) is conservative, then $ L _ {h} $ is self-adjoint in $ H $, that is, a conservative scheme preserves the property of being self-adjoint.

The usual method for obtaining conservative uniform schemes is the so-called balance method or the integro-interpolation method. The essence of the balance method consists in approximating, on the difference grid, the integral conservation law (the balance equation) corresponding to the given differential equation. The balance method has found wide application in approximating equations with variable, including discontinuous, coefficients. Another group of methods for constructing differences schemes which preserve the property of self-adjointness and positive definiteness of the original operator are methods based on variational principles (Ritz' method, a finite-element method, see Difference scheme, variational; Ritz method).

In constructing difference schemes for the equations in gas dynamics the principle of being totally conservative has been applied (see [5]). For equations of hyperbolic type investigating the dispersion properties of the corresponding difference equations has turned out to be useful (see [13]).

If it is known that, as $ t \rightarrow \infty $, the solution of the original differential problem tends to zero, then it is natural to require the same for the solution of the approximating difference problem. Schemes with this property are said to be asymptotically stable (see [4]).

Another approach to constructing difference schemes of better quality is to try to obtain schemes which satisfy the same a priori estimates which are characteristic (and which cannot be improved) for the original differential equations (see [14]).

Economic difference schemes for multi-dimensional problems in mathematical physics.

In solving systems of difference equations which approximate non-stationary multi-dimensional problems in mathematical physics (with two or more space coordinates) specific difficulties arise connected with the fact that the number of arithmetic operations necessary to determine solutions at the next time layer increases sharply on refining the grid. At the same time the solution of one-dimensional non-stationary problems can be effectively treated by a marching technique, which is economic in the sense that it requires a finite (independent of the grid step $ h $) number of actions at a single point of the grid. In general, a difference scheme is said to be economic if the ratio of the number of actions necessary to find the solution at the next time layer to the number of nodes of the space grid does not depend on the number of nodes in the grid. The usual implicit difference schemes are not economic. A most effective method for constructing economic difference schemes is to reduce a multi-dimensional problem to a few one-dimensional problems (the alternating-direction method, the decomposition method) (see [1], [15], [16]).

New algorithms have also stimulated a new approach to the basic concepts in the theory of difference schemes: approximation, stability and convergence. For example, the concept of a total approximation or an approximation in the weak sense has turned out to be fruitful (see [1], [16]). An additivity principle has been formulated which enables one to construct, in the general case, economic difference schemes which have the property of total approximation (see [17]). The schemes with equations on graphs and vector schemes are further generalizations of alternating-direction difference schemes (see [18]).

Methods for investigating well-posedness and convergence of difference schemes.

For linear problems stability and consistency imply convergence. Therefore, the theory of difference schemes has concentrated mainly on obtaining a priori estimates, which imply well-posedness of the problems in some norm. Methods for obtaining a priori estimates for difference schemes are to a large extent analogous to the same methods in the theory of differential equations. For example, one can cite the following methods: separation of variables, Fourier transformation, maximum principle, the energy inequality.

Methods for solving grid equations.

Any grid method for differential equations results in large systems of linear algebraic equations. For example, for multi-dimensional problems the number of equations typically reaches the order $ 10 ^ {4} $– $ 10 ^ {6} $. One-dimensional difference problems are usually solved by the shooting method (see [2]), which is a variation of the method of successive elimination of unknowns. Iteration methods are the most common methods for solving multi-dimensional grid equations. Iteration methods that are widely used in computing practice are the Richardson method with Chebyshev parameters; alternating-direction iteration methods; two-step iteration methods, which are a combination of the alternating-direction methods (internal iteration) and some classical method (external iteration). The method of upper relaxation and the alternate-triangular iteration method are also often used (see [2], [6]). The theory of iteration methods can be presented as a branch of the general theory of stability of difference schemes (see [2]).

There is a noticeable tendency to use direct (non-iterative) methods to solve multi-dimensional difference problems. Such methods are matrix shooting methods, discrete fast-Fourier transform methods and their generalizations, and the method of total representations.

Non-linear problems.

A theory of uniform difference schemes for non-linear equations of parabolic type has been developed (see [19]). Lax's theorem on the relation between stability and convergence has been generalized to the non-linear case (see [20], [21]). Difference schemes for non-linear elliptic equations (see , [24]) and for non-linear parabolic equations (see [21], [22]) have been considered. There are a number of general theorems on the well-posedness of difference schemes for the non-linear abstract Cauchy problem (see [25]). The convergence of difference schemes for the non-linear evolution equations has been studied (see [26], ).

References

[1]	A.A. Samarskii, "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian)
[2]	A.A. Samarskii, E.S. Nikolaev, "Numerical methods for grid equations" , 1–2 , Birkhäuser (1989) (Translated from Russian)
[3]	A.A. Samarskii, V.B. Andreev, "Méthodes aux différences pour équations elliptiques" , MIR (1978) (Translated from Russian)
[4]	A.A. Samarskii, A.V. Gulin, "Stability of difference schemes" , Moscow (1973) (In Russian)
[5]	A.A. Samarskii, Yu.P. Popov, "Difference schemes of gas dynamics" , Moscow (1975) (In Russian)
[6]	G.I. Marchuk, "Methods of numerical mathematics" , Springer (1982) (Translated from Russian)
[7]	S.K. Godunov, V.S. Ryaben'kii, "The theory of difference schemes" , North-Holland (1964) (Translated from Russian)
[8]	R.D. Richtmeyer, K.W. Morton, "Difference methods for initial value problems" , Wiley (1967)
[9]	N.N. Gudovich, "An abstract scheme for a difference method" USSR Comp. Math. Math. Physics , 6 : 5 (1966) pp. 185–194 Zh. Vychisl. Mat. i Mat. Fiz. , 6 : 5 (1966) pp. 916–921
[10]	N.N. Kuznetsov, "Asymptotic behaviour of the solutions of the finite-difference Cauchy problem" USSR Comp. Math. Math. Physics , 12 : 2 (1973) pp. 65–86 Zh. Vychisl. Mat. i Mat. Fiz. , 12 : 2 (1972) pp. 334–351
[11]	A.N. Tikhonov, A.A. Samarskii, "Homogeneous difference schemes" USSR Comp. Math. Math. Physics , 1 : 1 (1962) pp. 5–67 Zh. Vychisl. Mat. i Mat. Fiz. , 1 : 1 (1961) pp. 5–63
[12]	B.L. Rozhdestvenskii, N.N. Yanenko, "Systems of quasilinear equations and their applications to gas dynamics" , Amer. Math. Soc. (1983) (Translated from Russian)
[13]	D. Potter, "Computational physics" , Wiley (1973)
[14]	Yu.I. Mokin, "Two-layer parabolic and weakly parabolic difference schemes" USSR Comp. Math. Math. Physics , 15 : 3 (1976) pp. 111–121 Zh. Vychsl. Mat. i Mat. Fiz. , 15 : 3 (1975) pp. 661–671
[15]	I.V. Fryazinov, "Economic difference schemes for the two-dimensional equation of heat conduction with mixed derivatives" USSR Comp. Math. Math. Physics , 16 : 4 (1977) pp. 83–96 Zh. Vychsl. Mat. i Mat. Fiz. , 16 : 4 (1976) pp. 908–921
[16]	N.N. Yanenko, "The method of fractional steps; the solution of problems of mathematical physics in several variables" , Springer (1971) (Translated from Russian)
[17]	A.A. Samarskii, "Additivity principle for the construction of efficient difference schemes" Soviet Math. Dokl. , 6 (1965) pp. 1601–1605 Dokl. Akad. Nauk SSSR , 165 : 6 (1965) pp. 1253–1256
[18]	A.A. Samarskii, I.V. Fryazinov, "The method of summary approximation" Beitr. Numer. Math. , 4 (1975) pp. 191–203 (In Russian)
[19]	A.A. Samarskii, "Homogeneous difference schemes for nonlinear parabolic equations" USSR Comp. Math. Math. Phys. , 2 (1964) pp. 23–54 Zh. Vychisl. Mat. i Mat. Fiz. , 2 : 1 (1962) pp. 25–56
[20]	L.I. Yakut, "The theorems of Lax for nonlinear evolution equations" Soviet Math. Dokl. , 5 : 3 (1964) pp. 843–847 Dokl. Akad. Nauk SSSR , 156 : 6 (1964) pp. 1304–1307
[21]	R. Ansorge, R. Hass, "Konvergenz von Differenzenverfahren für lineare und nichtlineare Anfangswertaufgaben" , Springer (1970)
[22]	E.G. D'yakonov, "Difference methods for solving boundary value problems" , 2. Non-stationary problems , Moscow (1972) (In Russian)
[23a]	M.M. Karchevskii, A.D. Lyashko, "Difference schemes for nonlinear multidimensional elliptic equations I" Izv. Vyssh. Uchebn. Zaved. Mat. , 11 (1972) pp. 23–31 (In Russian)
[23b]	M.M. Karchevskii, A.D. Lyashko, "Difference schemes for nonlinear multidimensional elliptic equations II" Izv. Vyssh. Uchebn. Zaved. Mat. , 3 (1973) pp. 44–52 (In Russian)
[24]	M.P. Sapagovas, "The method of finite differences for the solution of quasilinear elliptic equations with discontinuous coefficients" USSR Comp. Math. Math. Phys. , 5 (1968) pp. 72–85 Zh. Vychisl. Mat. i Mat. Fiz. , 5 : 4 (1965) pp. 638–647
[25]	M.M. Karchevskii, A.V. Lapin, A.D. Lyashko, "Efficient difference schemes for quasilinear parabolic equations" Izv. Vyssh. Uchebn. Zaved. Mat. , 3 (1972) pp. 23–31 (In Russian)
[26]	A.V. Lapin, A.D. Lyashko, "Investigation of difference schemes for a certain class of quasilinear parabolic equations" Izv. Vyssh. Uchebn. Zaved. Mat. , 1 (1973) pp. 71–77 (In Russian)
[27a]	P.A. Raviart, "Sur l'approximation de certaines équations d'évolution linéaires et non linéaires" J. Math. Pures Appl. , 46 : 1 (1967) pp. 11–107
[27b]	P.A. Raviart, "Sur l'approximation de certaines équations d'évolution linéaires et non linéaires" J. Math. Pures Appl. , 46 : 2 (1967) pp. 109–183
[28]	V.S. Ryaben'kii, A.F. Filippov, "Ueber die Stabilität von Differenzengleichungen" , Deutsch. Verlag Wissenschaft. (1960) (Translated from Russian)

Comments

Additional references to the literature on the theory of approximating continuous problems by difference schemes and the solution of the resulting grid equations are given below.

In addition to the various methods for solving grid equations in this article, there is a relatively recently developed technique provided by the multi-grid method. In essence, the multi-grid method is an iteration method (cf. Iteration methods) employing a sequence of grids of decreasing coarseness. This method goes back to R.P. Federenko [a3] in 1962 and was strongly advocated by A. Brandt [a1]. An excellent introduction to multi-grid methods is provided by the tutorial [a2]. A more advanced and up-to-date analysis of multi-grid methods is given in [a4].

References

[a1]	A. Brandt, "Multi-grid adaptive technique (MLAT) for fast numerical solutions to boundary value problems" H. Cabannes (ed.) R. Temam (ed.) , Proc. 3-rd Internat. Conf. Numer. Methods in Fluid Mechanics , Springer (1977) pp. 82–89
[a2]	W.L. Briggs, "A multigrid tutorial" , SIAM (1987)
[a3]	R.P. Fedorenko, "A relaxation method for solving elliptic difference equations" USSR Comp. Math. Math. Physics , 1 : 5 (1962) pp. 1092–1096 Zh. Vychisl. Mat. i Mat. Fiz. , 1 : 5 (1961) pp. 922–927
[a4]	G.E. Forsythe, W.R. Wasow, "Finite difference methods for partial differential equations" , Wiley (1960)
[a5]	P.R. Garabedian, "Partial differential equations" , Wiley (1964)
[a6]	I. Gladwell (ed.) R. Wait (ed.) , A survey of numerical methods for partial differential equations , Clarendon Press (1979)
[a7]	W. Hackbush, "Multigrid methods and applications" , Springer (1985)
[a8]	A.R. Mitchell, D.F. Griffiths, "The finite difference method in partial differential equations" , Wiley (1980)
[a9]	R.D. Richtmeyer, K.W. Morton, "Difference methods for initial value problems" , Wiley (1967)
[a10]	G.D. Smith, "Numerical solution of partial differential equations" , Oxford Univ. Press (1977)
[a11]	R.E. Bank, D.J. Rose, "Marching algorithms for elliptic boundary value problems" SIAM J. Numer. Anal. , 14 (1977) pp. 792–829
[a12]	E.P. Doolan, J.J.H. Miller, W.H.A. Schilders, "Uniform numerical methods for problems with initial and boundary layers" , Boole Press (1980)
[a13]	G. Birkhoff, R.E. Lynch, "Numerical solution of elliptic problems" , SIAM (1984)