<< . .

. 34
( : 59)



. . >>

The very idea of the multigrid method lies in the approximative calcula-
tion of this remaining error on a coarse grid. The smooth error can still be
represented on the coarser grid and should be approximated there. Gener-
ally, the dimension of the problem is greatly reduced in this way. Since the
¬nite element discretizations are a central topic of this book, we develop
the idea of multigrid methods for such an example. But it will turn out
that the multigrid method can be used as well for both the ¬nite di¬erence
and the ¬nite volume methods. Multigrid methods have even been success-
fully used in areas other than the discretization of di¬erential equations.
Algebraic multigrid methods are generally applicable to systems of linear
equations (5.1) and generate by themselves an abstract analogy of a “grid
hierarchy” (see, for example, [65]).


5.5.2 Multigrid Method for Finite Element Discretizations
Let Tl = Th be a triangulation that originates from a coarse triangulation
T0 by l applications of a re¬nement strategy, for example the strategy of
Section 2.4.1. As we will see, it is not necessary that, for example, in two
space dimensions going from Tk to Tk+1 each triangle will be partitioned
into four triangles. Only the relation
Vk ‚ Vk+1 , k = 0, . . . , l ’ 1 ,
has to hold for ¬nite-dimensional approximation spaces V0 , V1 , . . . , Vl =
Vh generated by a ¬xed ansatz; i.e., the approximation spaces have to be
nested. This holds for all approximation spaces discussed in Section 3.3 if
Tk+1 is still a conforming triangulation and results from Tk by partitioning
of K ∈ Tk into a possibly varying number of elements of equal kind.
The nodes of Tk , which are the degrees of freedom of the discretization
(possibly multiple in a Hermite ansatz), are denoted by
ak , i = 1, . . . , Mk ,
i

and the corresponding basis functions of Vk are denoted by
•k , i = 1, . . . , Mk ,
i

with the index k = 0, . . . , l. For a quadratic ansatz on a triangle and Dirich-
let boundary conditions the ak are just the vertices and midpoints of the
i
edges in the interior of the domain. Let the underlying variational equa-
tion (2.21) be de¬ned by the bilinear form a and the linear form b on the
function space V . The system of equations to be solved is
Al xl = bl . (5.88)
In addition, we have to consider auxiliary problems
Ak xk = bk
5.5. Multigrid Method 241

for k = 0, . . . , l ’ 1. For the discretization matrix on each re¬nement level
we have, according to (2.34),
(Ak )ij = a •k , •k , i, j = 1, . . . , Mk , k = 0, . . . , l ,
j i

and for the right side of the problem to be solved
(bl )i = b •l , i = 1, . . . , Ml .
i

In Section 2.2, xl is denoted by ξ, and bl is denoted by q h .
First we discuss the ¬nite element discretization of a variational equa-
tion with symmetric bilinear form, so that in reference to Lemma 2.14 the
Galerkin method to be solved is equivalent to the Ritz method, i.e., to the
minimization of
1
Fl (xl ) := xT Al xl ’ bT xl .
2l l

Note that l indicates the discretization level and is not an index of a
component or an iteration step.
We distinguish between the function ul ∈ Vl and the representation
vector xl ∈ RMl , so that
Ml
xl,i •l .
ul = (5.89)
i
i=1

For a Lagrange ansatz we have
xl,i = ul al , i = 1, . . . , Ml ,
i

as illustrated by Figure 5.5.


2 1
ui 2
xi = 1
1 1.5



Figure 5.5. ui and xi .

Relation (5.89) de¬nes a linear bijective mapping
Pl : RMl ’ Vl . (5.90)
Thus for z l ∈ RMl (compare (2.35)),
1T 1
z l Al z l ’ bT z l = a (Pl z l , Pl z l ) ’ b(Pl z l ) = F (Pl z l ) ,
Fl (z l ) = l
2 2
where
1
a(u, u) ’ b(u) for u ∈ V
F (u) :=
2
242 5. Iterative Methods for Systems of Linear Equations


(k)
Let xl be the kth iterate to the solution of (5.88).
(1) Smoothing step: For ¬xed ν ∈ {1, 2, . . .} calculate
(k+1/2) (k)
= Slν xl .
xl
Let the corresponding function be:
(k+1/2) (k+1/2)
∈ Vl .
ul = Pl xl
(2) Coarse grid correction: Solve (exactly)
(k+1/2)
+ v ’ min
F ul (5.93)
varying v ∈ Vl’1 , with solution vl’1 . Then set
¯
= Pl’1 ul + Pl’1 vl’1 .
(k+1) (k+1/2) (k+1/2)
xl + vl’1 = xl
¯ ¯

Table 5.5. (k + 1)th step of the two-grid iteration.

is the energy functional for the variational equation.
If xl is an approximation of xl , then the error y l := xl ’ xl satis¬es the
error equation
Al y l = bl ’ Al xl . (5.91)
This equation is equivalent to the minimization problem
Fl (xl + y l ) = min Fl (xl + y)
y∈RMl
and therefore to
F (Pl xl + vl ) = min F (Pl xl + v) , (5.92)
v∈Vl

with vl = Pl y l .
If the error y l is “smooth” in the sense that it can be well approxi-
mated also in the lower-dimensional space Vl’1 , one can solve the error
equation (5.91) approximately as part of an iteration step by solving the
minimization problem (5.92) only on Vl’1 . The starting condition of a
“smooth” error will be ensured by the application of a ¬xed number of
steps of a smoothing iteration method. Let Sl denote the application of
such a smoothing operation, for example the damped Jacobi™s method
’1
Sl x = x ’ ωDl (Al x ’ bl )
with the diagonal matrix Dl corresponding to Al according to (5.18).
Thus we get the algorithm of the two-grid iteration, whose (k + 1)th step
is described in Table 5.5. Problem (5.93) from Table 5.5 is equivalent to
(compare with Lemma 2.3)
(k+1/2)
for all w ∈ Vl’1
a ul + v, w = b(w) (5.94)
5.5. Multigrid Method 243

(1) A priori smoothing: Perform ν1 smoothing steps:
(k+1/3) (k)
= Slν1 xl
xl ,
where ν1 ∈ {1, 2, . . .} is ¬xed. Let the corresponding function be
(k+1/3) (k+1/3)
ul := Pl xl .
(2) Coarse grid correction: Solve on Vl’1 the Galerkin discretization
a(¯l’1 , w) = ˜ for all w ∈ Vl’1
v b(w) (5.95)
with the bilinear form a and the linear form
(k+1/3)
˜
b(w) := b(w) ’ a ul ,w

(a) for l = 1 exactly,
(b) for l > 1 by µ steps of a multigrid iteration on level l ’ 1 for a
and ˜ and for the start approximation 0.
b
+ Pl’1 vl’1 .
(k+2/3) (k+1/3)
Set xl = xl ¯
(3) A posteriori smoothing: Perform ν2 smoothing steps
(k+1) (k+2/3)
= Slν2 xl
xl ,
with ν2 ∈ {1, 2, . . .} ¬xed.

Table 5.6. (k + 1)th step of the multigrid iteration on level l for bilinear form a
and linear form b.

and thus again to the Galerkin discretization of a variational equation with
Vl’1 instead of V , with the same bilinear form and with a linear form
de¬ned by
(k+1/2)
w ’ b(w) ’ a ul for w ∈ Vl’1 .
,w

Hence we can ignore the assumption of symmetry for the bilinear form a
and ¬nd the approximative solution of the error equation (5.91) on grid
level l ’ 1 by solving the variational equation (5.94). The equivalent system
of equations will be derived in the following. On the one hand, this prob-
lem has a lower dimension than the original problem, but it also must be
solved for each iteration. This suggests the following recursive procedure:
If we have more than two grid levels, we again approximate this variational
equation by µ multigrid iterations; in the same way we treat the hereby
created Galerkin discretization on level l ’ 2 until level 0 is reached, where
we solve exactly. Furthermore, to conclude each iteration step smoothing
steps should be performed. This leads to the algorithm of the multigrid
iteration. The (k + 1)th step of the multigrid iteration on level l for the
(k)
bilinear form a, linear form b, and starting iteration xl is described in
Table 5.6.
244 5. Iterative Methods for Systems of Linear Equations

In general, ν1 = ν2 is used. In a convergence analysis it turns out that
only the sum of smoothing steps is important. Despite the recursive de¬-
nition of a multigrid iteration we have here a ¬nite method, because the
level 0 is reached after at most l recursions, where the auxiliary problem
will be solved exactly. For µ usually only the values µ = 1 or µ = 2 are
used. The terms V-cycle for µ = 1 and W-cycle for µ = 2 are commonly
used, because for an iteration, the sequence of levels on which operations
are executed have the shape of these letters (see Figure 5.6).

for l = 2 :

Level
µ=1 µ=2
2 o o o o

1 o o o o o

0 o o o



for l = 3 :

Level

3 o o o o

2 o o o o o

1 o o o o o o o o

0 o o o o o
Figure 5.6. Grid levels for the V-cycle (µ = 1) and the W-cycle (µ = 2).

The problems in (5.94) and (5.95) (see Table 5.6) have the form
for all w ∈ Vl’1 ,
a (u + v, w) = b(w) (5.96)
where v ∈ Vl’1 is unknown and u ∈ Vl is known. An equivalent system of
equations arises by inserting the basis functions •l’1 , j = 1, . . . , Ml’1 ,
j
for w and an appropriate representation for v. If we again take the
representation with respect to •l’1 , we get as in (2.34)
j
’1
Al’1 Pl’1 v = dl’1 . (5.97)
Here the residual dk ∈ RMk of u on the di¬erent levels k = 0, . . . , l is
de¬ned by
dk,i := b •k ’ a u, •k , i = 1, . . . , Mk .
i i
5.5. Multigrid Method 245

We now develop an alternative representation for (5.97) and the coarse
grid correction for possible generalizations beyond the Galerkin approxima-
tions. Therefore, let R ∈ RMl’1 ,Ml be the matrix that arises through the
unique representation of the basis functions •l’1 with respect to the basis
j
l
•i , which means the elements rji of R are determined by the equations
Ml
•l’1 rji •l ,
= j = 1, . . . , Ml’1 .
i
j
i=1

Then (5.96) is equivalent to
a(v, w) = b(w) ’ a(u, w) for all w ∈ Vl’1
« 
Ml’1
” a •l’1 , •l’1  = b •l’1 ’ a u, •l’1 , j = 1, . . . , Ml’1
’1
Pl’1 v s j j j
s
s=1
Ml’1 Ml Ml Ml
’1
” rji b •l ’ a u, •l
rst •l rji •l
Pl’1 v s a , =
t i i i
s=1 t=1 i=1 i=1
Ml’1 Ml
’1
” rji a •l , •l rst Pl’1 v = (Rdl )j , j = 1, . . . , Ml’1 .
t i s
s=1 i,t=1

Hence the system of equations has the form
’1
RAl RT Pl’1 v = Rdl . (5.98)
The matrix R is easy to calculate for a node-based basis •l satisfying
i
•i aj = δij , since in this case we have for v ∈ Vl ,
l l

Ml
v al •l ,
v= i i
i=1

and therefore in particular,
Ml
•l’1 •l’1 al •l
= i i
j j
i=1

and thus
rji = •l’1 al .
i
j

For the linear ansatz in one space dimension with Dirichlet boundary
1
conditions (i.e., with V = H0 (a, b) as basic space) this means that
«1 
11
2 2
¬ ·
1
11
¬ ·
R=¬ ·.
2 2
(5.99)
¬ ·
..
 
.
1 1
1
2 2
246 5. Iterative Methods for Systems of Linear Equations

The representation (5.98) can also be interpreted in this way:
Due to Vl’1 ‚ Vl the identify de¬nes a natural prolongation from Vl’1 to
Vl , which means that
p : Vl’1 ’ Vl , v ’ v ,
˜
as illustrated by Figure 5.7.



1 1
1 1
2 2




Figure 5.7. Prolongation.

This prolongation corresponds to a prolongation p from RMl’1 to RMl ,
the canonical prolongation, through the transition to the representation
vectors (5.90). It is given by
p := Pl’1 Pl’1 , (5.100)
since for xl’1 ∈ RMl’1 , p can be composed as follows:
p
˜
xl’1 ’ Pl’1 xl’1 ’ Pl’1 xl’1 ’ Pl’1 Pl’1 xl’1 .
Obviously, p is linear and can be identi¬ed with its matrix representation
in RMl ,Ml’1 . Then
p = RT (5.101)
holds, because
Ml’1 Ml Ml’1
yj •l’1 yj rji •l ,
Pl’1 y = = i
j
j=1 i=1 j=1

i.e., RT y = Pl’1 (Pl’1 y) for any y ∈ RMl’1 .
(l)
In the following RMl will be endowed with a scalar product ·, · , which
is an Euclidean scalar product scaled by a factor Sl ,
Ml
(l)
xl , y l := Sl xl,i yl,i . (5.102)
i=1

The scaling factor is to be chosen such that for the induced norm · and
l
the L2 („¦)-norm on Vl ,
¤ xl ¤ C2 Pl xl
C1 Pl xl (5.103)
0 l 0

for x ∈ RMl , l = 0, 1, . . ., with constants C1 , C2 independent of l: If the
triangulations are members of a regular and quasi-uniform family Th (see
5.5. Multigrid Method 247

De¬nition 3.28), then in d space dimensions one can choose Sl = hd , with
l
hl being the maximal diameter of K ∈ Tl (see Theorem 3.43).
Let r : RMl ’ RMl’1 be de¬ned by
r = p— , (5.104)
with the adjoint p— de¬ned with respect to the scalar products ·, · (l’1)

<< . .

. 34
( : 59)



. . >>