The Conjugate Gradient Method - Finite Elements: Theory, Fast Solvers, and Applications in Elasticity Theory - page 187

§ 1. Classical Iterative Methods
for Solving Linear Systems

For a small step size h , the finite element method leads to very large systems of
equations. Although the associated matrices are sparse, unfortunately their struc-

ture is such that after a few (approximately √ n ) steps of Gauss elimination, the
computational effort will grow significantly because many zero elements will be
replaced by nonzero ones.
This is the reason why iterative methods were studied in the fifties. The meth-
ods introduced then, which we shall call classical iterative methods , converge very
slowly. Nowadays they are rarely used as stand-alone iterative methods. Neverthe-
less, they have not lost their importance. Indeed they are often used in conjunction
with modern iterative methods, for example in the CG method for preconditioning,
and in the multigrid method for smoothing.
We now review classical iterative methods. For more detailed treatments, see
the monographs of Varga [1962], Young [1971], and Hackbusch [1991].

Stationary Linear Processes

Many iterative methods for the solution of the system Ax = b are based on a
decomposition of the matrix

A = M − N.

Here M is assumed to be an easily invertible matrix, and the given system can be
rewritten in the form

Mx = Nx + b.

This leads to the iteration

Mx k + 1 = Nx k + b,

or equivalently x k + 1

= M − 1 (Nx k + b) ,or

x k + 1 = x k + M − 1 (b − Ax k ), k = 0 , 1 , 2 ,... . ( 1 . 1 )

Clearly, (1.1) is an iteration of the form

x k + 1 = Gx k

+ d

( 1 . 2 )

with G = M − 1 N = I − M − 1 A , d = M − 1 b .