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

The Gauss-Seidel 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 .