View source for Discretization method

<!--
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''

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  $  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|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

$$ 

\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 [[#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

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 [[#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====
<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====
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====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  J. Douglas,   "On the numerical integration of $u_{xx}+u_{yy}=u_t$ 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>