A recurrence needs more than a candidate
Solving can suggest the limit of , but it does not prove that the iterates converge or even remain in the domain. A contraction supplies these missing steps and a quantitative error bound.
Definition 5.1.1
(Contraction on a closed interval)
Let be a nonempty closed bounded interval and a map. It is a contraction on if there is a constant with such that
The sequence with is the iteration of , and a point with is a fixed point.
The condition ensures every iterate is defined; the single number controls all pairs in .
Theorem 5.1.2
(Contraction theorem with error bounds)
Let be a contraction on with constant . Then has exactly one fixed point , and for every the iterates converge to . Moreover, for ,
and for ,
Why the iterates converge
Proof
(Cauchy iterates, a fixed limit, and the tail estimate)
Write and interpret , including when . Every lies in because . Applying the contraction inequality repeatedly yields . For , the triangle inequality and a geometric sum give
The right side tends to zero, so the iterates are Cauchy. Completeness of gives a limit , and closedness of keeps inside . The contraction inequality also gives continuity of , so passing to the limit in gives .
If are fixed points, . Since , this forces . Passing in the tail estimate gives the a priori bound.
For the a posteriori bound, fix and apply the a priori bound with index to the iteration started at . Its first step is , and its first difference is , so . The constant is the one proved for ; a small step alone is not enough without such a bound.
Proof X-ray
Where each hypothesis acts in the contraction proof
The proof has four moves and each uses a different hypothesis. First, keeps every iterate inside the set where the inequality is available. Second, turns the telescoping differences into a convergent geometric series, which makes the sequence Cauchy. Third, completeness of supplies a limit and closedness of keeps it in the domain; only then does continuity of , which follows from the contraction inequality itself, identify the limit as a fixed point. Fourth, uniqueness is a separate comparison , where is used again to force . The error bounds are the tail of the geometric series in the second move. Dropping breaks the second and fourth moves at once.
The strict inequality cannot be replaced by a bound of , even when the fixed point is unique.
Counterexample mode
A unique fixed point alone does not force convergence
Claim: if satisfies and has a unique fixed point, the iterates converge to it. This is false. Take . Solving gives the unique fixed point . But from the iterates are forever, and for every . Here , so the constant is exactly and the theorem does not apply. The repair is the strict constant .
Worked example
Worked example 5.1.3
(An explicit contraction and its error bound)
On , take . For , , so the interval is invariant. For ,
Thus works. Starting at gives and . The fixed-point equation is , with roots ; only lies in . Existence and convergence have already been proved, so choosing that root identifies the limit rather than assuming it.
The latest-step bound at is . The true error is , comfortably inside the bound.
Worked example 5.1.4
(Choosing the number of iterations)
For the same map, , and , so the a priori bound is . To guarantee error below we need . Since but , the smallest guaranteed choice is . The guarantee needs no knowledge of .
Worked example 5.1.5
(The edge case )
Let on . The inequality holds with because both sides are . For any , and every later iterate is , so . The a priori bound has for , so for , which is exactly right. For it reads , which is also true because .
Common mistakes
Common mistake
(Starting outside the invariant interval)
For the fixed-point equation has two roots, and . Only the first is the limit when we start in . From the iterates are , increasing without bound. The contraction estimate was proved on only, and the root lies outside it.
Common mistake
(A small last step is not a small error)
The bound contains the factor , which is large when is close to . For on and , we have , and . Hence , and the factor is attained. Stopping when the step is below the tolerance guarantees only that the error is below nine times the tolerance.
Exercises and solutions
Quick check
(For the worked map , find exactly from .)
Apply once to .
Solution · Answer
.
Quick check
(If and , bound .)
Use the a posteriori bound.
Solution · Answer
The factor is , so .
Quick check
(If on , why does the closed-interval theorem above not apply?)
Look at where the iterates go.
Solution · Answer
The domain is not closed. All iterates from a positive start converge to , which lies outside the domain, so there is no fixed point in it.
Quick check
(If , what happens after one iteration?)
Put in the contraction inequality.
Solution · Answer
The inequality forces to be constant on the nonempty domain. Its value lies in and is the fixed point, so all iterates from onward equal it.