Database Reference
In-Depth Information
Let us remain a little longer with the last case of the efficient solution of
differential equations and go into a little more detail, since this will help us for
the Bellman equation.
Let us consider the original approach, the
multigrid
method. It was initially
developed by the Soviet mathematicians Fedorenko [Fed64] and Bakhvalov
[Bakh66], and main contributions are made by Achi Brandt [Bra77] and Wolfgang
Hackbusch [Ha85].
After the discretization of the differential equation has been performed, the FEM
approach leads via nodal bases to the solution of the equation system
Kx ¼ f
,
ð
6
:
3
Þ
where
K
is what we call the stiffness matrix,
f
is the load vector, and
x
is the solution
vector for our coefficients
c
i
in the nodal basis. Let
IT
be a simple iteration method
like Richardson or Gauss-Seidel. For the solution of (
6.3
), it requires a lot of
iterations and is therefore very slow.
Then the solution approach of multigrid is as follows: at every iteration step
i,
we
start with the current solution vector
x
i
, perform some iteration steps
ν
1
with the
simple iteration method
IT,
and obtain the new approximation
x
f
(relaxation). Now
it can be shown that in the new approximation
x
f
, the high-frequency components of
the error are significantly reduced, but the low-frequency components hardly at all.
Therefore, we calculate the residuum:
y
f
¼ Kx
f
f
and project it onto the coarse grid using what we call
restrictor I
f
:
y
i
g
¼ I
f
y
f
. Now
we solve the equation system for the coarse grid:
K
g
w
g
¼ y
g
,
where
K
g
is the coarse grid matrix. The coarse grid matrix can be calculated either
by directly discretizing (
6.3
) on the coarse grid or by application of the restrictor
I
g
f
and
interpolator I
g
f
as a
Galerkin
operator
K
g
¼ I
f
KI
g
:
We project the calculated correction vector
w
i
g
by use of the interpolator
I
g
f
back
again on to the fine grid
w
f
¼ I
g
f
w
i
g
to obtain the new approximation:
x
iþ
1
¼ x
f
þ w
f
:
^
x
iþ
1
as start vector, we again run some iteration steps
ν
2
by our simple
iteration method
IT
and obtain the new iterate
x
iþ
1
. After this the iteration starts all
over again.
Instead of using only two grids, we can recursively repeat the whole method
over several grids - that is, perform a multigrid method. The procedure for four
Using
^
