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)