Namespaces
Variants
Actions

Difference between revisions of "Discretization method"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
Line 1: Line 1:
 +
<!--
 +
d0331901.png
 +
$#A+1 = 55 n = 1
 +
$#C+1 = 55 : ~/encyclopedia/old_files/data/D033/D.0303190 Discretization method,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''splitting method''
 
''splitting method''
  
A grid method for solving non-stationary problems with one or more spatial variables, in which the passage from a given time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331901.png" /> to the next time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331902.png" /> is realized at the expense of a sequential solution of the grid analogues of related non-stationary problems with a smaller number of spatial variables (see [[#References|[1]]]–[[#References|[7]]]). One can often find methods in this class such that: 1) the whole passage from a grid layer at a moment of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331903.png" /> to a new grid layer at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331904.png" /> is simple enough to be realized using <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331905.png" /> arithmetical operations, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331906.png" /> is the number of nodes in the spatial grid; 2) absolute stability of the method is guaranteed; and 3) an acceptable precision of the method is guaranteed (existence of some form of approximation). Discretization methods are used fairly extensively in the practical solution of higher-dimensional problems of mathematical physics, such as those involving linear and non-linear systems of parabolic, hyperbolic or mixed type (see [[#References|[1]]]–[[#References|[9]]]).
+
A grid method for solving non-stationary problems with one or more spatial variables, in which the passage from a given time $  t _ {n} $
 +
to the next time $  t _ {n + 1 }  = t _ {n} + \tau $
 +
is realized at the expense of a sequential solution of the grid analogues of related non-stationary problems with a smaller number of spatial variables (see [[#References|[1]]]–[[#References|[7]]]). One can often find methods in this class such that: 1) the whole passage from a grid layer at a moment of time $  t _ {n} $
 +
to a new grid layer at $  t = t _ {n + 1 }  $
 +
is simple enough to be realized using $  O ( N) $
 +
arithmetical operations, where $  N $
 +
is the number of nodes in the spatial grid; 2) absolute stability of the method is guaranteed; and 3) an acceptable precision of the method is guaranteed (existence of some form of approximation). Discretization methods are used fairly extensively in the practical solution of higher-dimensional problems of mathematical physics, such as those involving linear and non-linear systems of parabolic, hyperbolic or mixed type (see [[#References|[1]]]–[[#References|[9]]]).
  
For a problem with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331907.png" /> spatial variables, the passage from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331908.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d0331909.png" /> by a discretization method can usually be carried out using <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319010.png" /> auxiliary (fractional) steps:
+
For a problem with $  p $
 +
spatial variables, the passage from $  t _ {n} $
 +
to $  t _ {n + 1 }  $
 +
by a discretization method can usually be carried out using $  p $
 +
auxiliary (fractional) steps:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319011.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$ \tag{1 }
 +
A _ {s}  ^ {(} n)
 +
u ^ {n + s/p }  = \
 +
B _ {s} ^ { ( n) }
 +
( u  ^ {n} , u ^ {n + 1/p } \dots u ^ {n + ( s - 1)/p } ),
 +
$$
  
 
where
 
where
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319012.png" /></td> </tr></table>
+
$$
 +
u  ^ {n}  \equiv \
 +
u ( t _ {n} ),\ \
 +
u ( t _ {n + 1 }  )  \equiv  u ^ {n + p/p } ,
 +
$$
  
<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319013.png" /> is the matrix corresponding to the difference approximation of a certain differential operator, containing only derivatives with respect to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319014.png" /> (a one-dimensional differential operator), and the right-hand side of (1) can be easily calculated. By a corresponding enumeration of the unknowns, connected with the choice of the direction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319015.png" />, the matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319016.png" /> usually become diagonal and the solution of (1) for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319017.png" /> reduces to the multiple solution of one-dimensional difference systems in the direction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319018.png" />. Hence a discretization method is often called either an alternating-directing method (see also [[Variable-directions method|Variable-directions method]]) or a method of fractional steps (cf. [[Fractional steps, method of|Fractional steps, method of]]).
+
$  A _ {s}  ^ {(} n) $
 +
is the matrix corresponding to the difference approximation of a certain differential operator, containing only derivatives with respect to $  x _ {s} $(
 +
a one-dimensional differential operator), and the right-hand side of (1) can be easily calculated. By a corresponding enumeration of the unknowns, connected with the choice of the direction $  x _ {s} $,  
 +
the matrices $  A _ {s}  ^ {(} n) $
 +
usually become diagonal and the solution of (1) for every $  s $
 +
reduces to the multiple solution of one-dimensional difference systems in the direction $  x _ {s} $.  
 +
Hence a discretization method is often called either an alternating-directing method (see also [[Variable-directions method|Variable-directions method]]) or a method of fractional steps (cf. [[Fractional steps, method of|Fractional steps, method of]]).
  
 
As a typical example, consider the equation
 
As a typical example, consider the equation
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319019.png" /></td> </tr></table>
+
$$
 +
 
 +
\frac{\partial  u }{\partial  t }
 +
  = \
 +
 
 +
\frac{\partial  ^ {2} u }{\partial  x _ {1}  ^ {2} }
 +
+
 +
 
 +
\frac{\partial  ^ {2} u }{\partial  x _ {2}  ^ {2} }
 +
+ f,\ \
 +
( x _ {1} , x _ {2} ) \in \Omega ,
 +
$$
 +
 
 +
with initial condition  $  u \mid  _ {t = 0 }  = \phi ( x _ {1} , x _ {2} ) $
 +
and boundary condition  $  u \mid  _  \Gamma  = \psi ( x _ {1} , x _ {2} , t) $,
 +
where  $  \Omega \equiv ( 0, 1) \times ( 0, 1) $
 +
and  $  \Gamma $
 +
is the boundary of  $  \Omega $.
 +
The following method can be used on a square grid with step  $  h $:
 +
 
 +
$$
 +
\left .
  
with initial condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319020.png" /> and boundary condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319021.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319023.png" /> is the boundary of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319024.png" />. The following method can be used on a square grid with step <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319025.png" />:
+
\begin{array}{c}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319026.png" /></td> </tr></table>
+
\frac{u _ {i} ^ {n + 1/2 } - u _ {i}  ^ {n} }{\tau /2 }
 +
+ [ \Lambda _ {1} ( \sigma u ^ {n + 1/2 } +
 +
( 1 - \sigma ) u  ^ {n} )] _ {i}  = \
 +
f _ {i} ^ { n + 1/2 } ,\ \
 +
\overline{x}\; _ {i} \in \Omega _ {n} ; \\
 +
u _ {i} ^ {n + 1/2 }  = \
 +
\psi _ {i} ^ {n + 1/2 } \ \
 +
\textrm{ and } \ \
 +
u _ {i} ^ {n + 1 }  = \
 +
\psi _ {i} ^ {n + 1 } \ \
 +
\textrm{ for }  \overline{x}\; _ {i} \in \Gamma ; \\
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319027.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319029.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319031.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319032.png" /> are the simplest difference approximations to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319034.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319035.png" /> is the set of all interior nodes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319036.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319037.png" />.
+
\frac{u _ {i} ^ {n + 1 } - u _ {i} ^ {n + 1/2 } }{\tau /2 }
 +
+ [ \Lambda _ {2} ( \sigma u ^ {n + 1 } +
 +
( 1 - \sigma ) u ^ {n + 1/2 } )] _ {i}  = \
 +
f _ {i} ^ { n + 1/2 } ,\  \\
 +
\  \  \  \  \overline{x}\; _ {i} \in \Omega _ {n} , \\
 +
\end{array}
  
There are two alternative approaches to the theory of discretization methods. In one of them the intermediate steps do not differ essentially from integral steps, and the difference equations in fractional steps and the boundary conditions for them, being similar to those in method , are carried out in the same way. One can thus expect that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319039.png" /> will serve as approximations to the solution of the original problem at the moments of time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319040.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319041.png" />. This approach is based on the use of the notions of a splitting scheme and a total approximation (see [[#References|[2]]]). Schemes of such a type are often called locally one-dimensional schemes or additive schemes. They can also be treated as ordinary difference schemes for a certain equation with strongly-oscillating coefficients, whose solution must be close to that of the original problem (see [[#References|[1]]]–[[#References|[4]]]). The merits of this approach are in its simplicity and generality. For example, generalizations of method
+
\right \}
 +
$$
  
also exist in the case of curvilinear domains <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319042.png" /> and for more general problems. The level of precision of the methods obtained when following this course is usually not very high. There are well-known and sometimes successfully applied variants of discretization methods in which the splitting takes place with respect to the physical processes rather than the spatial variables (see [[#References|[5]]], [[#References|[9]]]).
+
where  $  i \equiv ( i _ {1} , i _ {2} ) $,
 +
$  \overline{x}\; _ {i} \equiv ( i _ {i} h, i _ {2} h) $,
 +
$  u _ {i}  ^ {n} \equiv u ( n \tau , \overline{x}\; _ {i} ) $,
 +
$  \psi _ {i} ^ {n + 1/2 } \equiv \psi (( n + 1/2) \tau , \overline{x}\; _ {i} ) $,
 +
$  \Lambda _ {1} $
 +
and  $  \Lambda _ {2} $
 +
are the simplest difference approximations to  $  {\partial  ^ {2} } / {\partial  x _ {1}  ^ {2} } $
 +
and  $  {\partial  ^ {2} } / {\partial  x _ {2}  ^ {2} } $,
 +
$  \Omega _ {n} $
 +
is the set of all interior nodes  $  \overline{x}\; _ {i} $,
 +
and  $  \sigma \geq  1/2 $.
 +
 
 +
There are two alternative approaches to the theory of discretization methods. In one of them the intermediate steps do not differ essentially from integral steps, and the difference equations in fractional steps and the boundary conditions for them, being similar to those in method , are carried out in the same way. One can thus expect that  $  u  ^ {n} $
 +
and  $  u ^ {n + 1/2 } $
 +
will serve as approximations to the solution of the original problem at the moments of time  $  t _ {n} $
 +
and  $  t _ {n + 1/2 }  = t _ {n} + \tau /2 $.
 +
This approach is based on the use of the notions of a splitting scheme and a total approximation (see [[#References|[2]]]). Schemes of such a type are often called locally one-dimensional schemes or additive schemes. They can also be treated as ordinary difference schemes for a certain equation with strongly-oscillating coefficients, whose solution must be close to that of the original problem (see [[#References|[1]]]–[[#References|[4]]]). The merits of this approach are in its simplicity and generality. For example, generalizations of method
 +
 
 +
also exist in the case of curvilinear domains  $  \Omega $
 +
and for more general problems. The level of precision of the methods obtained when following this course is usually not very high. There are well-known and sometimes successfully applied variants of discretization methods in which the splitting takes place with respect to the physical processes rather than the spatial variables (see [[#References|[5]]], [[#References|[9]]]).
  
 
A second approach to the plan of analysis of stability and convergence dispenses with the need to consider fractional steps. Both the difference scheme itself and the approximation are treated in the traditional way. The unusualness of the difference scheme is to be found only at a higher level of the scheme, where there appears an unusual difference operator. For example, instead of method
 
A second approach to the plan of analysis of stability and convergence dispenses with the need to consider fractional steps. Both the difference scheme itself and the approximation are treated in the traditional way. The unusualness of the difference scheme is to be found only at a higher level of the scheme, where there appears an unusual difference operator. For example, instead of method
Line 31: Line 124:
 
one considers the method
 
one considers the method
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319043.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3)</td></tr></table>
+
$$ \tag{3 }
 +
\left ( A \left (
 +
{
 +
\frac{u ^ {n + 1 } - u  ^ {n} } \tau
 +
} \right ) \right ) _ {i} +
 +
( \Lambda _ {1} u  ^ {n} ) _ {i} +
 +
( \Lambda _ {2} u  ^ {n} ) _ {i}  = \
 +
f _ {i} ^ { n + 1/2 } ,
 +
$$
 +
 
 +
$$
 +
\overline{x}\; _ {i}  \in  \Omega _ {n} ,
 +
$$
 +
 
 +
$$
 +
u _ {i}  ^ {n}  = \psi _ {i}  ^ {n} \  \textrm{ for } \  \overline{x}\; _ {i} \in \Gamma ,
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319044.png" /></td> </tr></table>
+
where  $  A \equiv ( E + \sigma \tau \Lambda _ {1} ) ( E + \sigma \tau \Lambda _ {1} ) $
 +
and  $  E $
 +
is the identity operator. Such operators  $  A $
 +
are usually called split or factorized operators. The fractional steps are only connected with the method for solving the resulting system, and for one and the same scheme (3) one can introduce various methods, with boundary conditions chosen accordingly. Schemes of type (3) can be treated as ordinary weighted schemes for an  $  \epsilon $-
 +
equation such as
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319045.png" /></td> </tr></table>
+
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319046.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319047.png" /> is the identity operator. Such operators <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319048.png" /> are usually called split or factorized operators. The fractional steps are only connected with the method for solving the resulting system, and for one and the same scheme (3) one can introduce various methods, with boundary conditions chosen accordingly. Schemes of type (3) can be treated as ordinary weighted schemes for an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319049.png" />-equation such as
+
\frac{\partial  u }{\partial  t }
 +
-
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319050.png" /></td> </tr></table>
+
\frac{\partial  ^ {2} u }{\partial  x _ {1}  ^ {2} }
 +
-
  
where the solutions differ from the solution of the original problem by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319051.png" /> (see [[#References|[4]]]). In the case of a domain <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319052.png" /> made up of rectangles, the matrices of the systems arising in methods of type (3) cannot be written as a product of  "one-dimensional"  matrices. Nevertheless, solutions of similar systems can be found using <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319053.png" /> arithmetical operations (see [[#References|[4]]]), and operators of this type are called generalized split operators. In investigating the stability and convergence of schemes with split and generalized split operators, a major role is played by the method of energy inequalities (see [[#References|[2]]], [[#References|[4]]], [[#References|[6]]]–[[#References|[8]]]).
+
\frac{\partial  ^ {2} u }{\partial  x _ {2}  ^ {2} }
 +
+
 +
\epsilon
 +
 
 +
\frac{\partial  ^ {5} u }{\partial  x _ {1}  ^ {2}
 +
\partial  x _ {2}  ^ {2} \partial  t }
 +
  =  f,\ \
 +
\epsilon > 0,
 +
$$
 +
 
 +
where the solutions differ from the solution of the original problem by $  O ( \epsilon ) $(
 +
see [[#References|[4]]]). In the case of a domain $  \Omega $
 +
made up of rectangles, the matrices of the systems arising in methods of type (3) cannot be written as a product of  "one-dimensional"  matrices. Nevertheless, solutions of similar systems can be found using $  O ( N) $
 +
arithmetical operations (see [[#References|[4]]]), and operators of this type are called generalized split operators. In investigating the stability and convergence of schemes with split and generalized split operators, a major role is played by the method of energy inequalities (see [[#References|[2]]], [[#References|[4]]], [[#References|[6]]]–[[#References|[8]]]).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G.I. Marchuk,  "Methods of numerical mathematics" , Springer  (1975)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Samarskii,  "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D.  (1984)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.N. Yanenko,  "The method of fractional steps; the solution of problems of mathematical physics in several variables" , Springer  (1971)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.G. D'yakonov,  "On the stability of difference schemes for some nonstationary problems"  J. Miller (ed.) , ''Topics in numerical analysis'' , Acad. Press  (1973)  pp. 63–87  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  V.M. Kovenya,  N.N. Yanenko,  "Discretization methods in problems of gas dynamics" , Novosibirsk  (1981)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  A.R. Mitchell,  "Computational methods in partial differential equations" , Wiley  (1969)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  G. Fairweather,  "Finite element Galerkin methods for differential equations" , M. Dekker  (1978)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.A. Zlotnik,  "The rate of convergence of the projection-difference scheme with a splitting operator for parabolic equations"  ''USSR Comput. Math. Math. Phys.'' , '''20''' :  2  (1980)  pp. 155–164  ''Zh. Vychisl. Mat. Mat. Fiz.'' , '''20''' :  2  (1980)  pp. 422–432</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  R. Glowinski,  "On a new preconditioner for the Stokes problem"  ''Math. Aplic. Comp.'' , '''6''' :  2  (1987)  pp. 123–140</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G.I. Marchuk,  "Methods of numerical mathematics" , Springer  (1975)  (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  A.A. Samarskii,  "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D.  (1984)  (Translated from Russian)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  N.N. Yanenko,  "The method of fractional steps; the solution of problems of mathematical physics in several variables" , Springer  (1971)  (Translated from Russian)</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  E.G. D'yakonov,  "On the stability of difference schemes for some nonstationary problems"  J. Miller (ed.) , ''Topics in numerical analysis'' , Acad. Press  (1973)  pp. 63–87  (Translated from Russian)</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  V.M. Kovenya,  N.N. Yanenko,  "Discretization methods in problems of gas dynamics" , Novosibirsk  (1981)  (In Russian)</TD></TR><TR><TD valign="top">[6]</TD> <TD valign="top">  A.R. Mitchell,  "Computational methods in partial differential equations" , Wiley  (1969)</TD></TR><TR><TD valign="top">[7]</TD> <TD valign="top">  G. Fairweather,  "Finite element Galerkin methods for differential equations" , M. Dekker  (1978)</TD></TR><TR><TD valign="top">[8]</TD> <TD valign="top">  A.A. Zlotnik,  "The rate of convergence of the projection-difference scheme with a splitting operator for parabolic equations"  ''USSR Comput. Math. Math. Phys.'' , '''20''' :  2  (1980)  pp. 155–164  ''Zh. Vychisl. Mat. Mat. Fiz.'' , '''20''' :  2  (1980)  pp. 422–432</TD></TR><TR><TD valign="top">[9]</TD> <TD valign="top">  R. Glowinski,  "On a new preconditioner for the Stokes problem"  ''Math. Aplic. Comp.'' , '''6''' :  2  (1987)  pp. 123–140</TD></TR></table>
 
 
  
 
====Comments====
 
====Comments====
In the Western literature, the terminology  "discretization method"  is used for constructing difference schemes (cf. [[Difference scheme|Difference scheme]]) both for boundary value problems and for initial-boundary value problems. I.e. for a method of replacing a differential equation by a [[Difference equation|difference equation]]. In this article, it is used in the restrictive sense of the time discretization of initial-boundary value problems by splitting methods. Furthermore, in the English literature, fractional steps and locally one-dimensional methods (cf. also [[#References|[a7]]]) refer to the discretization methods originally proposed by Yanenko, Samarskii, D'yakonov<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319054.png" /> while the alternating-direction implicit methods refer to methods proposed by Peaceman, Rachford, Douglas<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319055.png" />. A further family of splitting methods are the so-called hopscotch methods advocated by Courlay [[#References|[a4]]].
+
In the Western literature, the terminology  "discretization method"  is used for constructing difference schemes (cf. [[Difference scheme|Difference scheme]]) both for boundary value problems and for initial-boundary value problems. I.e. for a method of replacing a differential equation by a [[Difference equation|difference equation]]. In this article, it is used in the restrictive sense of the time discretization of initial-boundary value problems by splitting methods. Furthermore, in the English literature, fractional steps and locally one-dimensional methods (cf. also [[#References|[a7]]]) refer to the discretization methods originally proposed by Yanenko, Samarskii, D'yakonov $  \dots $
 +
while the alternating-direction implicit methods refer to methods proposed by Peaceman, Rachford, Douglas $  ,\dots $.  
 +
A further family of splitting methods are the so-called hopscotch methods advocated by Courlay [[#References|[a4]]].
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Douglas,  "On the numerical integration of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319056.png" /> by implicit methods"  ''J. Soc. Ind. Appl. Math.'' , '''3'''  (1955)  pp. 42–65</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Douglas,  H.H. Rachford,  "On the numerical solution of heat conduction problems in two and three space variables"  ''Trans. Amer. Math. Soc.'' , '''82'''  (1956)  pp. 421–439</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.E. Forsythe,  W.R. Wasow,  "Finite difference methods for partial differential equations" , Wiley  (1960)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.R. Gourlay,  "Hopscotch, a fast second-order partial differential equation solver"  ''J. Inst. Math. Appl.'' , '''6'''  (1970)  pp. 375–390</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A.R. Mitchell,  D.F. Griffiths,  "The finite difference method in partial differential equations" , Wiley  (1980)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D.W. Paeceman,  H.H. Rachford,  "The numerical solution of parabolic and elliptic differential equations"  ''J. Soc. Indust. Appl. Math.'' , '''3'''  (1955)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  W.F. Ames,  "Numerical methods for partial differential equations" , Acad. Press  (1977)</TD></TR></table>
 
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Douglas,  "On the numerical integration of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d033/d033190/d03319056.png" /> by implicit methods"  ''J. Soc. Ind. Appl. Math.'' , '''3'''  (1955)  pp. 42–65</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  J. Douglas,  H.H. Rachford,  "On the numerical solution of heat conduction problems in two and three space variables"  ''Trans. Amer. Math. Soc.'' , '''82'''  (1956)  pp. 421–439</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G.E. Forsythe,  W.R. Wasow,  "Finite difference methods for partial differential equations" , Wiley  (1960)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  A.R. Gourlay,  "Hopscotch, a fast second-order partial differential equation solver"  ''J. Inst. Math. Appl.'' , '''6'''  (1970)  pp. 375–390</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A.R. Mitchell,  D.F. Griffiths,  "The finite difference method in partial differential equations" , Wiley  (1980)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  D.W. Paeceman,  H.H. Rachford,  "The numerical solution of parabolic and elliptic differential equations"  ''J. Soc. Indust. Appl. Math.'' , '''3'''  (1955)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  W.F. Ames,  "Numerical methods for partial differential equations" , Acad. Press  (1977)</TD></TR></table>

Revision as of 19:36, 5 June 2020


splitting method

A grid method for solving non-stationary problems with one or more spatial variables, in which the passage from a given time $ t _ {n} $ to the next time $ t _ {n + 1 } = t _ {n} + \tau $ is realized at the expense of a sequential solution of the grid analogues of related non-stationary problems with a smaller number of spatial variables (see [1][7]). One can often find methods in this class such that: 1) the whole passage from a grid layer at a moment of time $ t _ {n} $ to a new grid layer at $ t = t _ {n + 1 } $ is simple enough to be realized using $ O ( N) $ arithmetical operations, where $ N $ is the number of nodes in the spatial grid; 2) absolute stability of the method is guaranteed; and 3) an acceptable precision of the method is guaranteed (existence of some form of approximation). Discretization methods are used fairly extensively in the practical solution of higher-dimensional problems of mathematical physics, such as those involving linear and non-linear systems of parabolic, hyperbolic or mixed type (see [1][9]).

For a problem with $ p $ spatial variables, the passage from $ t _ {n} $ to $ t _ {n + 1 } $ by a discretization method can usually be carried out using $ p $ auxiliary (fractional) steps:

$$ \tag{1 } A _ {s} ^ {(} n) u ^ {n + s/p } = \ B _ {s} ^ { ( n) } ( u ^ {n} , u ^ {n + 1/p } \dots u ^ {n + ( s - 1)/p } ), $$

where

$$ u ^ {n} \equiv \ u ( t _ {n} ),\ \ u ( t _ {n + 1 } ) \equiv u ^ {n + p/p } , $$

$ A _ {s} ^ {(} n) $ is the matrix corresponding to the difference approximation of a certain differential operator, containing only derivatives with respect to $ x _ {s} $( a one-dimensional differential operator), and the right-hand side of (1) can be easily calculated. By a corresponding enumeration of the unknowns, connected with the choice of the direction $ x _ {s} $, the matrices $ A _ {s} ^ {(} n) $ usually become diagonal and the solution of (1) for every $ s $ reduces to the multiple solution of one-dimensional difference systems in the direction $ x _ {s} $. Hence a discretization method is often called either an alternating-directing method (see also Variable-directions method) or a method of fractional steps (cf. Fractional steps, method of).

As a typical example, consider the equation

$$ \frac{\partial u }{\partial t } = \ \frac{\partial ^ {2} u }{\partial x _ {1} ^ {2} } + \frac{\partial ^ {2} u }{\partial x _ {2} ^ {2} } + f,\ \ ( x _ {1} , x _ {2} ) \in \Omega , $$

with initial condition $ u \mid _ {t = 0 } = \phi ( x _ {1} , x _ {2} ) $ and boundary condition $ u \mid _ \Gamma = \psi ( x _ {1} , x _ {2} , t) $, where $ \Omega \equiv ( 0, 1) \times ( 0, 1) $ and $ \Gamma $ is the boundary of $ \Omega $. The following method can be used on a square grid with step $ h $:

$$ \left . \begin{array}{c} \frac{u _ {i} ^ {n + 1/2 } - u _ {i} ^ {n} }{\tau /2 } + [ \Lambda _ {1} ( \sigma u ^ {n + 1/2 } + ( 1 - \sigma ) u ^ {n} )] _ {i} = \ f _ {i} ^ { n + 1/2 } ,\ \ \overline{x}\; _ {i} \in \Omega _ {n} ; \\ u _ {i} ^ {n + 1/2 } = \ \psi _ {i} ^ {n + 1/2 } \ \ \textrm{ and } \ \ u _ {i} ^ {n + 1 } = \ \psi _ {i} ^ {n + 1 } \ \ \textrm{ for } \overline{x}\; _ {i} \in \Gamma ; \\ \frac{u _ {i} ^ {n + 1 } - u _ {i} ^ {n + 1/2 } }{\tau /2 } + [ \Lambda _ {2} ( \sigma u ^ {n + 1 } + ( 1 - \sigma ) u ^ {n + 1/2 } )] _ {i} = \ f _ {i} ^ { n + 1/2 } ,\ \\ \ \ \ \ \overline{x}\; _ {i} \in \Omega _ {n} , \\ \end{array} \right \} $$

where $ i \equiv ( i _ {1} , i _ {2} ) $, $ \overline{x}\; _ {i} \equiv ( i _ {i} h, i _ {2} h) $, $ u _ {i} ^ {n} \equiv u ( n \tau , \overline{x}\; _ {i} ) $, $ \psi _ {i} ^ {n + 1/2 } \equiv \psi (( n + 1/2) \tau , \overline{x}\; _ {i} ) $, $ \Lambda _ {1} $ and $ \Lambda _ {2} $ are the simplest difference approximations to $ {\partial ^ {2} } / {\partial x _ {1} ^ {2} } $ and $ {\partial ^ {2} } / {\partial x _ {2} ^ {2} } $, $ \Omega _ {n} $ is the set of all interior nodes $ \overline{x}\; _ {i} $, and $ \sigma \geq 1/2 $.

There are two alternative approaches to the theory of discretization methods. In one of them the intermediate steps do not differ essentially from integral steps, and the difference equations in fractional steps and the boundary conditions for them, being similar to those in method , are carried out in the same way. One can thus expect that $ u ^ {n} $ and $ u ^ {n + 1/2 } $ will serve as approximations to the solution of the original problem at the moments of time $ t _ {n} $ and $ t _ {n + 1/2 } = t _ {n} + \tau /2 $. This approach is based on the use of the notions of a splitting scheme and a total approximation (see [2]). Schemes of such a type are often called locally one-dimensional schemes or additive schemes. They can also be treated as ordinary difference schemes for a certain equation with strongly-oscillating coefficients, whose solution must be close to that of the original problem (see [1][4]). The merits of this approach are in its simplicity and generality. For example, generalizations of method

also exist in the case of curvilinear domains $ \Omega $ and for more general problems. The level of precision of the methods obtained when following this course is usually not very high. There are well-known and sometimes successfully applied variants of discretization methods in which the splitting takes place with respect to the physical processes rather than the spatial variables (see [5], [9]).

A second approach to the plan of analysis of stability and convergence dispenses with the need to consider fractional steps. Both the difference scheme itself and the approximation are treated in the traditional way. The unusualness of the difference scheme is to be found only at a higher level of the scheme, where there appears an unusual difference operator. For example, instead of method

one considers the method

$$ \tag{3 } \left ( A \left ( { \frac{u ^ {n + 1 } - u ^ {n} } \tau } \right ) \right ) _ {i} + ( \Lambda _ {1} u ^ {n} ) _ {i} + ( \Lambda _ {2} u ^ {n} ) _ {i} = \ f _ {i} ^ { n + 1/2 } , $$

$$ \overline{x}\; _ {i} \in \Omega _ {n} , $$

$$ u _ {i} ^ {n} = \psi _ {i} ^ {n} \ \textrm{ for } \ \overline{x}\; _ {i} \in \Gamma , $$

where $ A \equiv ( E + \sigma \tau \Lambda _ {1} ) ( E + \sigma \tau \Lambda _ {1} ) $ and $ E $ is the identity operator. Such operators $ A $ are usually called split or factorized operators. The fractional steps are only connected with the method for solving the resulting system, and for one and the same scheme (3) one can introduce various methods, with boundary conditions chosen accordingly. Schemes of type (3) can be treated as ordinary weighted schemes for an $ \epsilon $- equation such as

$$ \frac{\partial u }{\partial t } - \frac{\partial ^ {2} u }{\partial x _ {1} ^ {2} } - \frac{\partial ^ {2} u }{\partial x _ {2} ^ {2} } + \epsilon \frac{\partial ^ {5} u }{\partial x _ {1} ^ {2} \partial x _ {2} ^ {2} \partial t } = f,\ \ \epsilon > 0, $$

where the solutions differ from the solution of the original problem by $ O ( \epsilon ) $( see [4]). In the case of a domain $ \Omega $ made up of rectangles, the matrices of the systems arising in methods of type (3) cannot be written as a product of "one-dimensional" matrices. Nevertheless, solutions of similar systems can be found using $ O ( N) $ arithmetical operations (see [4]), and operators of this type are called generalized split operators. In investigating the stability and convergence of schemes with split and generalized split operators, a major role is played by the method of energy inequalities (see [2], [4], [6][8]).

References

[1] G.I. Marchuk, "Methods of numerical mathematics" , Springer (1975) (Translated from Russian)
[2] A.A. Samarskii, "Theorie der Differenzverfahren" , Akad. Verlagsgesell. Geest u. Portig K.-D. (1984) (Translated from Russian)
[3] N.N. Yanenko, "The method of fractional steps; the solution of problems of mathematical physics in several variables" , Springer (1971) (Translated from Russian)
[4] E.G. D'yakonov, "On the stability of difference schemes for some nonstationary problems" J. Miller (ed.) , Topics in numerical analysis , Acad. Press (1973) pp. 63–87 (Translated from Russian)
[5] V.M. Kovenya, N.N. Yanenko, "Discretization methods in problems of gas dynamics" , Novosibirsk (1981) (In Russian)
[6] A.R. Mitchell, "Computational methods in partial differential equations" , Wiley (1969)
[7] G. Fairweather, "Finite element Galerkin methods for differential equations" , M. Dekker (1978)
[8] A.A. Zlotnik, "The rate of convergence of the projection-difference scheme with a splitting operator for parabolic equations" USSR Comput. Math. Math. Phys. , 20 : 2 (1980) pp. 155–164 Zh. Vychisl. Mat. Mat. Fiz. , 20 : 2 (1980) pp. 422–432
[9] R. Glowinski, "On a new preconditioner for the Stokes problem" Math. Aplic. Comp. , 6 : 2 (1987) pp. 123–140

Comments

In the Western literature, the terminology "discretization method" is used for constructing difference schemes (cf. Difference scheme) both for boundary value problems and for initial-boundary value problems. I.e. for a method of replacing a differential equation by a difference equation. In this article, it is used in the restrictive sense of the time discretization of initial-boundary value problems by splitting methods. Furthermore, in the English literature, fractional steps and locally one-dimensional methods (cf. also [a7]) refer to the discretization methods originally proposed by Yanenko, Samarskii, D'yakonov $ \dots $ while the alternating-direction implicit methods refer to methods proposed by Peaceman, Rachford, Douglas $ ,\dots $. A further family of splitting methods are the so-called hopscotch methods advocated by Courlay [a4].

References

[a1] J. Douglas, "On the numerical integration of by implicit methods" J. Soc. Ind. Appl. Math. , 3 (1955) pp. 42–65
[a2] J. Douglas, H.H. Rachford, "On the numerical solution of heat conduction problems in two and three space variables" Trans. Amer. Math. Soc. , 82 (1956) pp. 421–439
[a3] G.E. Forsythe, W.R. Wasow, "Finite difference methods for partial differential equations" , Wiley (1960)
[a4] A.R. Gourlay, "Hopscotch, a fast second-order partial differential equation solver" J. Inst. Math. Appl. , 6 (1970) pp. 375–390
[a5] A.R. Mitchell, D.F. Griffiths, "The finite difference method in partial differential equations" , Wiley (1980)
[a6] D.W. Paeceman, H.H. Rachford, "The numerical solution of parabolic and elliptic differential equations" J. Soc. Indust. Appl. Math. , 3 (1955)
[a7] W.F. Ames, "Numerical methods for partial differential equations" , Acad. Press (1977)
How to Cite This Entry:
Discretization method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Discretization_method&oldid=46739
This article was adapted from an original article by E.G. D'yakonov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article