Contraction Mapping Convergence Proof

a value iteration perspective

Contraction Mapping Convergence Proof

1. Contraction Mapping Definition

A function \(f:X \rightarrow X\) on a metric space \((X,d)\) is called a contraction mapping if there exists a constant \(k \in [0,1)\) such that for all \(x,y \in X\), the following inequality holds:

\[d(f(x), f(y)) \leq k \cdot d(x, y)\]

2. Banach Fixed Point Theorem

Theorem: If \(f\) is a contraction mapping on a complete metric space \((X,d)\), then \(f\) has a unique fixed point \(x^∗ \in X\) (i.e. \(f(x^∗)=x^∗\)). Moreover, for any initial point \(x_0 \in X\), the sequence of iterates \(x_1 =f(x_0),x_2 = f(x_1), \dots\) converges to \(x^∗\).

3. Proof of Convergence


Consider the sequence of iterates \(x_n =f(x_{n−1})\), starting from any \(x_0 \in X\). By the contraction property, we have: \(d(x_n, x_{n-1}) \leq k \cdot d(x_{n-1}, x_{n-2}) \leq \ldots \leq k^n \cdot d(x_1, x_0)\)

Since \(0≤k<1\), the right-hand side converges to \(0\) as \(n \rightarrow \infty\) . Therefore, the sequence \({x_n}\) is Cauchy. Since \(X\) is complete, the Cauchy sequence \({x_n}\) converges to some point \(x^∗ \in X\).


Suppose there are two fixed points \(x^∗\) and \(y^∗\), i.e., \(f(x^∗)=x^∗\) and \(f(y^∗)=y^∗\) . By the contraction property: \(d(x^*, y^*) = d(f(x^*), f(y^*)) \leq k \cdot d(x^*, y^*)\)

Since \(0\le k < 1\) , this implies \(d(x^∗ ,y^∗)=0\), meaning \(x^∗ =y^∗\).

4. Consistency No Matter the Initialization

The proof demonstrates that any initial point \(x_0 \in X\) leads to the same fixed point \(x^∗\) through the iterative process. This means the contraction mapping converges to the unique fixed point regardless of the starting point.


Contraction mappings guarantee convergence to a unique fixed point due to their inherent property of “pulling points closer together”. This property makes them valuable in various fields, including numerical analysis, optimization, and dynamical systems. (Incorporating images would not significantly enhance the content of this proof, as it is primarily based on mathematical concepts and relationships.)