A loop can stop because two displayed numbers look close, because an iteration budget has expired, or because an error bound meets a requested tolerance. These are different events. A numerical method should report which event occurred and what assumptions make its stopping rule informative.
The mathematical contract
Definition 13.1.1
(Contraction on an invariant interval)
Let be a closed interval. A map is a contraction on with constant if and
The inclusion is the invariance condition: it keeps every iterate where the contraction estimate is known. For write for the observed step.
Theorem 13.1.2
(A posteriori bound for fixed-point iteration)
Let be a contraction on with constant and let . Then all iterates lie in , for a unique fixed point , and for every
Proof
(Bounding the tail by a geometric series)
Invariance gives for all by induction. For the contraction inequality applied to gives , hence . For , telescoping and the triangle inequality give
The same estimate shows is a Cauchy sequence, so it converges to some , and because is closed. As is continuous, . If is another fixed point in , then forces since . Finally let in the displayed bound: , which gives the claim. If , is constant on and the first update is already the fixed point.
Proof X-ray
Which hypothesis does each line use
The key move is the telescoping sum: the unknown error is replaced by a sum of observed steps, and the contraction inequality turns that sum into a geometric series. Invariance is used only to guarantee that and both lie in at every stage, so the inequality may be applied each time; without it the chain breaks at the first iterate that leaves . The condition is used twice, to sum the series and to make the fixed point unique. The final limit needs the convergence proved just before it; a small alone, with no contraction constant, gives no tail estimate at all. The factor is the price of not knowing the future steps: it is large exactly when is near one.
This bound applies to the new iterate , after measuring its distance from . A small difference alone is not a universal certificate: the bound uses a proven contraction constant and invariance of the interval.
Worked calculation
Worked example 13.1.3
(A map with constant one half)
Take , , and . The image is and , so . The fixed point solves , hence . The first iterates are
At , , so the certificate is . Here the actual error is also . Equality is a property of this example, not a general promise that the bound is sharp.
The explorer below runs this loop on five maps and compares each step , the certificate and the true error, so you can see when a small step certifies anything.
Worked example 13.1.4
(How many steps does a tolerance need?)
For the same map and , , so and, since , the certificate equals . We want it at most , that is . Because and , the first admissible is , with certificate and true error . With the budget maxSteps = 10 the loop cannot certify this tolerance, and the status must say so.
Worked example 13.1.5
(A contraction constant from a derivative)
Let on . Then , and on , so the mean-value theorem gives a contraction with this , and . From : , , , so and the certificate is about . It is valid, because the true error is , but it is larger than the length of and tells us nothing useful. Here a constant close to one makes a moderate step an unconvincing certificate; many more iterations are needed before the certificate is small.
A bounded loop that reports its status
The following MATLAB function is a compact demonstration for this specific and interval. It accepts finite real scalar x0 in [0,2], positive finite tol, and a positive integer maxSteps. Inputs are assumed to satisfy that stated contract; a production function should validate them before executing the loop.
function [x, ok, n, bound] = fixed_demo(x0, tol, maxSteps)
% Mathematical x_n is returned after n updates.
q = 1/2;
x = double(x0);
ok = false;
bound = Inf;
for n = 1:maxSteps
xnew = 1 + x/2;
bound = (q/(1-q))*abs(xnew-x);
x = xnew;
if bound <= tol
ok = true;
return
end
end
end
The iteration counter counts completed updates. If no bound meets the tolerance, ok remains false and the last approximation is returned together with the last bound and the exhausted count. The positive-maxSteps contract ensures n is assigned even if the loop never returns early. In exact arithmetic, ok=true certifies the stated distance bound under the proved contraction assumptions. Floating-point rounding adds effects not included in that proof, so the displayed bound alone is not a rigorous machine-arithmetic certificate.
For a different , do not reuse q=1/2 without proving a valid bound on the relevant interval. In particular, if is continuous on and differentiable on its interior with everywhere in that interior, the mean-value theorem gives the contraction inequality. Invariance still needs a separate check; checking the derivative at a single point is insufficient.
A small step can mislead
Counterexample mode
A small step with a large error
Claim: if is below , then is within about of the fixed point. Take on . The image is , so , and . From we get , so , but the true error is , which is . In general while . This agrees with the theorem: the certificate is exactly the true error here. A small step certifies a small error only when is moderate; for the factor is at most one.
Common mistake
(Treating the last iterate as a root when the contract fails)
The map maps into itself and has the fixed point , but it is not a contraction with a constant less than one: . From the sequence is , with at every step, so the step test never fires and the loop ends only at the maximum step count. The last iterate, or , is not the fixed point . A maximum-step limit prevents an endless loop, but it does not turn this output into a converged answer. Likewise has small steps but no fixed point and no invariant bounded interval of the required kind. The correct response to a failed hypothesis is to report the limitation, not to label the last iterate a certified root.
Quick checks
Quick check
(For on with , what is the certificate at ?)
Use and .
Solution · Answer
and , so the certificate is . The true error is .
Quick check
(A map is a contraction with and the last step was . What error bound does the theorem give?)
Compute .
Solution · Answer
, so . Stopping at a step of certifies only about , not .
Quick check
(For which values of is the stopping test itself a certificate of error at most ?)
Solve with .
Solution · Answer
, that is . For larger the step must be compared with instead.
Quick check
(Which hypothesis of the theorem fails for on ?)
Test the contraction inequality on , .
Solution · Answer
Invariance holds, but , so no constant works. The iteration does not converge.