Why a stopping rule needs a bound
An iterative linear solver reports vectors, not the unknown error. A residual that looks small is useful evidence only after we specify its scale and how the matrix turns residual into error. In a finite-element solve the energy norm is often the quantity of interest, and a preconditioner supplies a more informative residual scale than the unweighted Euclidean norm. We derive bounds that apply to any approximate solution, whether or not it was produced by conjugate gradients.
Let be symmetric positive definite (SPD), , and let be an approximate solution. Write and . Let and . We do not need to form an inverse: the latter norm can be evaluated by solving and computing .
Definition 1.6.1
(Spectral equivalence)
Suppose known constants satisfy
Equivalently the eigenvalues of lie in . Bounds need not be sharp, but they must be valid for the actual matrices.
Theorem 1.6.2
(Residual-to-error bounds)
Under (1), every satisfies
If , the relative energy error also satisfies
Proof
(Diagonalize the preconditioned matrix)
Set . Since , the squared error is , and the squared preconditioned residual is . Diagonalize the SPD matrix and put . Then and . For each eigenvalue we have ; summing over the coordinates yields , which proves (2).
Applying (2) to the approximate solution , whose residual is , bounds between and . Dividing the upper bound for the numerator by the lower bound for the denominator, and vice versa, gives (3); ensures a nonzero denominator.
Proof X-ray
Why the square roots appear
The only hypothesis used is the spectral inclusion (1), and it enters only through the eigenvalues of . The decisive move is the change of variable : it puts the error and the preconditioned residual into the same orthonormal eigenbasis of , with weights and on the same squared coordinates. Comparing with coordinate by coordinate gives factors between and on squared norms, hence square roots on the norms themselves.
The relative bound (3) needs a second, separate idea: is itself an approximate solution with residual , so the same inequality controls the denominator . The constants combine to because an upper bound on the numerator is paired with a lower bound on the denominator. No step refers to how was produced, so the bounds hold for every iterate of every method.
Thus, in exact arithmetic, a sufficient relative stopping rule is . A failure of this sufficient test does not prove that the actual error exceeds : conservative spectral bounds can leave a wide gap. If , the unique solution is zero and the relative expression in (3) has a zero denominator; use the absolute bound instead.
An implementable certificate with two defects
Computers may store an approximate residual and an approximate solution to . In recursive Krylov updates the stored residual can drift from . Recomputing it can reduce the drift, but does not by itself make floating-point error vanish. We therefore assume supplied, valid bounds, rather than silently identifying the stored quantity with the exact residual:
Here is the mathematical residual of the represented data and iterate. Both defect bounds must be obtained independently, for example by a validated error analysis or verified arithmetic; a floating-point printout alone is not automatically such a bound. Define
Theorem 1.6.3
(Defect-aware absolute certificate)
Under (1) and (4), with the quantities in (5) evaluated exactly or bounded outwards,
In particular, the upper endpoint certifies an absolute tolerance when it is no larger than that tolerance.
Proof
(Two triangle inequalities in the preconditioned norm)
The reverse triangle inequality in the norm gives
Because , diagonalization gives . Also . Hence . Insert these bounds into (2). The conclusion includes , and does not require to be positive. In numerical implementation, outward bounds must also account for rounding in , , and the constants; reporting a rounded ordinary calculation as a proof would be unjustified.
The inner-solve defect and residual defect play different roles: one measures how well was solved, while the other compares the stored residual with . A small value of only one cannot replace a bound on the other. For a relative certificate, independently bound the denominator away from zero using the same construction; do not divide by a lower bound that may be zero.
Worked example 1.6.4
(A certificate with explicit defects)
Let , , , and . The generalized eigenvalues are and , so , and . The true residual is . Suppose a calculation stores and . Then
Thus and (6) bounds the energy error between and . The known exact solution gives , inside this interval. In a real solve the true residual and exact error are generally unavailable for this comparison; valid defect bounds must come from another source.
Worked example 1.6.5
(Relative bounds at a conjugate-gradient iterate)
Use the same , , and , now with exact arithmetic, so and . Then and , so the ratio is . Inequality (3) gives
The actual value is , since . To certify a relative error of at most by the sufficient rule, the ratio would have to fall to .
Worked example 1.6.6
(An exact preconditioner closes the gap)
In the edge case , condition (1) holds with , and (2) becomes the identity . For and , the residual gives , which equals . The bound is exact, but evaluating requires a solve with , which is the original problem.
Common mistake
(An estimated eigenvalue is not a valid bound)
The upper bound in (2) needs a constant that is truly a lower bound for the spectrum of . An estimate from a few Lanczos steps or from a coarse model may overestimate it. In the first example the true value is ; using instead would give , below the actual error , so the resulting certificate would be false.
Counterexample mode
A small residual can hide a large error
Take , and . Then and , but . The residual is small because the matrix suppresses error in its second eigendirection. The example does not contradict (2): the relevant lower spectral bound is small, and the norm and scale must be stated.
Practice with solutions
Quick check
(Sharpness: let and with . Which errors give equality in each side of (2)?)
Try errors along a single eigenvector.
Solution · Answer
If lies in the eigenspace, then and , giving equality in the upper error bound. An error in the eigenspace gives equality in the lower bound. Thus neither constant can be improved using only these endpoint bounds.
Quick check
(Tolerance: suppose , and . Does (6) certify an absolute energy error of at most ?)
Evaluate the upper endpoint of (6).
Solution · Answer
The upper bound is , so yes, provided every stated bound is valid and the displayed arithmetic is evaluated safely.
Quick check
(Missing defect: let , , , and . Is an exact inner solve enough to certify zero error?)
Compare the stored residual with .
Solution · Answer
No. The inner defect is zero, but , so the residual defect is . The actual error is one, and (6) correctly gives the interval ; ignoring would produce the false certificate zero.
Quick check
(Lower bound: explain why a small upper error certificate does not imply that the lower bound in (6) is positive.)
Consider the case .
Solution · Answer
If , the certified lower endpoint is zero. The available information is then consistent both with exactness and with a nonzero error; it says nothing about whether the actual error is zero.
These bounds concern a fixed SPD problem and supplied deterministic enclosures. They do not provide spectral bounds, validate floating-point computations automatically, analyze variable or indefinite preconditioners, or certify the discretization error between the linear system and an underlying differential equation.