Why change the linear system?
A finite-element mesh may improve the approximation while producing a poorly conditioned stiffness matrix. Conjugate gradients (CG) can solve a symmetric positive-definite (SPD) system using matrix-vector products, but its iteration count can still grow with the spread of the eigenvalues. A preconditioner changes the geometry of the solve so that this spread may be reduced. It is useful only if applying the change is cheaper than the work it saves.
Let be SPD, , and let be a fixed SPD matrix. We write to mean solving ; one need not construct an inverse. The solution of is . All identities and termination claims below are in exact arithmetic. The earlier CG result gives minimization in the energy norm .
Definition 1.5.1
(Symmetric preconditioning)
The matrix has a symmetric positive-definite square root. Set
Then is equivalent to , and is SPD because for every nonzero .
This is a conceptual construction: a practical implementation applies and solves with , without forming . The nonsymmetric-looking matrix is similar to , so it has positive real eigenvalues; it is generally not symmetric in the Euclidean inner product. Applying the ordinary Euclidean CG recurrence to it without changing inner products is therefore not justified.
Deriving the implementable recurrence
Write and . If , the initial vector is already the solution. Otherwise set and . While , compute
If , stop. Otherwise solve and set
The recurrence is ordinary CG for , rewritten in the original variables.
Lemma 1.5.2
(Equivalence with CG on the transformed system)
Run ordinary CG on from , with residuals and search directions . Then for every before termination
the two methods use the same and , and they stop at the same step.
Proof
(Induction on the three transformed quantities)
For , , and . Suppose the three relations hold at step . Then
so the ordinary CG step size equals in (1). Hence and . Because is invertible, exactly when , so the stopping events coincide. Otherwise the ordinary coefficient equals in (2), and .
Proof X-ray
Where the recurrence comes from
The induction carries three relations at once, and they transform in two different ways: iterates and search directions are multiplied by , residuals by . This mismatch is exactly what makes the method implementable. Each inner product that ordinary CG needs, and , becomes or , in which the square roots cancel; the only new operation is the solve with for .
Symmetry and positive definiteness of are used twice: to have a real symmetric square root at all, and to make positive whenever , which keeps defined. The argument closes because invertibility of makes the two stopping events identical, so the equivalence holds for the whole run and not only up to some step.
SPD of makes whenever ; SPD of and the CG construction make before termination. Thus the displayed divisions are legitimate. The recurrence requires one -product and one -solve per nonterminal iteration, in addition to vector operations and inner products. A dense or costly preconditioner can outweigh a reduction in iterations.
Theorem 1.5.3
(Minimization, termination and the condition-number bound)
With fixed SPD and , and , preconditioned CG produces the unique minimizer of over
until it terminates. It reaches in at most iterations. If and , then
If , one iteration suffices.
Proof
(Transfer, then a Chebyshev polynomial)
The equivalence above transfers ordinary CG's Krylov-space minimization and finite termination from to : . To obtain (3), CG minimizes over all with and . Diagonalizing bounds the error by times the initial -norm, where and . Choosing the scaled Chebyshev polynomial
and using on gives the factor in (3): for , the denominator is . If , then , so the first line minimization gives the solution. The bound depends only on the extreme eigenvalues and can be pessimistic when eigenvalues cluster; it does not guarantee that the total computing time is smaller.
A complete two-step calculation
Worked example 1.5.4
(A diagonal preconditioner)
Take , , and . Then , , , and . Thus and
Solving with gives and . Hence and . Now , so and . Direct multiplication confirms . Here has condition number , while has condition number .
The initial residual is not necessarily the first search direction: it is the preconditioned residual. The norm minimized at each step is the -norm of the error, not generally the Euclidean norm of the residual. A smaller condition number in the transformed system says nothing by itself about the cost of solving with . The next two examples show what the condition number does and does not measure.
Worked example 1.5.5
(Jacobi scaling of a coupled matrix)
Let and take the diagonal (Jacobi) preconditioner . The eigenvalues of are and , so . With ,
The factor in (3) drops from to , and applying costs one division per component. Since , both methods terminate in at most two steps in exact arithmetic; what carries over to large matrices is the comparison of factors.
Worked example 1.5.6
(Two distinct eigenvalues defeat the bound)
Take , , and . Here and the factor in (3) is , so after two steps (3) only guarantees , which says nothing. Yet . By the theorem, minimizes over polynomials of degree at most two with ; the polynomial vanishes at both eigenvalues, so and the minimum is zero. Concretely, , , and ; the second step lands on . The bound sees only the extreme eigenvalues, so clustering is invisible to it.
Common mistake
(A stopping test on the preconditioned residual depends on the scale of )
The quantity is computed anyway, so it is tempting to stop once is small. Replacing by with leaves every iterate unchanged but divides by ; the same iterate then passes or fails a fixed tolerance according to an arbitrary scale. Test against , or use only together with a valid lower bound for , as in the residual certificate below.
Counterexample mode
Why positivity of the preconditioner matters
Let , and . Then although . Formula (1) already loses the positive quantity on which the CG derivation relies. Invertibility and symmetry of alone are insufficient.
Practice with solutions
Quick check
(Exact preconditioner: let . How many steps are required from an arbitrary ?)
Compute .
Solution · Answer
, so at most one. Equivalently , and , so . This is usually not an economical algorithm: the preconditioner solve is the original problem.
Quick check
(Scaling: replace by , where . What happens to the transformed condition number and to the iterates?)
Track how , and change.
Solution · Answer
becomes , scaling all eigenvalues by and leaving their ratio unchanged. In exact arithmetic the iterates also agree: the scaled and are times the originals, is divided by , and each is times its original value, so is unchanged; each is unchanged.
Quick check
(Residual certificate: show that .)
Transform the error by .
Solution · Answer
With and , the left side is . Since , also . Diagonalization gives , because each eigenvalue satisfies . A useful numerical certificate needs a valid lower eigenvalue bound.
Quick check
(A misleading left product: for and , calculate .)
Divide each row of by the corresponding diagonal entry of .
Solution · Answer
It is , which is not symmetric, even though both and are SPD. The symmetric transform or the equivalent preconditioned recurrence is needed.
The analysis assumes exact applications of a fixed SPD and exact arithmetic. Roundoff, inexact or varying inner solves, practical stopping rules, construction of scalable preconditioners and measured performance require additional analysis.