Motivation
For a large sparse linear system, storing a dense factorization can be much more expensive than multiplying the matrix by a vector. An iterative method instead builds a sequence of approximations from matrix–vector products. The conjugate-gradient method uses information gathered so far to choose a new search direction, rather than applying one fixed stationary iteration matrix at every step.
Its special structure depends on the matrix. For a real symmetric positive-definite matrix, solving is equivalent to minimizing a strictly convex quadratic. Conjugate gradients chooses mutually orthogonal directions in the matrix's energy inner product and produces the best approximation in an expanding Krylov space. These statements are exact-arithmetic theorems. A real implementation also needs stopping, scaling and rounding-error decisions.
The energy viewpoint
Definition 3.2.1
(Symmetric positive definiteness and the energy norm)
Let be symmetric positive definite (SPD): and for every nonzero . Define
The unique solution is the unique minimizer of . Indeed, for ,
The residual is the negative gradient of and satisfies .
A small residual and a small solution error are different statements. In the Euclidean norm, ; an ill-conditioned matrix can magnify a residual. The energy norm weights directions differently, according to . A theorem about minimizing energy error should therefore not be quoted as saying that every Euclidean error component decreases at every step.
Definition 3.2.2
(Krylov spaces and conjugacy)
Starting from and , define
Nonzero vectors are -conjugate if whenever . Positive definiteness makes an -conjugate family linearly independent. The affine space contains all corrections built from polynomials in of degree below applied to the initial residual.
The algorithm and what it guarantees
If , already solves the system and no iteration is needed. Otherwise put . For , while , compute
If , stop. Otherwise set
The matrix is used through ; the algorithm need not form . The denominator is positive before termination because is SPD and, as the induction below proves, the search direction is nonzero. The stopping check avoids a zero denominator after an exact solution has already been found.
Theorem 3.2.3
(Orthogonality, minimization and finite termination)
In exact arithmetic, until termination, the residuals are mutually Euclidean-orthogonal and the directions are mutually -conjugate. After steps without earlier termination,
and uniquely minimizes over . The algorithm reaches the exact solution in at most steps.
Theorem 3.2.4
(A condition-number convergence bound)
Let be the extreme eigenvalues of , and let . In exact arithmetic, for every before termination,
If , then is a positive multiple of the identity and conjugate gradients terminates in at most one step. The displayed estimate is a worst-case bound, not a prediction that the actual error falls by exactly its factor at each iteration.
Concept lensAnalytic
The same iterate as an optimal polynomial
Write , so . Every point of has error for a polynomial of degree at most with , and every such polynomial occurs. Hence is the point whose polynomial minimizes under this constraint. In an orthonormal eigenbasis with , this quantity is . Conjugate gradients is therefore a polynomial-approximation problem on the spectrum of : the constraint is , and should be small at the eigenvalues that carry weight in .
Why the short recurrence works
Proof
(Orthogonality and energy minimization)
We prove the relations together by induction. At step the invariants are: the directions are nonzero and pairwise -conjugate; is orthogonal to the preceding directions; ; and each constructed so far belongs to . At , , conjugacy and preceding orthogonality are vacuous, , and both vectors lie in . In particular . Suppose the invariants hold at step . Because when , . Therefore the chosen step satisfies
For , the induction hypotheses give . Each earlier residual is a linear combination of its corresponding direction and the preceding one, so is also orthogonal to .
The update also preserves the true-residual identity: . To check conjugacy of the next direction, use . For , residual orthogonality gives , and . For ,
The chosen cancels these terms in . Also when , since . This completes the induction and justifies each positive denominator.
The Krylov memberships follow inductively too: ; if , then and . The first directions are linearly independent and lie in the at-most--dimensional space , so its dimension is and they span it. Thus and . For any ,
The Pythagorean identity in the inner product shows that adding any nonzero to increases the energy error, proving unique minimization. At most nonzero conjugate directions exist; after steps the residual is orthogonal to all of and is zero. If it becomes zero sooner, the algorithm already has the exact solution.
Proof X-ray
Why only one previous direction is needed
A general projection method might remove components along every previous direction. Here the identity turns older conjugacy conditions into residual orthogonality. Only the most recent direction needs the explicit correction. This economy is a consequence of symmetry and the coupled invariants, not a property of arbitrary iterative methods.
Proof
(From the Krylov minimum to the spectral bound)
Put . Since , any correction in gives an error for some polynomial of degree at most with . Conversely each such polynomial gives a correction in the Krylov space. Diagonalize in an orthonormal eigenbasis and write . Since and the spectrum lies in ,
The minimization theorem gives for every admissible polynomial, so any one of them supplies an upper bound. For , choose
where . The numerator has absolute value at most one on the spectral interval, and . For , writing gives . At the denominator's argument, . Hence the reciprocal denominator is at most , proving the bound. The eigenvalue interval bound can be conservative, especially when eigenvalues cluster or the initial error has no component in a difficult eigendirection. In fact, if has nonzero components in eigenspaces for only distinct eigenvalues , then gives . Krylov optimality therefore forces exact termination in at most steps, possibly earlier. This refined statement also depends on exact arithmetic.
Worked examples
Worked example 3.2.5
(Two iterations on a diagonal system)
Take , and . Then and
Thus , which satisfies . The next step has , giving
The residuals are orthogonal as well: . This exact termination in two steps illustrates the dimension theorem; in floating-point arithmetic the computed residual may not be exactly zero after two steps.
Worked example 3.2.6
(A repeated eigenvalue can give earlier termination)
Let with arbitrary and . If , then and . The method solves the system in one step, regardless of dimension. More generally, finite termination can occur before steps when the Krylov space reaches the needed solution correction earlier; counting distinct eigenvalues alone is not an iteration guarantee in floating-point arithmetic.
Worked example 3.2.7
(Energy error versus residual)
Let and suppose a candidate error is . Then , , , and . A different error has the same residual norm one but Euclidean error one and energy error one. The direction of a residual relative to the spectrum matters; a single unscaled residual norm does not directly report a coordinatewise error.
Counterexample mode
Symmetry without positive definiteness is insufficient
For , and , the system has the unique solution . Yet gives , so the very first conjugate-gradient step is undefined. The quadratic is indefinite and unbounded below; the solution is a saddle point, not a minimizer. Nonsingularity and symmetry do not replace positive definiteness.
Common mistakes
Common mistake
(Treating finite termination as a floating-point promise)
The orthogonality, exact zero residual and -step termination statements use exact arithmetic. Rounding can destroy conjugacy and make the recursively updated residual differ from the explicitly computed . A practical stopping rule should account for scaling and the difference between a residual and an error; the exact proof alone does not supply a universal floating-point stopping tolerance.
Common mistake
(Using the theorem for an arbitrary nonsymmetric system)
The algorithm and energy argument here require to be symmetric positive definite. Other Krylov methods address other matrices with different invariants and convergence statements. Preconditioning also needs its own hypotheses: a left-preconditioned operator need not be symmetric in the ordinary Euclidean inner product, even when its components are SPD.
Summary
Conjugate gradients combines matrix–vector products through a short recurrence. In exact arithmetic, residual orthogonality and -conjugacy produce the energy-minimizing point in each Krylov space and guarantee termination in at most steps. The spectral bound explains the role of condition number, while implementation and rounding behavior require separate analysis.
Exercises
Quick check
(For , and , compute the first CG step, including and .)
Start from .
Solution · Answer
, so . Hence and .
Quick check
(For , and , take the first step as , . Compute , , and , and verify that .)
Use .
Solution · Answer
and . Its -inner product with is . Also , so . Therefore , which is the exact solution.
Quick check
(Suppose an SPD matrix has . Compute the factor in the energy bound after steps and explain why it is not necessarily the actual error ratio.)
Compute the ratio first.
Solution · Answer
Here , so the upper-bound factor is . The actual ratio depends on the eigenvalues, initial error and exact arithmetic; the inequality need not be sharp for this instance.
Quick check
(Let with , and suppose the residual is . Find the corresponding error and explain the role of .)
Use .
Solution · Answer
Since , the error is . The residual norm is even though the error norm is one. A small eigenvalue can make a small residual correspond to a much larger error.