644 Methods for Solving Grid Equationsexample, for any grid with steps h along all the directions x 1 ,x 2 , ... ,xP
(h 1 = h 2 = · · · = hp = h) the amount of nodal points is N = O(h-P),
where p is the total number of observations. In the two-dimensional and
three-clin1ensional cases 1! ~ 104 - 106 , for exa1nple, for h = 1/100. More
specifically, such sparse n1atrices are of the special band structure and the
characteristic rations between their greatest and the s1nallest eigenvalues
are high-order quantities(~ 103 - 104 of order O(h-^2 )).
Numerical solution of elliptic grid equations necessitates, in view of
their peculiarities, creating special economical algorithms, because direct
economical methods are applicable only in some narrow classes of grid equa-
tions. We will elaborate on this later.
vVhen solving difference boundary-value problems for Poisson's equa-
tion in rectangular, angular, cylindrical and spherical systems of coordi-
nates direct economical methods are widely used that are known to us as
the decomposition method and the method of separation of variables. The
calculations in both methods for two-dimensional problems require Q arith-
1netic operations, Q = O(IV^2 log 2 N), where N is the number of the grid
nodes along one of the directions.
As a matter of fact, the first 1nethocl is some modification of Gaussian
eli1nination relating to the odd-even elimination with the accon1panying
factorization, the second one is mostly based on the algorithm of the fast
Fourier transfonn. The third 1nethod of the 1natrix elin1ination seems to
offer more advantages in the domains of rather con1plicatecl configurations,
but the work during the course of the matrix elimination is clone with
Q = O(N^4 ) arithmetic operations and the extra storage in connection with
en1erging intermediate values.
Iterative 1nethocls of successive approxi1nation are in common usage
for rather complicated cases of arbitrary domains, variable coefficients, etc.
Throughout the entire section, the Dirichlet problem for Poisson's equation
is adopted as a model one in the rectangle G = {O < xo: < (» a = 1, 2}
with the boundary r:
(1)
a^2 tt a^2 tt
ti. tl = a x~ 0 + a x 2 = -f ( x) ,
1 2ulr = μ(x),
and a rectangular grid in G with steps h 1 and h 2 is taken to be