A large sparse system may be expensive to factor because elimination can create new nonzero entries. An iterative method instead repeatedly updates an approximate solution using the original equations. This can exploit sparsity, but an update rule is not automatically convergent. The matrix, the order of updates and any relaxation parameter all affect the iteration.
Let have nonzero diagonal entries and let . Write , where is diagonal and are strictly lower and upper triangular. The signs of are exactly those in ; some texts define them with the opposite sign. A fixed solution satisfies . When we discuss convergence to a unique solution, nonsingularity is part of the hypotheses or follows from them.
Three ways to update
Definition 3.1.1
(Jacobi iteration)
Jacobi computes every new component using only the previous iterate:
Definition 3.1.2
(Gauss–Seidel iteration)
Gauss–Seidel uses the new components as soon as they are available, in the order :
The inverse in this expression describes a triangular solve; an implementation need not form it. Changing the ordering generally changes and hence the iteration. Jacobi's component updates can be computed simultaneously, whereas a Gauss–Seidel sweep uses newly updated values.
Definition 3.1.3
(Successive over-relaxation (SOR))
Successive over-relaxation (SOR) replaces each old component by a weighted move toward its current Gauss–Seidel value. For a real parameter , its component formula is
In matrix form, , where
is nonsingular because it is triangular with the same nonzero diagonal as . At , SOR is Gauss–Seidel; at , it makes no change. The term “over-relaxation” usually refers to , while is under-relaxation.
The spectral-radius criterion
For any stationary iteration whose fixed point is , the error satisfies
Theorem 3.1.4
(Spectral-radius criterion)
In finite dimensions, the iteration converges to for every starting vector if and only if , where is the maximum absolute value of the eigenvalues of .
Proof
(Powers of through the Jordan form)
If , a complex Jordan decomposition expresses as a finite combination of terms bounded by polynomials in times for eigenvalues ; each tends to zero. Hence . Conversely, if an eigenvalue has modulus at least one, the powers cannot tend to zero on a corresponding complex eigenvector. If all real starting vectors converged, linearity would also make powers tend to zero on every complex vector, a contradiction.
When , is not an eigenvalue of , so is invertible and the fixed point exists uniquely as . The criterion concerns every starting vector. A particular initial error may have no component in an unstable direction and can behave better. Also, in an induced norm is sufficient, but a norm greater than one does not prove divergence: powers may still decay if .
Common mistake
(Reading a large norm as divergence)
Let . Then , yet , so for every starting vector and the iteration converges after two steps. The criterion concerns , which is here, not any single norm: a norm below one is sufficient, but a norm above one proves nothing.
Proposition 3.1.5
(Jacobi under strict row diagonal dominance)
If for every row, then is nonsingular, , and Jacobi converges from every starting point.
Proof
(Row sums and the largest component)
The entries of row of have absolute sum , so and ; the spectral-radius criterion gives convergence. If and , row gives , a contradiction. Hence is nonsingular.
Gauss–Seidel under the same hypothesis. The Jacobi bound is a direct row-sum estimate because the entries of are visible. The Gauss–Seidel matrix contains an inverse, so its rows cannot be read off in the same way. The useful idea is to bound through the triangular equations that define it, without forming the inverse. For each row split the off-diagonal weight into the parts before and after the diagonal:
Strict row diagonal dominance says exactly that for every , and .
Theorem 3.1.6
(Gauss–Seidel under strict row diagonal dominance)
If is strictly row diagonally dominant, then
Consequently Gauss–Seidel converges to the unique solution from every starting vector, with .
Proof
(Bounding one sweep row by row)
Each , so every denominator is positive and is defined. Fix with and let . Then , whose row is
This is one Gauss–Seidel sweep applied to the error : the entries with are the components already updated in the sweep. If there is nothing to prove. Otherwise choose with . Divide row by and use and :
Taking the maximum over unit vectors gives . For the comparison with Jacobi, note that for every row
hence . Since an induced norm bounds the spectral radius, , and the spectral-radius theorem gives convergence. The dominance argument above shows that is nonsingular, so the limit is the unique solution. Applying the norm bound once per sweep gives the stated error estimate.
Proof X-ray
Where the updated components enter the estimate
The proof explains the role of the newly computed values. In row , the updated components enter with total weight , and they are controlled by the same unknown quantity that is being estimated. That term is moved to the left-hand side, and the result is a factor no larger than the Jacobi row sum. The statement compares worst-case one-sweep factors in the max norm. By itself it does not assert for every dominant matrix, nor that Gauss–Seidel produces the smaller error after every sweep from every start. If the equations and unknowns are reordered by the same permutation, strict row dominance is preserved, so convergence holds for every such ordering. The value of , however, depends on which entries fall before the diagonal.
Worked example 3.1.7
(The dominance bound on a concrete matrix)
For the matrix of the two-by-two comparison below, and , so it is strictly row dominant. Its row weights are , , , . Therefore and . The explicit matrix computed below has absolute row sums and , so and the bound is attained in this example.
Counterexample mode
Gauss–Seidel need not beat Jacobi
Without some hypothesis of this kind, neither method dominates the other, so the expectation that Gauss–Seidel is always at least as good as Jacobi is false. A positive definite example in which Jacobi diverges while Gauss–Seidel converges appears later in this note. In the opposite direction, consider
Here , and no row is dominant. Expanding along the first row gives , so : in exact arithmetic Jacobi reaches the solution after at most three sweeps from every start. The Gauss–Seidel matrix, obtained by solving row by row, is upper triangular with eigenvalues . The initial error satisfies , so this error doubles at every sweep.
Why Gauss–Seidel and SOR converge for positive definite matrices
Assume now that is symmetric positive definite (SPD): for every nonzero . Then is nonsingular and every . Consider the quadratic
For an update to coordinate , let be the residual computed from the current mixed vector: earlier coordinates have already been updated in this sweep. SOR changes that coordinate by . Expanding the quadratic gives
For , every coordinate update decreases unless its current residual component is zero. A complete sweep decreases strictly unless the starting vector already solves : if every update has zero decrease, every residual encountered is zero, no coordinate changes, and the original residual is zero.
Theorem 3.1.8
(SOR for symmetric positive definite matrices)
If is SPD and , SOR converges to the unique solution from every starting vector. The result holds for any fixed coordinate ordering; in particular, Gauss–Seidel converges because it is the case .
Proof
(Strict energy decrease in every sweep)
Since , . A full sweep acts linearly on the error as . The preceding calculation shows for every nonzero error, where . On the compact unit sphere in this norm, the continuous ratio attains a maximum . Consequently . This argument uses finite dimensionality to turn strict decrease for each vector into one common contraction factor. It proves that such a exists but does not give a computable numerical rate.
The parameter restriction is a sufficient guarantee for SPD matrices, not a universal assertion about every matrix. For , : at nonzero errors alternate forever, and for or their magnitude grows. At they remain unchanged. Even within , an arbitrary choice is not guaranteed to be faster than Gauss–Seidel.
Common mistake
(Assuming over-relaxation always speeds convergence)
In the two-by-two comparison below, gives , which is worse than the value of Gauss–Seidel for the same matrix. The theorem guarantees convergence for ; it does not say that is faster. A good has to be chosen for the matrix at hand.
A worked comparison
Worked example 3.1.9
(Three iterations on a two-by-two system)
Take
is SPD since for nonzero . Starting from zero, one Jacobi sweep gives ; one Gauss–Seidel sweep gives . Their error matrices and spectral radii are
For SOR with , the first sweep from zero is and
Its conjugate eigenvalues have product and hence modulus . The three spectral radii are all below one, but this choice of over-relaxation has a larger asymptotic factor than Gauss–Seidel. Spectral radius describes the worst-case asymptotic geometric factor; particular initial errors can decay faster, and it does not necessarily predict which error is smaller after one finite sweep.
Worked example 3.1.10
(One SOR coordinate update lowers )
Take , and , and update the first coordinate. The residual component is and . With the change is , and
in agreement with . For we get and the decrease , the largest possible along this coordinate. At the endpoint , and : no decrease at all, which is why the strict-decrease argument needs the open interval .
Positive definiteness alone does not guarantee Jacobi convergence
Counterexample mode
Positive definiteness does not make Jacobi converge
Let be the matrix with diagonal entries 1 and every off-diagonal entry . Its eigenvalues are , so it is SPD. Jacobi has and , with eigenvalues . Taking the initial error makes each sweep multiply that error by , so it diverges. This does not contradict the SPD theorem above: that theorem applies to Gauss–Seidel and SOR, not to Jacobi. Strict diagonal dominance is a sufficient Jacobi condition, and this matrix fails it.
Residuals and stopping
The residual can be computed without knowing . It satisfies , so for nonsingular , in compatible norms. A small residual certifies a small forward error only when the scale and conditioning permit it. In practice one can monitor a scaled residual and impose a maximum iteration count; a small change between successive iterates alone may reflect stagnation. Finite precision also limits attainable accuracy, and the exact-arithmetic convergence proofs do not specify a universal stopping tolerance.
Common mistake
(A small residual is not a small error)
Let and . Then has norm although . The bound is attained here, since .
Practice with solutions
Quick check
(For the two-by-two example, compute the second Jacobi iterate from zero and verify that the fixed point is .)
Apply the Jacobi formula to .
Solution · Answer
From , the next Jacobi update is . Substitution of into verifies the fixed point.
Quick check
(For SPD , what happens to in one SOR coordinate update when ? When ?)
Compare with the minimizing step along one coordinate.
Solution · Answer
At , the change is , the minimum along that coordinate. At the change is zero, so the strict-decrease proof does not apply.
Quick check
(Let and . Find the error after SOR sweeps and its convergence factor.)
What is when ?
Solution · Answer
, hence and the factor is .
Quick check
(Can Jacobi fail for an SPD matrix? Give a specific matrix and initial error.)
Look for an SPD matrix with an eigenvalue of below .
Solution · Answer
The SPD matrix above has Jacobi eigenvalue on , so that initial error diverges.
Quick check
(For , compute , and . Then find , its max-norm and both spectral radii. Do equal one-sweep norm bounds imply equal asymptotic factors?)
Solve row by row.
Solution · Answer
, , , , so . Solving gives first row and second row , hence . Its eigenvalues are , so , while has eigenvalues and . Equal one-sweep norm bounds therefore do not imply equal asymptotic factors.
Quick check
(In the example above that is not diagonally dominant, verify by performing one Gauss–Seidel sweep on that error with zero right-hand side.)
Substitute row by row, using the new values.
Solution · Answer
With , the sweep gives , then , then . Thus .