The Banach Fixed-Point Theorem

Imagine repeatedly halving your distance to a wall: no matter where you start, each step brings you strictly closer, and you converge toward the wall itself. A contraction mapping is a function that does something similar to every pair of points in its space — applying it always shrinks the distance between them by at least some fixed fraction. The Banach fixed-point theorem says that if a function is a contraction on a complete space, then repeatedly applying it from any starting point converges to exactly one point that the function maps to itself (a "fixed point"), and no other fixed point exists.

Formally, if $f$ satisfies $d(f(x), f(y)) \le k \cdot d(x, y)$ for some constant $k < 1$ and all $x, y$, then iterating $x_{n+1} = f(x_n)$ from any starting $x_0$ converges to a unique $x^*$ with $f(x^*) = x^*$. In plain terms: as long as the function reliably pulls points closer together by at least a fixed proportion, repeating it enough times funnels every starting guess toward one and the same destination.

This is the theoretical reason iterative numerical procedures — Newton's method under the right conditions, or value iteration in dynamic programming — are guaranteed to converge rather than wander or oscillate forever: each is designed (or shown) to be a contraction, so the theorem applies directly. Value iteration in a discounted Markov decision process with discount factor $\gamma = 0.9$, for instance, is a contraction with constant $k = 0.9$, guaranteeing convergence to the unique optimal value function regardless of the initial guess.