The Gauss-Seidel Method



next up previous contents index
Next: The Successive Overrelaxation Up: Stationary Iterative Methods Previous: Convergence of the

The Gauss-Seidel Method

 

Consider again the linear equations in (gif). 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 (gif) 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.

Successive displacements, method of: Gauss-Seidel method.

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 gif and §gif.

In matrix terms, the definition of the Gauss-Seidel method in (gif) 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 gif.

  
Figure: The Gauss-Seidel Method

 



next up previous contents index
Next: The Successive Overrelaxation Up: Stationary Iterative Methods Previous: Convergence of the



Jack Dongarra
Mon Nov 20 08:52:54 EST 1995