Why change the Gauss–Seidel step?
Suppose is too large for a direct factorization, where is a real symmetric positive-definite matrix. Gauss–Seidel changes one coordinate at a time, using the newest available coordinates as soon as they are computed. Successive over-relaxation (SOR) takes a multiple of each such coordinate correction. A multiple greater than one can move faster, but it can also overshoot. We will prove exactly which positive multiples guarantee convergence for every symmetric positive-definite system; this does not say which one is fastest for a particular matrix.
Throughout, is symmetric positive definite, , and arithmetic is exact. Thus , and there is a unique solution . Write , with diagonal and strictly lower and upper triangular respectively. Symmetry gives .
Definition 7.2.1
(SOR sweep with parameter )
At the start of sweep , let the vector be . In coordinate order , define
The residual is evaluated at the partly updated vector. For the method under-relaxes; for it over-relaxes.
With this is Gauss–Seidel: the new coordinate makes that row's residual zero at that instant. Later coordinate updates can make it nonzero again.
Collecting the coordinate equations gives
The matrix on the left is lower triangular with positive diagonal, so each sweep is well-defined. This formula also shows why the method depends on the coordinate order: a different order changes and .
A quadratic to minimize
Definition 7.2.2
(Energy of the system)
The energy of is
Since and is symmetric,
with equality only at . Thus solving the system is the same as minimizing this quadratic. If the current partly updated vector is and only coordinate changes by , expansion gives
Writing , the one-coordinate minimizer is . SOR instead chooses .
Lemma 7.2.3
(Energy change of one relaxed coordinate step)
Let , , and . Then
Proof
(Substitute the relaxed step)
The expansion above reads . With ,
Since , ; substituting gives the second form.
For every coordinate step decreases , unless its residual is already zero. In the over-relaxed case the step goes beyond the coordinate minimum, but not so far that it loses the energy gained. Decrease alone does not automatically prove convergence to the solution; we must also rule out getting stuck away from it.
Theorem 7.2.4
(SOR convergence for a positive-definite matrix)
If is real symmetric positive definite and , SOR converges to from every starting vector. The interval is a uniform guarantee: for convergence from every start fails even for some one-dimensional positive-definite system.
Proof
(From energy decrease to a vanishing full residual)
Let denote the vector after the first coordinate changes of sweep , so and . Let be the th change. Summing the energy identity over all coordinates and sweeps, and using , gives
Consequently each . For a fixed coordinate , the residual just before its update equals , so it also tends to zero. The partly updated vector differs from in only the preceding finitely many changes, all tending to zero. Therefore continuity of the linear map implies that every component of tends to zero. Since is a fixed finite matrix,
This argument uses a fixed finite and a fixed in the open interval. It does not supply a uniform convergence rate for all positive-definite matrices. The necessity statement is the scalar computation in the section on endpoints below.
The proof never shows that a single sweep reduces the error by a fixed factor. It extracts convergence from a finite energy budget, as follows.
Proof X-ray
Where the energy budget comes from
The key move is to sum the energy identity over every coordinate step. Monotone decrease alone would allow the energy to level off above ; the telescoping sum instead shows that the squared steps have a finite total, so the steps themselves tend to zero. Two hypotheses make this sum finite: positive definiteness bounds below by , and makes the coefficient positive. At the coefficient is zero and the energy budget says nothing.
The remaining steps convert small steps into a small error. Dividing by turns each step into its pre-update residual. Each such residual is a component of , evaluated at a partly updated vector, not at ; finiteness of is what lets the finitely many intervening steps, each tending to zero, be absorbed. The last step uses the fixed inverse to pass from the residual to the error.
Worked example: track the newest value
Worked example 7.2.5
(A Gauss–Seidel sweep and its energy)
Take
The matrix is positive definite because for nonzero . For , the coordinate equations become
The first sweep yields ; the second yields . Using the old first coordinate in the second equation would instead be a Jacobi step, not this sweep. In fact , whose fixed point is and whose error is multiplied by per sweep. Hence and , matching the exact solution.
The energy confirms the lemma. Here . The two residuals in the first sweep are and , and the coefficient is , so the decreases are and . Indeed and . The minimum is , so an energy gap remains after one sweep.
Worked example 7.2.6
(Over-relaxation with )
For the same system and start, the first coordinate change is . The second residual, using that new value, is , so the second change is . The first sweep is therefore , not .
The coefficient in the lemma is now , so the two energy decreases are and , a total of . Direct substitution gives , as it should. The residual at the end of the sweep is
Convergence is guaranteed by the theorem, but the first sweep by itself does not establish whether this choice is faster in the long run.
Why the endpoints and hypotheses matter
Worked example 7.2.7
(The endpoints in one dimension)
For the scalar problem , that is and , SOR becomes , so . If and , the iterates alternate sign forever while the energy remains constant, matching the zero decrease in the lemma. If , they never move; if or , then and their magnitude grows. This proves the stated uniform necessity.
Positive definiteness matters too: without it the quadratic may not be bounded below and the energy proof does not apply. A positive diagonal is not a substitute.
Counterexample mode
Symmetry and a positive diagonal are not enough
Claim: SOR with converges for every symmetric matrix with positive diagonal. Take
The matrix is symmetric with positive diagonal, but , so it is not positive definite and is unbounded below along . The sweep reads and . From the second coordinate is , so the iterates are unbounded although the unique solution is . The theorem needs positive definiteness, not only a positive diagonal.
Nor does the theorem guarantee that a finite-precision implementation reaches arbitrarily small error: rounding and stopping criteria require separate analysis.
Common mistake
(Using old coordinates in the residual)
The residual for coordinate must be computed at the partly updated vector. Using the values from the start of the sweep gives a Jacobi-type step, whose energy change is not described by the lemma; in the worked example it would give after the first sweep instead of .
Common mistake
(Reading the interval as advice on the best parameter)
The theorem says that every in converges. It does not say that larger is faster, or which is fastest for a given matrix. Parameters close to either endpoint can be very slow, and the coordinate ordering also affects performance.
Practice, with solutions
Quick check
(For the scalar equation , start at and use . Find the first two iterates and the exact error after steps.)
Solution · Answer
The update is . Thus , , and the fixed point is . Subtracting it gives .
Quick check
(In the worked two-dimensional example, compute the residual after the first Gauss–Seidel sweep. Why is its second component zero but its first component nonzero?)
Solution · Answer
At , and . The second update enforces the second row using the new first coordinate; that update also changes the first row after its earlier correction.
Quick check
(Suppose is symmetric positive definite and one complete SOR sweep with leaves unchanged. Prove that the starting vector solves .)
Solution · Answer
Each coordinate energy change is nonpositive. Their sum can be zero only if every change is zero, by the strict positive coefficient in the energy identity. Each pre-update residual is then zero. Since no coordinate changed, all these residuals are components of at the starting vector, which is therefore zero.