Iterative methods for a linear system of equations

Au = f, | (1) |

Bu^{k+1} = f - ( A - B ) u^{k} |
(2) |

u^{k+1} = u^{k} + B^{-1} ( f - Au^{k} ) |
(3) |

Clearly, the exact solution
u^{*}=A^{-1}f
is a *fixed point*
of iteration (2).
To check whether the iteration converges
u^{k}=u^{*}+e^{k}
and
u^{k+1}=u^{*}+e^{k+1}
may be inserted into (3).
This simplifies to

e^{k+1} = ( I - B^{-1}A ) e^{k}. |
(4) |

||e^{k+1} ||
|| I - B^{-1}A || || e^{k} ||. |
(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 A_{C} 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 A_{C} than A.
Unfortunately, however, equation (3)
cannot be used any more, because now A_{C}^{-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:

R:
^{NxN} -> ^{(N-1)/2x(N-1)/2} |
(6) |

P:
^{(N-1)/2x(N-1)/2} -> ^{NxN} |
(7) |

B_{C} = P A_{C}^{-1} R |
(8) |

Now we replace B^{-1} in (3)
by B_{C}.
Note that since B_{C} has rank smaller than A,
therefore there exists no formulation of
the iteration equivalent to (2).

For the same reason, the product
B_{C}A is singular, and

|| I - B_{C}A ||
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