Civil Engineering Reference
In-Depth Information
of unknowns is reduced by a factor of about 4. Moreover, the bandwidth of the
matrix for the coarse grid is about half as large. This means that the number of
operations needed for Gauss elimination is reduced by a factor of about 16. This
leads to major savings after just two or three iterations.
In general, the number of operations needed to solve the system corresponding
to mesh size 2
h
will still be too large, and so we repeat the process. We continue
to double the size of the grid until we get a sufficiently small system of equations.
The Algorithm
For the sake of simplicity, we first describe the two-grid algorithm for conforming
finite elements.
To formulate multigrid algorithms, we need some notation. It is standard to
use the letter
for the smoothing operator. For example, when smoothing via
Richardson relaxation, we have
S
x
−→
S
x
:
=
x
−
ω(A
h
x
−
b
h
).
(
1
.
4
)
In order to avoid confusion with the finite element spaces
S
h
, we suppress the
subscript
h
in our notation for smoothing operators.
Let
N
{
ψ
i
}
be a basis for
S
h
. Each vector
x
∈ R
with
N
=
N
h
=
dim
S
h
is
associated with the function
u
=
i
x
i
ψ
i
∈
S
h
. The indices are inherited in the
correspondence.
The iterates
u
h
as well as the intermediate values
u
k,
h
are associated with the
fine grid, while the quantities
v
2
h
(which actually depend on
k
) correspond to the
coarser grid with double mesh size.
1.3 Two-Level Iteration
(k-th cycle):
Let
u
h
be a given approximation in
S
h
.
1.
Smoothing Step.
Perform
ν
smoothing steps:
u
k,
1
ν
u
h
.
=
S
h
2.
Coarse-Grid Correction.
Compute the solution
v
2
h
of the variational problem
at level 2
h
:
J(u
k,
1
+
v)
−→
min
v
∈
S
2
h
!
h
Set
=
u
k,
1
u
k
+
1
+
v
2
h
.
h
h
Search WWH ::
Custom Search