Why solve without an inverse?
A large least-squares or regularized model can lead to , where has many rows but multiplication by is affordable. Explicitly storing may be infeasible even when is sparse. The conjugate-gradient (CG) method builds approximate solutions using matrix–vector products, vector updates and inner products. It does not need the entries of an inverse. Its guarantees require a particular class of matrices, and we assume exact arithmetic for the derivation, discussing finite precision separately.
Definition 4.5.1
(Symmetric positive-definite matrix and -inner product)
A real matrix is symmetric positive definite (SPD) if and for every nonzero . For SPD , the -inner product is ; vectors are -orthogonal (conjugate) if .
The linear system is equivalent to minimizing a quadratic, and this reformulation drives every step of the method.
Lemma 4.5.2
(The system as a quadratic minimization)
Let be SPD, and . Then and, for every ,
Hence is the unique minimizer of , and the residual is the negative gradient.
Proof
(Complete the square)
Symmetry gives , so . Using and ,
By positive definiteness the right side is positive unless .
Moving only in the residual direction gives steepest descent, but successive steps can undo earlier progress. CG chooses directions that are -orthogonal; minimizing along one such direction does not disturb stationarity along earlier directions.
The recurrence
Start from any , set and . If , stop. Otherwise compute
If , stop. Otherwise set
A nonzero direction has by positive definiteness; the denominator is not a tuning parameter. The recurrence for follows from , so only one new product is needed per iteration after initialization. This does not include the cost of generating or storing , or of communication for distributed inner products.
Theorem 4.5.3
(Exact-arithmetic CG)
For SPD , until the method terminates, the directions are nonzero and mutually -orthogonal, and is orthogonal to all previous directions. The iterate uniquely minimizes over . The method reaches the exact solution in at most iterations.
Proof
(Induction on the directions)
Inductively suppose are mutually -orthogonal and is orthogonal to . Since for , we have ; this is also true at . The derivative of is , which vanishes at . Moreover,
Before stopping, is nonzero: otherwise its inner product with would be zero, whereas that inner product equals . For , the recurrence and orthogonality of to prior directions imply , since both residuals on the right lie in their span. For , the same recurrence and residual orthogonality give . As , the displayed makes ; for both terms in vanish. This completes the induction.
The directional derivatives at vanish on the stated span because is orthogonal to its basis. Strict positive definiteness makes that stationary point its unique minimizer. Nonzero mutually -orthogonal vectors are linearly independent, so there can be at most of them. If directions have been taken, the residual is orthogonal to a basis of and hence is zero.
The proof explicitly enforces only one orthogonality per step, yet concludes orthogonality to every earlier direction.
Proof X-ray
One correction buys all the old orthogonality
Positive definiteness enters twice: it makes the denominator of each step size positive, and it turns a stationary point on the search space into the unique minimizer. Symmetry is what lets the conditions be read in either order, so that the -orthogonality of two directions is one condition, not two. The key move is the identity , which writes times an old direction as a difference of two old residuals. Both residuals lie in the span of earlier directions, to which the new residual is already orthogonal, so the new direction is automatically conjugate to all directions except the latest; the coefficient only has to remove that single component. This is why CG needs a short recurrence and not a full Gram–Schmidt sweep over stored directions. The argument closes by counting: nonzero conjugate directions are independent, so at most of them exist, and a residual orthogonal to independent vectors is zero.
Worked example 4.5.4
(Two directions, not two independent guesses)
Take , , and . Then , , and . Hence and . Now and . Check . Since , , yielding and . Indeed .
The bound of iterations is only an upper bound; the next example stops after a single step.
Worked example 4.5.5
(Termination after one step)
Take , , . Then , and , so and . The updated residual is , and the true residual is also zero. The method stops here: would divide by and produce a meaningless direction , so it is not computed. The early stop happens because is an eigenvector of , so the first line search already reaches .
Concept lensAlgebraic
CG as an optimal polynomial
By induction from the recurrences, before termination the directions span the Krylov space . Hence for a polynomial of degree at most with , and by the lemma CG picks the minimizing . If has components in only eigenspaces of , the polynomial over their eigenvalues gives zero error, so CG stops within steps, as in the last example and for .
The method never needs the matrix itself, only a routine that applies it.
Worked example 4.5.6
(A matrix-free regularized operator)
Let , a single row with dependent columns, and , so is SPD although is singular. Apply it as . Solve with and .
First step: , , , , , and .
Second step: , , , . Check . Then , , and . Directly, .
Cost, stopping and assumptions
For an CSR matrix with stored entries, a product costs and storage is elements. CG keeps a constant number of length- vectors, so one iteration is operations in a unit-cost model. There may be significant synchronization, memory traffic and preconditioner costs in an actual system. For a matrix-free operator, the cost and memory of applying it replace the CSR figures. In exact arithmetic the theorem is a termination statement, not a promise that passes are cheap.
A common practical rule is to recompute the true residual and stop when , with nonnegative tolerances chosen for the application. The recursively updated residual can drift from the true one through rounding. A small residual is not automatically a small forward error: , so . Ill-conditioning can amplify residual error. Finite precision can also destroy exact conjugacy and the at-most- termination guarantee. Check the true residual periodically and at exit, allow an iteration limit, and treat an unexpected nonpositive as a reason to investigate the operator or numerical breakdown rather than to claim convergence. Replacing the recursive residual mid-run changes the subsequent algorithm and needs an appropriate implementation policy.
Common mistake
(Stopping on the updated residual alone)
The vector in the loop is produced by , not by evaluating . In exact arithmetic the two agree; in floating point they drift apart, and the updated residual can keep shrinking after the true residual has stalled. Reporting convergence because is small, without recomputing at exit, can certify an iterate that does not meet the tolerance.
Common mistake
(Running exactly iterations and stopping)
The at-most- statement is exact-arithmetic termination. In floating point the directions lose conjugacy, so after steps the residual need not be zero; for large , the intended use is to stop much earlier on a residual test. Use a residual-based stopping rule together with an iteration limit, rather than the dimension as the stopping rule.
For least squares, is SPD if , and can be evaluated as without forming . This may save storage but normal equations can worsen conditioning; it does not make CG a substitute for checking numerical accuracy. A fixed SPD preconditioner can improve the transformed system, but its construction and application have costs and its use requires the corresponding preconditioned recurrence.
Counterexample mode
Symmetry alone is insufficient
Let , and . Then and although , so the very first step size divides by zero. The matrix is symmetric and invertible, with solution , but indefinite. The repaired hypothesis is positive definiteness, which guarantees for every nonzero direction.
Practice with solutions
Quick check
(Let , and . Compare and .)
Find first.
Solution · Answer
The solution is , so , but . This attains the bound . A small absolute residual alone does not certify an error of the same size.
Quick check
(Show that is SPD for real and , even if has dependent columns.)
Expand .
Solution · Answer
It is symmetric, and for nonzero , . The first term may vanish when ; the positive regularization term supplies strict positivity.
Quick check
(In the example with , verify that the second update leaves the derivative along zero.)
Use the residual recurrence and the conjugacy .
Solution · Answer
After the first step . Since , . The directional derivative of along is , so it stays zero. This is the mechanism that preserves earlier progress.
Quick check
(How many CG iterations are needed for , any and ?)
Compute .
Solution · Answer
One. Here and , so and . Every nonzero vector is an eigenvector of , so the first line search is exact.