Elimination solves a linear system by changing its equations. A stationary iteration instead repeatedly improves a vector using a fixed update rule. For a sparse matrix, one sweep can use only its nonzero coefficients, avoiding the fill-in that can appear during factorization. But repeating a plausible update does not guarantee that its values approach the solution.
Jacobi and Gauss–Seidel start with the same rearranged equations and differ in which values a sweep reads. We will make that distinction precise, prove one sufficient convergence condition, and then answer a practical question: when does a small observed change actually certify a small solution error? Here “Jacobi” means the linear-system iteration, not the separate Jacobi rotation method for eigenvalues.
Rearrange each equation without hiding its dependencies
Let , , and assume each diagonal entry . We seek satisfying . Rearranging row gives
We number whole sweeps by . In Jacobi, every right-hand-side value comes from the previous vector. In Gauss–Seidel, rows are visited in order , and a row immediately uses values already updated during the current sweep.
Definition 10.1.1
(Two sweeps and their matrix splittings)
Write , where is diagonal, strictly lower triangular and strictly upper triangular. These matrices retain the actual signs of the entries of .
Jacobi uses
Gauss–Seidel uses
The triangular inverse notation describes the map. Implementing a Gauss–Seidel sweep means substitution, not explicitly constructing that inverse.
The matrix identities follow by moving the terms with new values to the left. Because and are invertible, either rule has a fixed point exactly when that point solves . This proves a correspondence between fixed points and solutions; it has not yet proved that a sequence converges to one.
A one-array update can silently change the algorithm
The following pseudocode describes one sweep, with nonzero diagonal entries as a precondition. It omits the outer stopping loop deliberately: a stopping claim will need the estimates derived below.
jacobi_sweep(A, b, old):
allocate next with n entries
for i = 1,...,n:
next[i] = (b[i] - sum(A[i,j] * old[j] for j != i)) / A[i,i]
return next
gauss_seidel_sweep(A, b, x):
for i = 1,...,n:
x[i] = (b[i] - sum(A[i,j] * x[j] for j != i)) / A[i,i]
return x
In the second sweep, entries with smaller indices are new and entries with larger indices are still old. Jacobi's separate outputs can be computed independently; Gauss–Seidel's chosen order has sequential dependencies.
Common mistake
(Overwriting the input array turns Jacobi into Gauss–Seidel)
Replacing old by a vector being overwritten in the first sweep implements Gauss–Seidel-style dependencies, not Jacobi, and the result also depends on the order in which rows are visited. A Jacobi sweep needs two arrays: one that is only read, and one that is only written.
With a sparse row representation, sum only stored nonzero off-diagonal entries. One sweep then costs work, including visiting rows and diagonal divisions. A dense implementation costs . The number of sweeps needed for an accuracy target is an additional cost; cheap sweeps do not imply a cheap solve.
Prove a sufficient condition that does not require symmetry
Use the vector norm and the induced matrix norm . The latter gives by applying the triangle inequality in each row.
Theorem 10.1.2
(Strict row diagonal dominance gives convergence)
Suppose
Then is nonsingular. For its unique solution , both Jacobi and the stated Gauss–Seidel ordering converge from every initial vector, with
This is a sufficient condition. It does not assert that every matrix failing it causes divergence, or that symmetry is required.
Proof
(First rule out a null vector, then contract the error)
If with , choose where . Row gives , contradicting strict row dominance. The square matrix is therefore nonsingular.
Subtract the solution's row equations from a Jacobi sweep. Each new error component is bounded by its row's off-diagonal ratio times the previous maximum error. Thus the entire new error norm is at most times the old one.
For Gauss–Seidel, let be the old maximum error. Induct through the sweep's rows, assuming the already updated errors are at most . The next row satisfies
because and the total off-diagonal ratio is at most . This proves the induction, including its first row where the lower-index sum is empty. Iterating the one-sweep bound proves the theorem.
The same arguments applied to any two input vectors, instead of an input and the solution, prove that each sweep map is a contraction with factor at most in the infinity norm.
Proof X-ray
Where strict dominance is used
Strictness enters twice, in two different places. In the null-vector argument it produces the contradiction , so a non-strict inequality would not exclude a null vector. In the contraction step it supplies the factor that makes the geometric bound go to zero. The one non-obvious move is the Gauss–Seidel induction: the freshly updated components are only known to have error at most , not , and it is the inequality that lets the row bound absorb this weaker information without losing the factor . Choosing the maximum norm is what makes each row a self-contained estimate, with no coupling between rows.
The proof does not compare the two methods' exact rates. A verified smaller value of or can give a better bound. Ordering also changes the Gauss–Seidel splitting. A statement about one matrix and one ordering should not be turned into a universal ranking of algorithms.
Follow the same system with the two dependency rules
Worked example 10.1.3
(A small system where Gauss–Seidel uses fresh information)
Take
The dominance bound is . Starting at , the sweeps give:
| Sweep k | Jacobi vector | Gauss–Seidel vector |
|---|---|---|
| 0 | ||
| 1 | ||
| 2 | ||
| 3 |
For example, the first Gauss–Seidel row gives ; the second immediately uses it to obtain . Jacobi's second row still sees the old zero and obtains .
The iteration matrices are
Their infinity norms are and . The smaller Gauss–Seidel norm improves its certified contraction factor for this example. The table itself is not a convergence proof for arbitrary data.
Concept lensAlgebraic
Convergence as a statement about the spectrum
The errors satisfy , so the iteration converges from every start exactly when the spectral radius satisfies . A bound in some induced norm is a sufficient certificate for this, not an equivalent one. For the infinity norm is , yet the eigenvalues are . In the worked system and .
Turn a step difference into a solution-error certificate
Theorem 10.1.4
(Step-based error certificate)
Let with , which may be the dominance bound or a sharper bound for the particular matrix, and let . With and the fixed point , for every ,
Proof
(Summing the geometric tail after the last step)
Differences of consecutive iterates satisfy . Therefore the th future step after iterate has norm at most . Since the iterates converge to , which lets us telescope those future steps:
If , the map is constant and the first sweep already reaches its fixed point; the zero bound remains correct for .
Proof X-ray
Why the sum starts at the first future step
The sum starts at and not at , because the current iterate already includes the step of length : only the steps that have not been taken contribute to the error. The contraction factor is used only through the relation between consecutive differences, so a sharper verified improves the certificate directly, while an unjustified voids it. The multiplier is what converts an observed step into a bound on the unobserved tail, and it blows up as .
For , a sufficient stopping condition for solution error at most is .
Common mistake
(A small step alone is not a certificate)
Stopping when is below a tolerance, without a justified contraction factor, certifies nothing: the multiplier can be large. For example, gives multiplier 99, so a step of certifies only error at most .
Bound a solution error using a residual and its scale
Strict row diagonal dominance also gives a different certificate, valid for any approximation , irrespective of how it was obtained.
Theorem 10.1.5
(Residual error certificate under strict dominance)
Let be strictly row diagonally dominant and define
Then
Proof
(Reading the error equation at its largest component)
Put , so , and choose an index with . The triangle inequality in that row gives . Move the off-diagonal term to the left and use the lower bound . This proof does not assume symmetry, positive definiteness or a particular iteration map.
Worked example 10.1.6
(A small residual with a small scale)
A residual by itself has a scale. For , , , the solution is , and the approximation has residual , of norm , but solution error 1. Here , so the stated bound correctly gives rather than treating the small residual as a small forward error.
Worked example 10.1.7
(Certifying the third Gauss–Seidel iterate)
For the worked Gauss–Seidel sequence, the third step difference is . Using the verified factor gives error at most . The actual error, known here only because we also have the exact solution, is . Using the looser shared factor would give instead. A valid certificate can be conservative, and improving its proven constant can matter.
A nonsingular system can still make an iteration diverge
Counterexample mode
Existence of a unique solution is not an iteration guarantee
Let and . The determinant is , so the unique solution is .
Jacobi from zero gives . Errors in the direction are multiplied by at every sweep. They grow rather than approach zero. The rearranged equations have the correct fixed point, but the update moves away from it.
Conversely, failure of the dominance test does not prove divergence. For , the Jacobi infinity norm is 2, yet . Every pair of sweeps reduces every error by , so the method converges from every start. A one-step norm bound can fail while a two-step argument succeeds.
Keep exact-arithmetic theorems separate from computed diagnostics
A program may compute a residual with rounding error, or produce sweeps that include arithmetic perturbations. The statements proved here concern the exact map and exact residual. A complete floating-point error certificate must also bound those perturbations; merely printing the word “residual” does not supply that bound.
For a sparse solve, an implementation can evaluate a fresh residual periodically rather than infer it from the newest step alone. The residual must use the same complete iterate in every row.
Common mistake
(Checking only the last equation of a sweep)
In Gauss–Seidel, the last equation visited is satisfied at the end of a sweep, because it was just solved for the new value, while earlier rows have become inexact again because later components changed. In the worked system the third iterate has second-row residual but first-row residual . A residual test that reads only the last row is therefore insufficient.
The two certificates have distinct assumptions: the step bound requires a verified contraction factor for the update map; the residual bound requires a justified bound translating residual to solution error, supplied here by strict row diagonal dominance. Neither follows merely from choosing a small numerical tolerance.
Exercises with solutions
Quick check
(In the worked system, explain why the first Jacobi vector is while the first Gauss–Seidel vector is . What change to the pseudocode would accidentally turn the first method into the second?)
Compare which value of the second row reads.
Solution · Answer
Both methods begin with the first component . Jacobi's second row uses old , giving . Gauss–Seidel uses the just-updated , giving . Writing Jacobi outputs into its input array and reading that modified array for later rows changes the dependencies; the stated separate old/next arrays prevent this.
Quick check
(At the third Jacobi iterate of the worked system, compute the step certificate with and the residual certificate with . Which one certifies error at most ?)
Compute and the residual separately.
Solution · Answer
The second iterate is , so . The step bound is .
The residual is and , giving the bound . Thus here the residual certificate proves the requested accuracy while the step certificate does not. The actual error is ; a failed sufficient bound does not mean the approximation is inaccurate.
Quick check
(For , prove Jacobi convergence using two sweeps. Derive a stopping bound at even iterate from the difference between iterates and , with .)
Compute and apply the step certificate to the two-sweep map.
Solution · Answer
The determinant of is , so its solution is unique. Here , so . The two-sweep affine map has contraction factor and the same unique fixed point. Its even subsequence therefore converges. The odd subsequence converges too, because it is obtained by applying the continuous map to the even subsequence.
Apply the step certificate to the two-sweep map, not to a single sweep. It gives . Using the two-sweep constant with a one-sweep difference would not be the proved result.
Quick check
(Let , , , and approximation . Find the exact solution, residual, error and . Why does a small residual alone fail to certify a small forward error?)
Divide the residual by the smallest diagonal scale.
Solution · Answer
The solution is , residual , and infinity-norm solution error is 1. Strict row dominance gives , so the residual certificate is , consistent with that error. The small residual is measured in a direction with a small matrix coefficient; dividing by a justified scale is essential.
Jacobi would solve this diagonal system in one exact sweep, because its iteration matrix is zero. That does not make the stated initial approximation accurate or justify stopping before a correction merely because its unscaled residual is small.