A small step can be misleading
An iterative linear solver returns a sequence of approximations, not an exact solution after a prescribed number of operations. A common stopping rule asks whether two successive stored vectors are close. That is useful, but it can be deceptive: rounding can make a computed iterate stop changing even though it is still far from the solution. To interpret a small step we need both a convergence bound for the ideal iteration and a bound for the errors in the computed sweep.
Definition 7.4.1
(Inexact fixed-point sweep)
Let on , and use a fixed vector norm and its induced matrix norm. Assume a known number satisfies . The unique fixed point solves . We regard the stored as exact data; discrepancies between these data and an intended physical or mathematical system require a separate analysis. The computer produces
The bound must apply to the entire sweep, including all rounding and any inexact inner solve. It may vary with . The following results apply to any computed sequence satisfying this model, even when the errors are dependent or deliberately chosen; no random-rounding assumption is used.
What remains of contraction?
Theorem 7.4.2
(Error propagation and a posteriori stopping)
For any ,
If , then the most recent bound gives the computable estimate
Alternatively, if is any certified upper bound for , then
Proof
(Absorb the unknown error into the left-hand side)
Subtract the fixed-point equation from the computed update. The triangle inequality and induced norm give
Repeated substitution proves the first bound. To obtain the step certificate, subtract the two vectors in the opposite order and insert the previous computed sweep:
Taking norms and moving to the left proves the result. Finally,
so the same rearrangement gives the defect bound. In each case is essential.
Proof X-ray
Keep the new error term
Three hypotheses enter at separate points. The induced norm gives for every , used once per sweep. The sweep bound enters additively, so an early error is damped by every later contraction; that is why carries the weight rather than being amplified.
The non-obvious move in the step certificate is to rewrite as . The unknown error then appears on both sides, with coefficient at most on the right, and lets it be absorbed into the left. This produces the factor ; with the rearrangement would divide by a nonpositive number and certify nothing. The defect bound is the same absorption with the exact sweep in place of the stored , so no term appears, but must bound the exact defect. No sign or probabilistic assumption is used: every step is a norm inequality valid for adversarial errors.
A stopping test for absolute tolerance may therefore accept only when a certified upper bound for is at most . In machine arithmetic, evaluating , , and the final expression also introduces error. Use exact arithmetic, directed rounding or another rigorous enclosure to obtain the required upper bounds; a rounded decimal displayed on screen is not automatically such a bound. For a relative target one also needs a certified positive lower bound for ; absolute error alone cannot certify relative accuracy at a zero solution.
Corollary 7.4.3
(Uniform and vanishing sweep errors)
If for all , then
If , then .
Proof
(Geometric sum and a split tail)
For the uniform case, . For the vanishing case, fix and choose with for all . For , the early terms satisfy , which tends to zero. The tail satisfies . Since as well, for every .
The uniform bound approaches , not necessarily zero. This is an error floor in the guarantee, not a claim that every actual sequence has a nonzero limiting error.
Obtaining a sweep bound
For an explicit matrix-vector evaluation, a standard rounding model supplies one possible bound. In this subsection additionally assume the vector norm is monotone: componentwise implies . The usual , and norms have this property; an arbitrary vector norm need not. Assume separately rounded scalar multiplications and additions in round-to-nearest arithmetic, no overflow or problematic underflow, and , where is the unit roundoff and . Let . Evaluate each component of as a sequential dot product of products followed by adding . Standard product-of-rounding-factors estimates give the conservative componentwise enclosure
Here and are entrywise absolute values; the expression on the right must itself be bounded upward. For the infinity norm this gives the maximum of the row sums of these nonnegative terms. A fused multiply-add, a different summation order, an implicit triangular sweep, subnormal arithmetic, or overflow requires a bound appropriate to that actual computation. In particular one must not apply this explicit-matrix count unchanged to a Gauss–Seidel implementation that never forms .
For a system , one often has for a nonsingular splitting matrix . Its exact defect is , not generally the unpreconditioned residual. Thus a residual bound becomes a contraction certificate only after the action of and its evaluation error are controlled.
Worked example and failure of a naive rule
Worked example 7.4.4
(Step certificate against defect certificate)
Consider the scalar ideal map , with fixed point . Suppose , the first computed update is , and the sweep error is known to satisfy . The stored step is . The theorem yields
The actual error is . The bound is conservative, but it is valid without knowing the sign of the sweep error. At the same stored point, the exact defect is , giving the sharper bound .
Counterexample mode
A zero step does not certify accuracy
Now take again and let a computed sweep from return . Its step is zero, yet the error is . The required sweep error is , so the corrected step bound is . A zero step is a certificate only if the error bound is also sufficiently small. Conversely, a certificate larger than the target means that this argument is inconclusive; it does not prove the actual answer inaccurate.
Worked example 7.4.5
(A sweep bound in the infinity norm)
Let and , so . Solving gives ; check: in each row. At , each component of is . Here , so . In binary double precision, and . The sweep bound is therefore about , and the guaranteed floor is . These decimals must be rounded upward before they are used in a certificate.
Worked example 7.4.6
(Sweep errors that shrink at the contraction rate)
Take , and . Each term of the weighted sum is , independent of , so
At this is . The bound tends to zero, as the corollary predicts, but this edge case shows the price of errors decaying exactly as fast as the contraction: the extra factor .
Common mistakes
Common mistake
(Using the residual in place of the defect)
For the defect is . Take the scalar case , , : then , and . At the residual is but the defect is . The residual would suggest the false certificate ; the defect gives , the actual error.
Common mistake
(Accepting a displayed decimal as an upper bound)
Suppose the exact value of is and the tolerance is . A display rounded to four decimals shows and appears to pass, yet the test fails. Only an upward-rounded or exactly computed value may be compared with .
Practice with solutions
Quick check
(Let , , and a certified . Can the step certificate establish absolute error at most ?)
Substitute into the step certificate.
Solution · Answer
The upper bound is , so it can. All three input bounds and the final arithmetic must be certified in an implementation.
Quick check
(Suppose and every sweep error is bounded by . Give the limiting upper bound from the uniform-error formula. Does it prove that the iteration fails to converge?)
Let in the uniform-error formula.
Solution · Answer
The limiting bound is . It does not prove failure: for example, all gives ordinary convergence. The bound permits a nonzero limiting error; it does not require one.
Quick check
(The scalar map is and the exact defect at a candidate is . Give an error bound. If the defect is instead computed as with an absolute evaluation error at most , what bound is justified?)
Here , so .
Solution · Answer
The exact defect yields . In the second case its certified upper bound is , so .
Quick check
(Give a computed sequence with constant nonzero sweep error that reaches the uniform bound asymptotically.)
Try a map whose fixed point is zero.
Solution · Answer
For with , , , and , direct summation gives . The limit equals the stated bound, so no smaller uniform guarantee follows from these assumptions alone.