Banach Fixed-Point Theorem

How it works

A contraction is a map that brings every pair of points closer together by a fixed ratio. If d(T(x), T(y)) ≤ k · d(x, y) for all x, y with k < 1, then T is a k-contraction. Geometrically: T shrinks distances by at least factor k. Pick any starting point x₀. Apply T: get x₁ = T(x₀). Apply again: x₂ = T(x₁). The successive distances satisfy d(xₙ, xₙ₊₁) ≤ kⁿ · d(x₀, x₁), so they form a geometric series — summable, hence convergent. The sequence (xₙ) is Cauchy, and completeness guarantees a limit x* in X. Continuity of T (a contraction is automatically 1-Lipschitz, hence continuous) forces x* to be a fixed point: T(x*) = lim T(xₙ) = lim x_{n+1} = x*. Uniqueness: if y* is another fixed point, then d(x*, y*) = d(T(x*), T(y*)) ≤ k · d(x*, y*); since k < 1, this forces d(x*, y*) = 0.

The explicit error bound d(xₙ, x*) ≤ k^n · d(x₀, x*) / (1 − k) tells you exactly how fast iteration converges — and lets you stop when you've reached desired accuracy. With k = 0.5, going from initial distance 1 to error 10⁻⁶ takes 20 iterations; with k = 0.9, it takes 132.

Proof sketch

Pick any x₀ ∈ X and define xₙ₊₁ = T(xₙ). Inductively, d(xₙ, xₙ₊₁) ≤ kⁿ d(x₀, x₁). For m > n, by the triangle inequality:

d(xₙ, xₘ) ≤ d(xₙ, xₙ₊₁) + d(xₙ₊₁, xₙ₊₂) + … + d(xₘ₋₁, xₘ)
         ≤ (kⁿ + kⁿ⁺¹ + … + kᵐ⁻¹) d(x₀, x₁)
         ≤ (kⁿ / (1 − k)) d(x₀, x₁)

The right side → 0 as n → ∞ (since k < 1), so (xₙ) is a Cauchy sequence. By completeness of X, the sequence converges to some x* ∈ X. Continuity of T (any contraction is Lipschitz, hence continuous) lets us pass to the limit in xₙ₊₁ = T(xₙ): the left side tends to x*, the right to T(x*). So x* = T(x*).

For uniqueness: if both x* and y* are fixed points, d(x*, y*) = d(T(x*), T(y*)) ≤ k · d(x*, y*). With 0 ≤ k < 1, this forces d(x*, y*) = 0, i.e., x* = y*. Taking m → ∞ in the Cauchy bound gives the error estimate d(xₙ, x*) ≤ kⁿ · d(x₀, x₁) / (1 − k) ≤ kⁿ · d(x₀, x*) · (1 + k)/(1 − k) — the usually-quoted form uses d(x₀, x*) directly via a second application of the triangle inequality.

Variants and generalizations

• Schauder fixed-point. Drops the contraction assumption: a continuous map from a compact convex subset of a Banach space to itself has a fixed point (existence only, not uniqueness). Strictly stronger than Brouwer in infinite dimensions.
• Brouwer fixed-point. A continuous self-map of a compact convex set in ℝⁿ has a fixed point. Topological — no contraction needed. Banach is the metric refinement: more hypothesis, much more conclusion (uniqueness + constructive iteration).
• Kakutani fixed-point. Generalizes Brouwer to set-valued (correspondence) maps with closed graph and convex values. Used in game theory (Nash equilibrium existence).
• Edelstein's theorem. If T satisfies the strict inequality d(T(x), T(y)) < d(x, y) for x ≠ y on a compact metric space, T has a unique fixed point. Weaker than contraction (no uniform k) but needs compactness.
• Caristi's theorem. If there is a lower semicontinuous function φ on X such that d(x, T(x)) ≤ φ(x) − φ(T(x)) for all x, then T has a fixed point (no continuity required). Generalizes Banach in a different direction.
• Hutchinson's theorem. The Banach fixed-point theorem applied to the Hausdorff metric on compact subsets of a complete metric space. Every IFS {T₁, …, T_n} of contractions defines a unique attractor — the Hutchinson operator A ↦ ⋃Tᵢ(A) is itself a contraction in the space of compact sets.
• Asymptotic regularity. If d(Tⁿ(x), Tⁿ⁺¹(x)) → 0 for some x, certain non-expansive maps still admit fixed points (Ishikawa, Krasnoselskii–Mann iterations). Used in convex analysis and proximal-point algorithms.

Numerical examples

Example 1 — solving x = cos(x). The map T(x) = cos(x) on ℝ has |T′(x)| = |sin x| ≤ 1, and on the interval [0, 1] one can show |T′| ≤ sin 1 ≈ 0.841. So T is a contraction with k ≈ 0.841 on [0, 1]. Iterate from x₀ = 0.5:

x₀ = 0.5000
x₁ = cos(0.5) = 0.8776
x₂ = cos(0.8776) = 0.6390
x₃ = cos(0.6390) = 0.8027
x₄ = cos(0.8027) = 0.6948
x₅ = cos(0.6948) = 0.7682
...
x₅₀ ≈ 0.7390851332    ← Dottie number, fixed point of cos

With k ≈ 0.84, error multiplies by 0.84 each step — about 5 iterations per digit. After 50 iterations, we have ~9 correct digits.

Example 2 — Picard iteration for the ODE y′ = y, y(0) = 1, solution y = eᵗ. Define T(y)(t) = 1 + ∫₀^t y(s) ds on C([0, ½]). The Lipschitz constant of f(t, y) = y is L = 1, so k = L · h = 0.5 contraction on [0, ½]. Picard iterates from y₀ = 1:

y₀(t) = 1
y₁(t) = 1 + t
y₂(t) = 1 + t + t²/2
y₃(t) = 1 + t + t²/2 + t³/6
...
yₙ(t) = 1 + t + t²/2 + … + tⁿ/n!  → eᵗ

The Picard iteration recovers the Taylor series of e^t. Convergence on [0, ½] is geometric at rate k = 0.5: 30 iterations give 10⁻⁹ accuracy at t = ½.

Example 3 — Sierpinski triangle as an IFS attractor. Three contractions T₁(p) = p/2, T₂(p) = p/2 + (½, 0), T₃(p) = p/2 + (¼, √3/4), each with k = ½. Hutchinson's theorem gives a unique compact attractor — the Sierpinski triangle. The chaos game (pick a starting point, repeatedly apply a random Tᵢ) converges almost surely to the attractor, plotting the fractal in O(N) operations for N iterations.

Common pitfalls

• "|T(x) − T(y)| < |x − y| suffices." Strict inequality without uniform k is not enough on a general complete space — you need uniform k < 1. Edelstein's theorem rescues the conclusion under compactness, but on noncompact complete spaces, strict-but-non-uniform contractions can fail to have fixed points.
• "Need T contractive everywhere." It suffices to verify the contraction on a closed (hence complete) invariant subset T(B) ⊆ B. This local-Banach version is used in Picard-Lindelöf (applied on a closed ball in C([0, h])) and Newton's method (applied on a closed ball around the root).
• "Need T to be Lipschitz with constant ≤ 1." You need strictly less than 1. Equality k = 1 (non-expansive) is not enough — translations T(x) = x + 1 on ℝ are non-expansive but have no fixed point.
• "Two fixed points coexist if T is contractive on an open set." No — uniqueness is global within the complete space where T is a contraction. Two fixed points in the same complete contracting domain contradicts d(x*, y*) ≤ k · d(x*, y*).
• "Iteration always converges fast." Convergence rate is exactly k per step. If k is close to 1 (weakly contracting), iteration is slow — log(1/ε) / log(1/k) ≈ log(1/ε) / (1 − k) steps for ε accuracy. Newton's method is famous because near a simple root the effective k → 0, giving quadratic rather than linear convergence.
• "Completeness is automatic." No — many natural settings (ℚ, open intervals (0, 1], normed spaces without completeness) admit contractions with no fixed point. Always check that you are in a complete metric space or a closed subset thereof.

Where it shows up

• Picard-Lindelöf for ODEs. The integral operator on continuous functions is a contraction in sup-norm on small intervals. Banach gives existence and uniqueness; Picard iteration constructs the solution.
• Inverse and implicit function theorems. Both are proved by setting up an auxiliary contraction whose fixed point is the inverse (or implicit) function. Newton-like update is a contraction near a non-degenerate point.
• Newton's method. Locally a contraction with k → 0 near a simple root, giving quadratic convergence. Banach's framework handles global existence; the sharp quadratic rate is a separate calculation.
• Iterated function systems (IFS). Sierpinski triangle, Cantor set, Barnsley fern, Koch snowflake — each is a Hutchinson attractor of contractions in the Hausdorff metric. Chaos-game rendering exploits the contraction-mapping convergence.
• Markov chain stationary distributions. The transition operator on the probability simplex is a contraction in total variation for ergodic chains. Banach gives uniqueness and exponential convergence to the stationary distribution.
• PageRank and stochastic iteration. The damped random-surfer operator is a contraction with k = damping factor. Banach guarantees a unique stationary vector; power iteration converges geometrically.
• Numerical fixed-point iteration. Splitting methods, Jacobi/Gauss-Seidel iteration for linear systems, proximal-point and prox-gradient methods in convex optimization — all are contractions on the iterates and inherit Banach-rate convergence.
• Game theory. Bertsekas's value iteration for dynamic programming and Markov decision processes is a contraction in the sup-norm with k = discount factor γ < 1. Banach gives existence, uniqueness, and rate of convergence to the optimal value function.