**Previous:** The Jacobi Method

**Up:** Stationary Iterative Methods

**Next:** The Successive Overrelaxation Method

**Previous Page:** Convergence of the Jacobi method

**Next Page:** The Successive Overrelaxation Method

Consider again the linear equations in (). If we proceed as with the Jacobi method, but now assume that the equations are examined one at a time in sequence, and that previously computed results are used as soon as they are available, we obtain the Gauss-Seidel method:

Two important facts about the Gauss-Seidel method should be noted.
First, the computations in () appear
to be serial. Since each component of the new iterate depends upon
all previously computed components, the updates cannot be done
simultaneously as in the Jacobi method. Second, the new iterate
depends upon the order in which the equations are examined.
The Gauss-Seidel method is sometimes called the * method of
successive displacements* to indicate the dependence of the
iterates on the ordering. If this ordering is changed, the *
components* of the new iterate (and not just their order) will
also change.

These two points are important because if is sparse, the dependency of each component of the new iterate on previous components is not absolute. The presence of zeros in the matrix may remove the influence of some of the previous components. Using a judicious ordering of the equations, it may be possible to reduce such dependence, thus restoring the ability to make updates to groups of components in parallel. However, reordering the equations can affect the rate at which the Gauss-Seidel method converges. A poor choice of ordering can degrade the rate of convergence; a good choice can enhance the rate of convergence. For a practical discussion of this tradeoff (parallelism versus convergence rate) and some standard reorderings, the reader is referred to Chapter and §.

In matrix terms, the definition of the Gauss-Seidel method in () can be expressed as

As before, , and represent the diagonal, lower-triangular, and upper-triangular parts of , respectively.

The pseudocode for the Gauss-Seidel algorithm is given in Figure .