Database Reference
In-Depth Information
Of course, this does no longer hold for multiple smoothing steps. For two
smoothing steps, we would obtain
x
:¼ x ^
ð
y
ÞþAx ^
ð
y
Þ Ax ^
ð
y
Þ¼x
2
y þ A
^
y
^
:
The resulting multigrid method is summarized in Algorithm 6.2. Hereupon, the
upper index
1
has been omitted for the sake of readability.
Algorithm 6.2: Multigrid V-cycle
Input: matrix
A
, right-hand side
b
, prolongator
L
, restrictor
R
, initial iterate
x
n
:¼ x
0
∈
R
n
of (
6.4
)
x
e
∈
R
Output: approximate solution
1: procedure VCYCLE(
y
)
2:
x
:
¼ x y
⊲
pre-smoothing
y
1
3:
:
¼ R
(
Ax y
)
computing the residual
⊲
x
1
:
¼
(
A
1
)
1
y
1
4:
direct solver on the coarse grid
⊲
x
:
¼ x
+
Lx
1
5:
⊲
coarse grid correction
6:
x
:
¼ x y
post-smoothing
⊲
7: return
x
8: end procedure
9: return VCYCLE(
b
)
initial call
⊲
The following rather technical convergence result has been established in
[Pap10].
Theorem 6.1 (Theorem 3.7.1 in [Pap11])
Let
q
ðÞ
j
:¼
α
,
i
,
j
∈
G
β
P
nn
∈
R
, e
p
ij
ð
6
:
15
Þ
,
0
else
for
0
α
1,
and
X
q
ðÞ
j
q
ðÞ
j
0,
j
∈
G
β
,
¼
1
, β∈
m
:
j∈G
β
Moreover, we define
A
:¼ I γ
P
,
Q
:¼ I A
,
Þ
1
RA
,
K
:¼ I L RAL
ð
1
P P
ε :¼
,
k
1
,
and
ε :¼ α
k
I RPL
q
ðÞ
j
c
:¼
min
β
,
j
: