Motivation
Elimination produces a solution through a factorization. For a large sparse matrix, storing the factors can be much more expensive than storing the original nonzero entries. An iterative method instead improves an approximation using matrix-vector products and simpler solves. Whether this saves work depends on convergence: a cheap step repeated too many times is not an efficient solver.
Two viewpoints help organize the subject. A stationary method repeatedly applies one fixed error-propagation matrix. A Krylov method searches progressively larger spaces generated by the matrix and initial residual. For symmetric positive definite systems, conjugate gradients connects the second viewpoint with minimization of an energy. Preconditioning changes the geometry of that search through an auxiliary system that is easier to solve.
Definitions
Definition 7.1.1
(Error, residual, and stationary splitting)
Let with nonsingular real , and let denote its solution. For an approximation , define error and residual . Given a splitting with nonsingular , stationary iteration is
The inverse is notation; an implementation solves with . For , where is its diagonal and its strictly lower and upper parts, Jacobi takes , while Gauss–Seidel takes . Their iteration matrices are and . These definitions require the selected triangular or diagonal solve to be nonsingular.
Definition 7.1.2
(Spectral radius, positive definiteness, and energy)
The spectral radius is . A real symmetric matrix is positive definite if for every nonzero real . For such a matrix, is the energy norm and
Definition 7.1.3
(Krylov spaces and -conjugacy)
Define and for . Vectors are -conjugate when . This is orthogonality in the energy inner product, not ordinary Euclidean orthogonality.
Theorem/Proposition
Theorem 7.1.4
(Stationary convergence and a norm certificate)
Stationary iteration converges to for every initial vector if and only if . If an induced matrix norm satisfies , then
In particular, strict row diagonal dominance gives a Jacobi certificate in the infinity norm:
Theorem 7.1.5
(Conjugate-gradient minimization and convergence)
For symmetric positive definite , exact-arithmetic conjugate gradients produces the unique minimizer of over . Its nonzero search directions are mutually -conjugate and its residuals are mutually Euclidean orthogonal. It reaches the solution in at most the matrix dimension, absent earlier termination.
If the extreme eigenvalues are and , then
If , one step suffices for nonzero initial residual. The statements about orthogonality and finite termination refer to exact arithmetic.
Concept lensStructural
An iteration chooses a geometry
Stationary methods control repeated action of one error matrix. CG instead chooses the best point in a growing affine space in the energy norm. Preconditioning changes that geometry through a cheaper positive definite metric. These viewpoints explain why a successful splitting, a small residual, and a favorable eigenvalue distribution are related but distinct pieces of evidence.
The factor two makes the bound conservative for small . It also ignores favorable clustering of eigenvalues. Conversely, positive definiteness alone does not guarantee convergence of every stationary splitting, as a counterexample below demonstrates.
Proof sketch or proof idea
Matrix powers and contraction
Proof
(Jordan blocks and a geometric series)
The error equation gives . If every eigenvalue has modulus below one, complex Jordan form shows that each block power tends to zero. For a nonzero eigenvalue, its entries are combinations of binomial coefficients in times powers of that eigenvalue; exponential decay dominates these fixed-degree polynomial factors. A zero-eigenvalue block is nilpotent and eventually vanishes. Thus . Conversely, convergence for every real initial error implies that every column of tends to zero, hence the same holds on complex vectors. An eigenvector with contradicts this conclusion. This proves the spectral criterion, including nondiagonalizable matrices.
The norm certificate follows by submultiplicativity. Let . Then , and convergence gives . Bounding that geometric series gives . For Jacobi, the infinity matrix norm is precisely the largest absolute off-diagonal row sum divided by the corresponding diagonal magnitude. A failed norm certificate does not prove divergence: it only means this sufficient argument cannot decide.
Constructing conjugate gradients
Proof
(Induction on the short recurrence)
Start with and . If a residual is zero, stop. Otherwise use
Positive definiteness makes each nonzero-direction denominator positive. Here is why the short recurrence enforces the larger-space minimization. Inductively suppose the current directions span and are conjugate, while is orthogonal to the earlier directions. Then . The chosen makes orthogonal to ; conjugacy makes it orthogonal to all earlier directions too.
For , use . Both residuals belong to , so . For the remaining direction,
Thus the stated cancels that product, proving conjugacy of with every preceding direction. The new residual belongs to and is orthogonal to . If nonzero, it supplies a new independent vector, so the enlarged directions span the next Krylov space. This closes the induction and also proves mutual residual orthogonality.
The gradient of is . Orthogonality of the residual to a search space is exactly the first-order condition for minimizing this strictly convex quadratic on the corresponding affine space. The energy identity makes the minimizer unique. At most the dimension many nonzero mutually conjugate directions can exist, proving exact finite termination.
Proof X-ray
Three invariants, two coefficients
The induction carries three statements together: the directions span , they are mutually -conjugate, and is orthogonal to . Each coefficient enforces exactly one new relation. The step length is the only choice making ; orthogonality to earlier directions then follows from conjugacy. Symmetry of is used at that point, to read as . The coefficient enforces conjugacy with only.
The non-obvious move is why conjugacy with costs nothing. Each is a difference of two residuals lying in , and is orthogonal to that whole space. The Krylov property that maps into is what replaces a full Gram–Schmidt sweep by a two-term recurrence. Positive definiteness is used twice: makes defined, and strict convexity of turns the orthogonality condition into a unique minimizer. The induction closes because a nonzero , lying in but orthogonal to , enlarges the span by exactly one dimension.
The spectral error bound
Proof
(A shifted and scaled Chebyshev polynomial)
Any vector in has error for some polynomial of degree at most with , since . Energy minimization and orthogonal diagonalization give
For , choose
The numerator has magnitude at most one on the spectral interval. For , the Chebyshev recurrence gives , where . At the displayed denominator's argument, . Thus the reciprocal denominator is at most , giving the result. If , the matrix is by the spectral theorem, and the first step solves the system. This bound is an upper estimate rather than an exact prediction of iteration counts.
Preconditioning changes the energy geometry
Choose a symmetric positive definite matrix that is cheap to solve with. Setting transforms the system to
The transformed matrix remains symmetric positive definite. Applying CG there yields preconditioned CG without forming square roots: solve , use , and use with initial . The relevant condition number is that of , not the Euclidean condition number of a generally nonsymmetric written matrix . A good preconditioner balances cheap solves against improved spectral structure. Taking gives one-step convergence but requires the original solve, so it is not a useful general algorithm.
A stopping rule should state both its scale and its meaning. Comparing the actual residual norm with an absolute tolerance is meaningful when the units of the right-hand side are fixed. A relative criterion based on the norm of the right-hand side permits comparisons across rescaled problems, but requires an absolute alternative when that right-hand side is zero or very small. Neither choice converts residual accuracy into solution accuracy without information about the inverse matrix. For CG, the energy norm in the theorem is useful for analysis but generally cannot be evaluated from the unknown solution during the computation.
Cost matters alongside the spectral bound. Each basic CG step uses one matrix-vector product, vector updates, and scalar inner products; preconditioned CG also uses an auxiliary solve. For sparse matrices the product may scale with the number of nonzero entries, while communication needed for inner products can dominate in parallel computing. These observations explain why reducing iteration count is only one criterion for choosing a preconditioner. An auxiliary factorization can be worthwhile for many right-hand sides but expensive for a single solve. Such engineering decisions should be informed by measured costs rather than inferred from the condition number alone.
Worked examples
Worked example 7.1.6
(Jacobi and Gauss–Seidel on a sparse pair)
For and , the solution is . Jacobi has , with . Starting from zero gives and . Gauss–Seidel uses the newly updated first component, giving already after one sweep. This example compares actual steps; it is not a universal ranking of the two methods.
Worked example 7.1.7
(Two exact CG steps)
Let , , and . Then , , and . Next and . The second step length is , giving . The residuals have zero dot product; the directions have zero -inner product. These different orthogonalities can be checked independently.
Worked example 7.1.8
(A diagonal preconditioner)
For the same diagonal system, choose . Solving with it is just componentwise division, and , so preconditioned CG solves in one step. For a general sparse matrix, using only its positive diagonal remains inexpensive but need not produce an identity or a small condition number. The example explains the mechanism; it does not establish a uniform benefit for diagonal preconditioning.
Common mistakes
Counterexample mode
Positive definiteness does not guarantee Jacobi convergence
Take the three-by-three matrix with diagonal entries one and every off-diagonal entry . Its eigenvalues are , so it is symmetric positive definite. Jacobi's iteration matrix has zero diagonal and off-diagonal entries , hence eigenvalues . Along the all-ones error direction, errors grow by magnitude each step. The SPD hypothesis supports CG, but not this Jacobi splitting.
Common mistake
(Reading a small residual as a small error)
The bound involves conditioning. For and error , the residual has norm while the error has norm one; the bound is attained. Likewise, a small change between iterates becomes an error bound only through a contraction certificate.
Common mistake
(Treating exact-arithmetic CG identities as hardware guarantees)
Finite-precision CG loses exact orthogonality and can take more than the dimension many iterations. Its recursively updated residual may also drift from . Recompute the actual residual at a justified stopping checkpoint; the finite-termination theorem is not an iteration limit for a computer.
Summary
Stationary convergence is equivalent to spectral radius below one; a contracting norm gives computable error certificates. Exact CG minimizes energy over Krylov spaces, with conjugate directions and a spectral convergence bound. SPD preconditioning transfers that analysis to a transformed system. Conditioning and finite arithmetic remain essential when deciding whether a numerical stopping test certifies the original equation.
Exercises
Quick check
(For , find the Jacobi iteration matrix, its infinity norm, and its spectral radius. If two consecutive iterates differ by at most in infinity norm, give the contraction-based current error bound.)
; scale the off-diagonal entries by the row diagonal.
Solution · Answer
. Its infinity norm is and its eigenvalues are , giving spectral radius . The current error bound is times the iterate change, hence . The spectral radius is smaller than this norm certificate, but it does not replace the norm in that particular bound.
Quick check
(Give a matrix with but . Explain why its stationary iteration nevertheless converges and why a large first step need not contradict convergence.)
A nilpotent matrix has spectral radius zero.
Solution · Answer
Take . Its only eigenvalue is zero, while its infinity norm is two. Since , every error vanishes after at most two steps. Some errors grow at the first step before becoming zero. The spectral criterion permits transient growth; a contraction estimate in the selected norm would forbid it.
Quick check
(For SPD with eigenvalues in , use the theorem to bound the energy-error ratio after six CG steps. Does the bound assert equality or finite-precision termination?)
With , .
Solution · Answer
gives ratio at most . It is an upper bound in exact arithmetic, potentially very conservative. It neither asserts equality nor guarantees that a finite-precision implementation will preserve the exact residual and conjugacy identities.
Quick check
(Let and . Find the transformed matrix, its condition number, and the exact-arithmetic preconditioned-CG step count for nonzero residual. Explain why the square-root formulation is mainly an analysis device.)
Here is diagonal.
Solution · Answer
, so . Its condition number is one, and one step solves any nonzero residual in exact arithmetic. The implementation uses solves with and inner products involving ; it need not construct a matrix square root.