Iterative methods for a linear system of equations
|Au = f,||(1)|
|Buk+1 = f - ( A - B ) uk||(2)|
|uk+1 = uk + B-1 ( f - Auk )||(3)|
Clearly, the exact solution
is a fixed point
of iteration (2).
To check whether the iteration converges
may be inserted into (3).
This simplifies to
|ek+1 = ( I - B-1A ) ek.||(4)|
|||ek+1 || || I - B-1A || || ek ||.||(5)|
The difficulty is to find the right compromise of having B easily invertible, and being a good approximation to A.
Relaxation methods use particularly simple choices of B. For the Gauß-Jacobi method B=diag(A), for the Gauß-Seidel method, B is taken as the lower triangle of A. These B are certainly easily invertible, however, they do not make very good approximations to A, at least when A is large. However, they provide good smoothers for the multigrid method.
Here we now study an alternative method, the so-called coarse grid correction method.
Our idea is to construct B-1 form a similar grid problem as A, however, a simpler one by taking fewer gridlines. Let us assume that AC is constructed just like A, but from a grid with only (N-1)x(N-1) gridlines. The dimension of the matrix is therefore less than ¼ of the original dimension. It is therefore obviously easier to invert AC than A. Unfortunately, however, equation (3) cannot be used any more, because now AC-1 does not have a dimension compatible with f, A, and u. To fix this, we introduce the interpolation (prolongation) operator P, and the restriction operator R. R and P are mappings between these two spaces:
|BC = P AC-1 R||(8)|
Now we replace B-1 in (3) by BC. Note that since BC has rank smaller than A, therefore there exists no formulation of the iteration equivalent to (2).
For the same reason, the product BCA is singular, and
||| I - BCA || 1.|
The multigrid method alternates between smoothers and coarse grid corrections. The combination of the two results in a new iterative algorithm, where the different convergence properties of the two basic iteration combine favorably. The two grid algorithm resulting from this idea is extended to a multigrid algorithm by extending this idea recursively to the solution of A-1.
Besides the simple iterative schemes many more possibilities exist. We refer to the chapter on numerical linear algebra in the Computational Science Education Project.
Ulrich Ruede , Thu Feb 2 21:06:09 MEZ 1995
Updated by Craig C. Douglas