T(x) = x/3 + 2
k = 1/3, fixed point 3
x = x/3 + 2.
If is a contraction on a complete metric space ( with ), then has exactly one fixed point , and the iteration converges to it from any start, with error .
This page is easier if you are comfortable with:
A contraction brings every pair of points closer by the factor . So the iterates form a Cauchy sequence, which converges because the space is complete, and the limit is a fixed point; uniqueness follows because two fixed points would be times as far apart as themselves. This is the theoretical basis of fixed-point iteration, and the convergence condition in fixed-point convergence is the case .
Example: has and fixed point 2. From : , and after 5 steps , with error , exactly the bound . For on , , so the iteration converges to , the root of ; the picture is in cobweb and staircase diagrams.
The theorem proves the existence and uniqueness of solutions of differential equations (Picard iteration) and of linear systems solved by Jacobi and Gauss–Seidel iterations. Faster methods such as Newton–Raphson have a contraction constant that tends to zero near the root; see quadratic convergence. Closed and bounded sets in finite dimensions are compact, as in the Heine–Borel theorem.
A map that shrinks distances has exactly one fixed point, and repeated application finds it from any start.
Iterating cos starting anywhere in [0, 1] spirals in to the intersection.
These examples are worked by hand, step by step, so you can compare your own working.
For and , find the error bound after 5 steps and the actual error.
For on , find the contraction constant.
Find the fixed point of .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
k = 1/3, fixed point 3
x = x/3 + 2.
2, 2.6667
Approach 3.
kⁿ/(1 − k) × |x₁ − x₀|
0.0370.
⌈ln(0.001(1 − k)/|x₁ − x₀|)/ln k⌉
8.
If d(Tx, Ty) ≤ q d(x, y) with q < 1 on a complete metric space, T has a unique fixed point x*, and d(xₙ, x*) ≤ qⁿ/(1 − q) d(x₁, x₀).
Solve x = x/3 + 2.
From x₀ = 0 find x₂ = T(T(0)).
Find q⁴/(1 − q)·|x₁ − x₀| with q = 1/3.
Smallest n with error < 0.001.
allowed ✗
need q < 1 ✓
Strict.
any metric space ✗
complete required ✓
Else no fixed point.
ignored ✗
T maps the space into itself ✓
Required.
qⁿ|x₁ − x₀| ✗
divide by 1 − q ✓
Geometric tail.
Try each one on paper, then open the answer. Use the solver above to see the full working.
4
3
0.125
0.00111
10
8
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
A contraction on a complete metric space has a unique fixed point.
Iterate from any start.
d(xₙ, x*) ≤ qⁿ/(1 − q) d(x₁, x₀).
Existence of ODE solutions.
contraction mapping theorem.
More in Analysis, algebra and topology and the formula sheets.