Motivation
Discretizing a boundary value problem is only half the calculation: the resulting equations still have to be solved. For many grid points, forming an explicit inverse wastes both storage and the sparsity of the stencil. An iterative method instead improves a candidate grid function by repeated local updates. The distinction between the exact solution of the finite system and the solution of the differential equation is essential: an iteration can solve the wrong or too-coarse discretization extremely accurately.
Jacobi computes every new entry from the previous sweep. Gauss–Seidel uses an updated entry as soon as it is available; successive over-relaxation (SOR) takes a fraction or multiple of that correction. We derive these procedures for a simple Poisson system, and then prove convergence for any symmetric positive definite matrix.
Definitions
For on with prescribed endpoint values, let and let approximate . Multiplying the central-difference equations by gives
Definition 3.6.1
(Gauss–Seidel and SOR sweeps)
The known endpoint terms are moved to the right. In matrix form , where has diagonal and adjacent entries . More generally, for a matrix with nonzero diagonal, a Gauss–Seidel sweep in increasing index order sets
SOR writes , using already relaxed new entries for . The parameter gives Gauss–Seidel; under-relaxes and over-relaxes. A sweep is one visit to each coordinate. Different ordering changes the iteration, although the same linear system is being solved.
Definition 3.6.2
(Discrete energy and residual)
For symmetric positive definite , define the discrete energy , and the residual . Its unique minimizer satisfies
Thus the energy gap measures algebraic error in the -norm. Multiplying both and by the same positive number leaves the iteration and its solution unchanged, though it rescales the energy and residual.
Theorem/proposition
Theorem 3.6.3
(Energy descent and convergence of SOR)
Let be a real symmetric positive definite matrix, , and . For any starting vector, cyclic SOR in a fixed coordinate order converges to the unique solution of . At a single coordinate update with current residual , the energy decrease is
Proposition 3.6.4
(Residual and algebraic error)
If the smallest eigenvalue of symmetric positive definite is , then every candidate satisfies
These bounds concern the finite linear system, not its discretization error.
Proof sketch or proof idea
Proof
(Coordinate descent on the energy)
Hold all coordinates except fixed. Along , the energy is the quadratic . Its exact one-coordinate minimizer has , so SOR chooses . Substitution gives the displayed energy decrease. Positive definiteness ensures and a lower energy bound. Summing decreases over all updates shows that the squared residual seen at each successive update is summable, hence tends to zero.
To pass from these coordinate residuals to the residual at the start of a sweep, observe that each update changes the vector by in one coordinate, so every update tends to zero. There are only updates per sweep and is fixed; the difference between the residual at any update and at the sweep's start therefore tends to zero. Every component of the start-of-sweep residual tends to zero. Since is fixed, the sweep-start vectors converge to , and the intermediate vectors converge to the same limit. This proves convergence without assuming that every individual error component decreases.
Proof X-ray
What positive definiteness and the range of the parameter each do
The proof uses positive definiteness three times, each for a different purpose. It gives , so every coordinate update is defined and the energy along is a convex parabola. It makes bounded below by , so the nonnegative decreases have a finite sum. And it makes invertible, so a residual tending to zero forces the iterates to . The condition is used exactly once: it makes the factor positive, so a finite sum of decreases controls ; at the decrease vanishes and the argument yields nothing. Symmetry is what makes the gradient of ; for a nonsymmetric matrix the gradient of is , and the descent identity no longer describes the update. The key move is the passage from momentary to whole residuals. Summability controls only the residual component of the coordinate being updated, at the moment of its update. Because each update moves one coordinate by and a sweep has only updates, the residual hardly changes during a sweep, and these momentary components assemble into the full residual at the start of the sweep.
The residual proposition needs only the spectral theorem for symmetric matrices.
Proof
(Spectral bounds for the residual)
For the second statement, write , so . Symmetric diagonalization gives and . The claimed bounds follow.
Three distinct errors should be kept apart. The sweep decreases the energy of the finite system. The residual bounds its algebraic error only after the scale of and its smallest eigenvalue are accounted for. A separate consistency and stability argument is needed to compare with samples of the continuous solution.
Worked examples
Worked example 3.6.5
(One sequential sweep)
Take , and . Gauss–Seidel first sets , then uses that new value to set . A simultaneous Jacobi sweep would instead give . Solving the two equations gives , so neither first sweep is exact.
Concept lensAlgebraic
A sweep as a fixed matrix splitting
Write with diagonal, strictly lower and strictly upper triangular. A Gauss–Seidel sweep in increasing order is exactly , so the error obeys ; SOR replaces this by . Convergence from every start is equivalent to spectral radius below one. In the example, , so after the first sweep each error is multiplied by : indeed .
Worked example 3.6.6
(An over-relaxed sweep)
With the same system and start, choose . The first unrelaxed candidate is , so the relaxed value is . The second candidate uses this new value and equals ; relaxation from zero gives . At the first update the residual is , and the energy decrease formula gives . Indeed and .
Worked example 3.6.7
(A residual can be misleading)
For the unscaled one-dimensional Poisson matrix, , which tends to zero as the grid is refined. Taking proportional to the corresponding eigenvector produces . Thus the same absolute residual tolerance can allow a larger algebraic error on a finer grid. Scaling the equations changes the numerical residual even though it does not change the iterates; a meaningful stopping rule must state the scaling and norm.
Common mistakes and subtle points
Common mistake
(The admissible range is not a speed guarantee)
The interval guarantees convergence here because is symmetric positive definite; it does not promise that every such is faster than Gauss–Seidel, nor does the proof apply automatically to an arbitrary nonsymmetric convection matrix. At even the scalar equation alternates between and from zero, so the endpoint cannot be included.
Common mistake
(A small update is not an error certificate)
A small successive update by itself is not a universal error certificate; under-relaxation can make the update small merely by choosing a small . A residual criterion should be compared with an appropriate estimate of discretization error and must also include practical iteration limits.
For inhomogeneous boundaries, their contributions belong in before any sweep; they are not extra unknowns in the interior matrix. No formula here specifies an optimal relaxation parameter for a general matrix. Positive definiteness, finally, is not a technicality of the proof.
Counterexample mode
A symmetric matrix on which Gauss–Seidel diverges
Claim: Gauss–Seidel converges for every symmetric matrix with nonzero diagonal entries. Take
which is symmetric and invertible, with solution . From the first sweep sets and then ; the next sweep gives . In general the second coordinate is multiplied by in every sweep, so the iterates diverge. The hypothesis that fails is positive definiteness: has eigenvalues and , and gives . The energy is then unbounded below, so its descent proves nothing. The repaired statement is the theorem: symmetric and positive definite.
Quick check
Quick check
(In Gauss–Seidel, which first-coordinate value is used when updating the second coordinate of the same sweep?)
Solution · Answer
The newly computed first-coordinate value is used. In SOR it is the newly relaxed value, not the unrelaxed candidate.
Exercises
Quick check
(Starting from zero, perform two Gauss–Seidel sweeps on , . Compute the residual after the second sweep.)
Solution · Answer
The first sweep gives . The second gives and . Hence : the second equation is satisfied at the end of each sweep, but the first need not remain satisfied after the second coordinate changes.
Quick check
(For the scalar system , derive the SOR error recurrence and determine exactly when it converges from every initial value.)
Solution · Answer
The candidate is always , so and . Convergence from every starting value holds exactly when , equivalently .
Quick check
(Let and . For , calculate the residual, energy gap and the proposition's energy bound. Explain whether the bound is sharp for this particular vector.)
Solution · Answer
Here , , and the upper bound is . It is valid but not sharp for this vector. Equality is possible for a residual lying in the eigenspace for .