Using the newest information
A large system need not be symmetric or positive definite. For such a system the energy argument for SOR is unavailable, but the order in which Gauss–Seidel uses information gives another way to bound errors.
Definition 7.3.1
(Gauss–Seidel sweep)
Let be a finite real square matrix with every , fix an ordering of its unknowns, and work in exact arithmetic. Write , with diagonal and and strictly lower and upper triangular. Starting from any , one sweep is
that is, with .
The lower-indexed entries on the right have already changed during this sweep. Since is triangular with nonzero diagonal, each sweep is well-defined even if itself happens to be singular. A convergence guarantee must also establish that the solution exists and is unique.
A row-by-row certificate
Definition 7.3.2
(Sassenfeld row numbers)
In the same order as the sweep, define the nonnegative numbers
When a new coordinate depends on an earlier one, its contribution is multiplied by the bound already obtained for that coordinate. This is the Sassenfeld criterion; it is a sufficient test, not a characterization of all convergent systems.
Theorem 7.3.3
(Gauss–Seidel row certificate)
If , then is nonsingular and Gauss–Seidel converges from every initial vector to the unique solution . For every sweep,
Furthermore, for , the computable step difference satisfies
Proof
(Contraction along a sweep)
Compare one sweep from arbitrary and , and set . For coordinate 1 the update formula gives . Suppose the same bound with holds for all . Taking absolute values in row and inserting these earlier bounds gives
Induction proves
This proof did not assume that a solution exists. To establish nonsingularity, let . Then , so , and . As , . A square matrix with trivial kernel is invertible, so exists uniquely and is a fixed point of . Applying the contraction bound with repeatedly proves the error bound and convergence.
For the step bound, set . The contraction gives . Since the iterates converge, . Taking norms and summing the geometric series gives the claimed bound. This is an exact-arithmetic certificate; rounded computations require additional error control.
The proof is short, but each hypothesis has a definite place in it.
Proof X-ray
Build the bound along a sweep
The key move is to bound the coordinates in the order they are computed. In row , the already-updated coordinates enter through , whose size the induction has already bounded by rather than by . This is where using the newest information pays off, and it is why depends on the ordering. The coordinates that are not yet updated enter through and are bounded by . The nonzero diagonal is used only to divide by ; it makes defined even for singular .
The second move obtains existence and uniqueness from the contraction instead of assuming them. For , the identity says that is fixed by the sweep with zero right-hand side, so forces . Only after this is available as a fixed point to compare with. The step bound closes by a telescoping series: it uses the convergence just proved to write as the sum of all later steps, and to sum .
Strict row dominance implies the certificate
Corollary 7.3.4
(Strict row dominance gives the certificate)
Suppose for every row, and let
Then in every ordering, so Gauss–Seidel converges for every right-hand side and initial vector.
Proof
(Induction on the row numbers)
Strict dominance in each row gives . Inductively, if each earlier , then each is at most one, and the formula gives
The first row starts the induction, since . Thus . Strict row dominance is also preserved by any simultaneous reordering of equations and unknowns, so the conclusion holds in every ordering.
Strict row dominance therefore guarantees convergence of both Gauss–Seidel and Jacobi, without requiring symmetry. The bound need not be a sharp convergence rate. The strict inequality cannot be weakened to equality in every row.
Counterexample mode
Weak dominance is not enough
Claim: if in every row, Gauss–Seidel converges. Take
Both rows satisfy the weak inequality with equality, and , , so . The matrix is singular and the system is inconsistent, because cannot equal both and . The sweep reads and , so increases by one in every sweep and the iterates are unbounded. The claim fails; the theorem needs , which strict dominance supplies.
Worked example: a certificate when row dominance fails
Worked example 7.3.5
(Row dominance fails but the certificate holds)
Consider
The third row is not strictly diagonally dominant: . The Jacobi infinity-norm test also fails because its third row ratio is . Nevertheless, in the displayed order,
The theorem certifies a unique solution and convergence from every start. Indeed . From the first sweep gives
The second row uses the new first coordinate, and the third uses both new coordinates. The resulting error norm is , below the bound . Failing a Jacobi norm test says nothing by itself about whether Jacobi converges; it certainly does not establish Gauss–Seidel divergence.
Worked example 7.3.6
(The computable stopping bound after two sweeps)
Continue the same system from . The second sweep gives
The step difference is , with infinity norm . Since , the computable bound is
The actual error is , with norm . The contraction bound from the first sweep gives the sharper . Both bounds are valid. The step bound needs no knowledge of , but its factor makes it pessimistic while the steps are still large; it becomes useful as a stopping test once successive iterates agree closely.
What a failed test does and does not mean
Worked example 7.3.7
(A failed certificate with a convergent iteration)
For
we have and , so and the certificate fails. Yet , and the error update is
Both components tend to zero from every start, since and . The first component can grow in the first sweep even though the iteration converges.
Common mistake
(Reading a failed certificate as divergence)
The certificate is an upper bound. When the bound says nothing, as the example above shows: the iteration converges although . A proof of divergence needs a separate argument, such as an explicit error component that grows in every sweep.
Common mistake
(Assuming an invertible matrix gives a defined sweep)
Invertibility alone does not guarantee a well-defined sweep: is invertible but has zero diagonal in this ordering. Reordering equations may repair zero pivots, but it changes the iteration and its certificate; it is not automatic for every proposed ordering.
Practice with solutions
Quick check
(For compute the row certificate. Does it prove convergence?)
Solution · Answer
and . Thus , and the theorem applies to every right-hand side and initial vector.
Quick check
(For the worked three-by-three system, reverse the order of both equations and unknowns. Compute the new certificate.)
Solution · Answer
The reordered matrix is . Its values are , , and . The maximum exceeds one. This ordering fails the test, although the original ordering passed; the failure alone does not determine convergence.
Quick check
(Suppose a verified exact-arithmetic certificate has and . Bound the error.)
Solution · Answer
The step bound gives times the difference, namely . In floating-point arithmetic the stated exact bound does not automatically account for rounding.
Quick check
(Give an invertible system for which Gauss–Seidel diverges in the stated order.)
Solution · Answer
Take and . Its determinant is , but the update gives and . Any initial vector with nonzero second component produces an unbounded sequence. Nonsingularity ensures a unique solution, not convergence of this iteration.