588 Appendix A
Figure A.3. Restriction and prolongation. The coarse grid points are marked by
×and the fine grid points by•. The arrows in the left hand figure represent the
restriction, and those in the right hand figure, the prolongation map.transferred to the fine grid, and the mapping used for this purpose is calledpro-
longation. On the fine grid, finally, a few Gauss–Seidel iterations are then carried
out to smooth out errors resulting from the somewhat crude representation of the
solution at the higher level. Schematically we can represent the method described
by the following diagram:
Coarse: δ=A−^1 r→δ
→→
Fine: Gauss–Seidel→r Gauss–Seidel
The obvious extension then is to play the same game at the coarse level, go to a
‘doubly coarse’ grid etc., and this is done in the multigrid method.
We now fill in some details. First of all, we must specifiy arestriction mapping,
which maps a function defined on the fine grid onto the coarse grid. We consider
here a coarse grid with sites being the centres of half of the plaquettes of the fine
grid as inFigure A.3. The value of a function on the coarse grid point is then given
as the average value of the four function values on the corners of the plaquette.
Usingψfor a function on the fine grid andφfor a function on the coarse grid, we
can write the restriction operator as
φij=(Pl−1,lψ)ij=^14 (ψ 2 i,2j+ψ 2 i+1,2j+ψ 2 i,2j+ 1 +ψ 2 i+1,2j+ 1 ). (A.105)φijcan be thought of as centred on the plaquette of the fourψfunctions at the right
hand side. We also need a prolongation mapping from the coarse grid to the fine
grid. This consists of copying the value of the function on the coarse grid to the four
neighbouring fine grid points as in the right hand side of Figure A.3. The formula
for the prolongation mapping (Pl,l− 1 )is
ψij=(Pl,l− 1 φ)ij=φi/2,j/ 2 (A.106)wherei/2 andj/2 denote (truncated) integer divisions of these indices.
We need the matrixAon the coarse grid. However, we know its form only on
the fine grid. We use the most natural option of taking for the coarse form also a