Chemistry Reference
In-Depth Information
behavior gets worse as the grid spacing decreases. To address why this hap-
pens, we will look at the solution of the Laplace equation [Poisson equation
with
0], since it illustrates the important features of the slowing down.
The analysis will be performed for the weighted Jacobi method discussed
above.
The update or relaxation Eq. [25] can be written as a matrix equation.
We are interested in the mathematical properties of the update matrix, so
we will calculate the eigenvalues of that matrix. Let the update matrix act
upon a plane wave with wavevector
k.
Then our eigenvalue equation is
r
ð
r
Þ¼
2
e
ik
ð
x
h
Þ
þð
þ
2
e
ik
ð
x
þ
h
Þ
¼
l
k
e
ikx
e
ikx
1
o
Þ
½
28
where
l
k
is the eigenvalue of
the update matrix. Using the relation
e
ix
¼
cos
x
þ
i
sin
x
, and a trigonometric identity, we find
sin
2
kh
2
l
k
¼
1
2
o
½
29
We can imagine that if the eigenvalues of this matrix exceed one in magnitude,
the iterations will numerically ''explode.'' This implies that
1 for the
weighted Jacobi method. When you write your first relaxation code, it is
easy to test this assertion, and indeed it is true! It turns out that, for the
SOR algorithm, the stability criterion is
o
2. This corresponds effectively
to a larger ''time step'' during the iterations and can lead to greater efficiency.
An added bonus of Gauss-Seidel and SOR methods is that, since the updated
values are used rather than the previous values, we need not store an extra vec-
tor for the old and new function values. Thus, the memory requirements are
reduced.
105
For small
k
, we can expand the sin function to give
o
k
2
h
2
2
o
l
k
1
½
30
Small
k
corresponds to a long-wavelength mode, and the above approxima-
tion tells us that the eigenvalues corresponding to the longest wavelength
modes in the errors approach 1 as the grid spacing is reduced toward
zero. This means that errors with the longer wavelengths do not get removed
efficiently. (The error reduction efficiency is related to the eigenvalue raised
to a power of the number of iterations.) This, in a nutshell, is the origin of
''critical slowing down,'' which motivated the development of multigrid
(MG) methods.
105
