Why update one coordinate at a time?
When a discretized model produces a large sparse system , factoring may require substantial storage. A stationary iteration instead repeatedly improves an approximate solution. Jacobi computes all new coordinates from the previous vector; Gauss–Seidel uses a new coordinate as soon as it is available. The order of the equations is therefore part of the algorithm. We will derive a useful convergence result for symmetric positive-definite matrices and see exactly what the relaxation parameter does. The result concerns exact arithmetic; it is not a prediction of runtime or roundoff error.
Write , where is diagonal, strictly lower triangular and strictly upper triangular. Assume . For an old iterate , the Gauss–Seidel sweep solves
This is forward substitution, not a request to form an inverse. In coordinate , the latest available values give the provisional value
Definition 1.7.1
(Gauss–Seidel and SOR sweeps)
One Gauss–Seidel sweep visits in order and sets . Successive over-relaxation (SOR) with a parameter , fixed throughout the sweeps, instead sets , where is computed from the already relaxed coordinates , .
Thus is Gauss–Seidel, is under-relaxation, and is over-relaxation. The name alone does not imply that over-relaxation is faster.
Energy and convergence
Suppose now that is real, symmetric and positive definite. Then , the solution is unique, and
The gradient is . Holding all coordinates except fixed, is the unique minimizer of this quadratic along that coordinate. SOR moves a fraction of the way there, possibly passing it.
Lemma 1.7.2
(Energy change of one relaxed coordinate update)
For the current vector , set , so that the SOR update of coordinate is . Then
Proof
(Expand the quadratic along one coordinate)
For , symmetry of gives . Substituting gives , which is the stated value.
The coefficient is positive exactly when , and it is largest at , the exact coordinate minimizer.
Theorem 1.7.3
(SOR for a symmetric positive-definite system)
If is real symmetric positive definite and , every SOR sequence converges to the unique solution, from every starting vector.
Proof
(Strict decrease per sweep and compactness)
The lemma shows that each coordinate update cannot increase the energy error. Let be the linear map taking an error vector through one complete sweep. For every nonzero , the energy decreases strictly during that sweep. Indeed, if equality held, every displayed squared gradient would be zero. Then no coordinate would change, so at the original vector, contradicting nonsingularity. On the compact unit sphere in the norm , the continuous ratio therefore has a maximum . Consequently . This proves convergence, but does not give a practical value of or identify an optimal .
Proof X-ray
From one-coordinate decrease to a uniform contraction
The lemma gives only non-increase, coordinate by coordinate; the proof upgrades it in two moves. First, strict decrease over a whole sweep. If a sweep lost no energy, then, because , every gradient component met during the sweep was zero, so no coordinate moved, and those components were therefore the components of at the starting error. Nonsingularity then forces . Symmetry has been used earlier, to make the gradient of , and positive definiteness gives and the norm . Second, uniformity. Strict decrease for each alone would allow ratios creeping toward one. Because is linear the ratio depends only on direction, and a continuous function on the compact unit sphere attains its maximum, so . At the first move fails, which is why the boundary is excluded.
A complete sweep
Worked example 1.7.4
(Compare two relaxation choices)
Let and . The leading entry is positive and the determinant is , so is positive definite. Its exact solution is . Starting at , Gauss–Seidel gives , then uses this new value to obtain .
With , the first coordinate instead becomes . Using that new value, the second provisional value is , and relaxation gives . These are different iterates, each convergent under the theorem. Comparing only the first step does not establish which choice reaches a specified tolerance sooner.
Common mistake
(Relaxing after the sweep instead of during it)
SOR relaxes each coordinate before the next one is computed. Relaxing the finished Gauss–Seidel vector, , is a different method. In the example with it gives , whereas SOR gives : the second coordinate of SOR already sees the relaxed first coordinate.
Worked example 1.7.5
(Watching the energy fall in one sweep)
For the same system, . In the Gauss–Seidel sweep from , the first update has and , so the lemma predicts a drop of ; indeed . The second update starts from with and , a predicted drop of , and direct evaluation gives . The energy error falls from to , a factor of about in one sweep.
Worked example 1.7.6
(The boundary preserves energy)
With and the same data, the first coordinate becomes . The second provisional value is , so . After one sweep the iterate is , and
Each update reflects the coordinate across the line minimizer, the factor vanishes, and no energy is lost, even though the matrix is positive definite. The convergence theorem's open interval is exactly what excludes this.
Counterexample mode
A positive-definite matrix does not rescue every parameter
For the one-dimensional system , SOR gives . At a nonzero error changes sign forever, and for its magnitude grows. At the iterate never moves. Positive definiteness alone does not guarantee convergence for an arbitrary parameter.
Strict diagonal dominance is another familiar sufficient condition for some stationary iterations, but it is not a prerequisite for the theorem above. For example, is positive definite (positive leading entry and determinant ), although its first row is not diagonally dominant. Conversely, a small update by itself is not a certificate of small error.
Common mistake
(Stopping because the update is small)
For the scalar system with and , the first update has size while the error is still , and after sweeps the error is . A tiny change between sweeps can reflect a tiny or slow contraction, not proximity to the solution. Check an appropriately scaled residual and set a maximum iteration count.
Practice with solutions
Quick check
(Perform the second Gauss–Seidel sweep in the worked example.)
Start from and use each new coordinate at once.
Solution · Answer
From , the new coordinates are and .
Quick check
(For and , start at . Find the next two iterates.)
The error is multiplied by .
Solution · Answer
and . The error factor is , so the iterates alternate while converging.
Quick check
(For , find the Jacobi iteration matrix and its spectral radius.)
The Jacobi matrix is .
Solution · Answer
, so its eigenvalues satisfy . Thus . This example is not diagonally dominant, yet Jacobi converges; failure of that sufficient test is not a divergence proof.
Quick check
(Explain why the SOR proof does not prove convergence at .)
Look at the coefficient in the lemma.
Solution · Answer
The energy decrease coefficient vanishes, so strict decrease and the uniform contraction argument both fail. The scalar example and the energy-preserving sweep above show that the boundary can actually fail to converge.