From an equation to an iteration
Solving by iteration begins with a choice, not a formula forced on us: rewrite the equation as and compute . Two equivalent rearrangements can behave very differently. Before iterating, check both directions of equivalence on the domain: every desired zero must be a fixed point, and every fixed point under consideration must be a zero. Multiplying by a factor that can vanish may introduce an unwanted fixed point.
Even an equivalent iteration need not converge. A useful design question is: can we find a closed interval that contains the intended root and is mapped back into itself, on which nearby points move closer together? The two conditions play different roles. Invariance keeps every iterate in the region where our estimate is valid; contraction makes the errors decrease.
Theorem 2.3.1
(A computable fixed-point error bound)
Let be a nonempty closed bounded interval. Suppose and, for some known ,
For any , the iterates converge to the unique fixed point . For , using in the bound when ,
and for ,
The first bound is a priori once the initial step is known; the second uses the most recent computed step. If , the map is constant on and .
Why the bounds hold
Proof
(A geometric tail controls every later iterate)
Write for . Contraction gives , and therefore . For , the triangle inequality and a geometric sum yield
The right side tends uniformly to zero as grows, because . Thus the iterates are Cauchy; completeness and the closedness of put their limit in . The contraction inequality makes continuous, so passing to the limit in gives . If were another fixed point, forces . Taking in the displayed sum gives the a posteriori bound. Summing from instead gives the a priori bound. These estimates assume exact arithmetic and an actually justified , not one guessed from a few observed steps.
Proof X-ray
Where invariance, closedness and contraction are used
The proof rests on one estimate, , and it needs both hypotheses at once: the contraction inequality may be applied to and only because invariance has kept every iterate in . The key move is to bound the distance between two iterates by the tail of a geometric series, . Letting turns this Cauchy estimate into the error bound. That is why the a posteriori bound is the last step multiplied by rather than the last step itself: the factor accounts for all future steps, and it is large when is close to one.
Closedness of and completeness of the real numbers place the limit in . Without closedness the conclusion fails: maps into itself with , but its fixed point is not in the interval. The condition is used twice more, for the convergence of the geometric series and for uniqueness.
If is continuous on , differentiable in its interior and there, the mean value theorem supplies the contraction inequality. The derivative check does not replace the separate requirement .
Common mistake
(Checking the derivative but not the image)
For on , everywhere, so the derivative test passes. But does not meet , and the only fixed point of on the real line is , outside . Starting at gives , converging to . The theorem's conclusion about a fixed point in is not available because invariance fails.
A complete calculation
Worked example 2.3.2
(A fixed point for the positive root)
To solve on , use . For , , and
The theorem gives a unique fixed point in . Since there, is equivalent to the original equation. Starting at gives
The last step has size . With , the computable error bound at is
This certificate requires neither the exact root nor a decimal approximation to it. The bound is conservative; it is valid because the interval and the derivative bound were proved before using it.
Worked example 2.3.3
(A pessimistic a priori count for )
Take on . Since is decreasing there, , and . From we get , so the a priori bound is . To guarantee error at most we need
so is certified (the bound is about ) while is not (about ). In fact the iterates first come within of the fixed point at , because near the local factor is rather than . The a priori count is valid but pessimistic; the a posteriori bound follows the actual progress more closely.
Local behavior is a different claim
Suppose is continuously differentiable near a fixed point . If , continuity gives a sufficiently small closed interval around on which . The mean value theorem then also shows , so this interval maps into itself. Starts in that sufficiently small interval converge. The statement does not identify its radius or guarantee success from arbitrary starting values.
Counterexample mode
Self-mapping and a local derivative are not enough separately
On , maps the interval into itself, but never converges. Here , so strict contraction is absent. Conversely, has fixed point and , yet starting at gives , moving away from zero. A local condition does not protect a distant start.
Common mistake
(A small step is not a small error)
A small step by itself is not an error certificate: has fixed point zero, but starting at produces a step of only while the error at is . Its contraction factor is , so the theorem correctly multiplies the step by .
Choosing a relaxation parameter
A common family is , with nonzero constant . On any interval where it is defined, its fixed points are exactly the zeros of . If is known to satisfy on , choosing
makes : the affine expression has largest absolute value at an endpoint or . This only establishes contraction; verify separately. If a zero is already known to exist and is symmetric about , the derivative bound implies invariance, but in practice an interval may be asymmetric or unknown. A poor parameter can cause divergence even for a simple equation: for , gives .
Worked example 2.3.4
(Relaxation for )
Let on . Here lies in , so , , and . The map has . Invariance must be checked separately: is concave with maximum , and , so . From ,
The latest step is , so . The actual error is about , inside the certificate.
Practice and solutions
Quick check
(Let on and . Verify the theorem's conditions, find the fixed point, and bound the error at using the latest step.)
The map is increasing, so its image is determined by the endpoints.
Solution · Answer
The image is and . The fixed point is . We obtain , , so the a posteriori bound is , equal here to the actual error.
Quick check
(For , consider . Explain why its fixed points are not all roots of .)
Solve directly.
Solution · Answer
Fixed points satisfy , so is an extra fixed point although . The desired zeros are fixed too. Equivalence fails because the multiplying factor vanishes at .
Quick check
(Suppose a verified contraction has and . Find a sufficient integer for the a priori bound to guarantee .)
Use .
Solution · Answer
The bound is . For it is , too large; for it is . Thus suffices. This counts iterations from , and it is a sufficient guarantee, not necessarily the first iterate whose true error meets the tolerance.
The formulas above describe exact iterations. Rounded function evaluations and arithmetic can break the stated inequalities; rigorous machine-level certificates require separate bounds on those errors. A stagnation or iteration-limit exit should therefore be reported separately from a proven error tolerance.