The Banach Fixed-Point Theorem: When Iteration Always Converges

A function takes inputs and produces outputs. A fixed point of a function $T$ is a point that the function leaves unchanged: $T(x) = x$. Fixed points are central to mathematics and applications — every steady state, every equilibrium, every stable configuration of a dynamical system is a fixed point of the function describing the system’s evolution.

When does a function have a fixed point? In general, fixed points need not exist. The function $T(x) = x + 1$ on the real line has no fixed point at all. The function $T(x) = -x$ has exactly one (at $x = 0$). And the function $T(x) = x^2$ has two ($x = 0$ and $x = 1$).

The Banach fixed-point theorem, also called the contraction mapping principle, gives a clean criterion under which a fixed point not only exists but is unique, and moreover under which the fixed point is constructible by simple iteration from any starting point. Banach proved this theorem in his 1922 paper as a special case of an argument about complete metric spaces. The simplicity of the statement, the cleanness of the proof, and the breadth of the applications have made it one of the most quoted results in modern analysis. This article is about what the theorem says, why it works, and where it shows up.

The statement

Let $(X, d)$ be a complete metric space — a metric space in which Cauchy sequences converge. Let $T : X \to X$ be a contraction mapping: there exists a constant $q$ with $0 \leq q < 1$ such that

$d(T(x), T(y)) \;\leq\; q \cdot d(x, y) \quad \text{for all } x, y \in X.$

Then $T$ has a unique fixed point $x^* \in X$. Moreover, for any starting point $x_0$, the sequence $x_{n+1} = T(x_n)$ converges to $x^*$ as $n \to \infty$, with the convergence rate

$d(x_n, x^*) \;\leq\; \frac{q^n}{1 - q} \cdot d(x_1, x_0).$

The fixed point exists. It is unique. You can find it by iteration. And you have an explicit bound on how close you are after $n$ steps. That is the entire content of the theorem.

A picture of contraction

Take $T(x) = (x + 2)/2$ on the real line. Then $T$ is a contraction with constant $q = 1/2$. Its fixed point is the solution of $x = (x+2)/2$, namely $x^* = 2$. Starting from $x_0 = 4$, the iterates are

$4, 3, 2.5, 2.25, 2.125, 2.0625, \dots$

each one halving the distance to $2$. The picture below uses a classical visualisation called a cobweb diagram to show this convergence: the graph of $y = T(x)$ is a straight line of slope $1/2$, the diagonal $y = x$ is the line of fixed points, and the iteration is the staircase that walks down to where the two lines meet.

The cobweb shows the staircase pattern that is characteristic of contraction iteration: a vertical move to the function graph, then a horizontal move to the diagonal, then a vertical move, then a horizontal move, repeated. The fixed point sits at the intersection of the two lines, and the cobweb spirals in toward it. The convergence rate $q^n$ — halving the distance every step in this case — is exactly the contraction constant raised to the iteration count.

Why the iteration converges

The proof of the theorem is short and elegant. Start from any point $x_0$ and iterate. Then for any $n \geq 1$,

$d(x_n, x_{n-1}) = d(T(x_{n-1}), T(x_{n-2})) \leq q \cdot d(x_{n-1}, x_{n-2}) \leq \cdots \leq q^{n-1} \cdot d(x_1, x_0).$

Successive distances shrink geometrically. By the triangle inequality, for any $m > n$,

$d(x_m, x_n) \leq \sum_{k=n}^{m-1} d(x_{k+1}, x_k) \leq d(x_1, x_0) \sum_{k=n}^{m-1} q^k \leq d(x_1, x_0) \cdot \frac{q^n}{1-q}.$

This goes to zero as $n, m \to \infty$. So the sequence $(x_n)$ is Cauchy. Because $X$ is complete, Cauchy sequences converge, so $x_n \to x^*$ for some $x^* \in X$. By the continuity of $T$ (which follows immediately from being a contraction), $T(x^*) = T(\lim x_n) = \lim T(x_n) = \lim x_{n+1} = x^*$. So $x^*$ is a fixed point.

Uniqueness is even quicker. If $y$ and $z$ are both fixed points, then $d(y, z) = d(T(y), T(z)) \leq q \cdot d(y, z)$. Since $q < 1$, the only way this can hold is $d(y, z) = 0$, i.e., $y = z$.

The proof packages two ideas: completeness (every Cauchy sequence converges) and strict contraction (distances shrink by a factor strictly less than $1$). These two ingredients, together, are enough to guarantee a unique fixed point and a constructive method to find it.

Picard, Newton, and the existence of solutions

The most famous application of Banach’s theorem is to existence theorems for differential equations. Consider the initial-value problem

$\frac{dy}{dt} = f(t, y), \qquad y(t_0) = y_0.$

When does a solution exist? Émile Picard’s 1890 theorem, now a standard textbook result, says: if $f$ is Lipschitz continuous in $y$ (which means $|f(t, y_1) - f(t, y_2)| \leq L|y_1 - y_2|$ for some constant $L$), then the initial-value problem has a unique solution on some interval around $t_0$.

The proof is a Banach fixed-point argument. Reformulate the differential equation as an integral equation:

$y(t) = y_0 + \int_{t_0}^{t} f(s, y(s)) \, ds.$

The right-hand side defines a map $T$ on a suitable function space (continuous functions on a small interval, with the supremum norm). On a sufficiently short interval, this $T$ is a contraction. By Banach’s theorem, it has a unique fixed point — which is exactly the solution to the differential equation.

This is the Picard iteration: start with a guess $y_0(t) = y_0$, then iterate $y_{n+1}(t) = y_0 + \int_{t_0}^{t} f(s, y_n(s)) \, ds$. The iterates converge to the solution. Picard’s theorem on the existence and uniqueness of ODE solutions is, behind the scenes, Banach’s theorem applied in a function space.

The same logic underlies many other existence theorems: the implicit function theorem, the inverse function theorem, the Cauchy–Kowalevski theorem in partial differential equations, the Hartman–Grobman theorem on linearisation of vector fields. In each case, the object whose existence is being asserted is constructed as a fixed point of a carefully chosen contraction, and the technical core of the proof is verifying the contraction condition.

Numerical methods and convergence rates

Banach’s theorem also drives the analysis of iterative numerical algorithms.

Newton’s method for finding roots of $g(x) = 0$ iterates $x_{n+1} = x_n - g(x_n)/g'(x_n)$. Near a simple root, this iteration is a contraction with a contraction constant that depends on the second derivative. The convergence is in fact quadratic — the number of correct digits doubles per iteration — which is the gold standard for numerical root-finding.

Jacobi and Gauss-Seidel methods for solving large linear systems $Ax = b$ iterate by splitting $A$ and treating the iteration as a contraction. The methods converge when a spectral condition (related to the largest eigenvalue of the iteration matrix) is satisfied; the spectral condition is exactly the requirement that the iteration is a contraction in an appropriate norm.

The simplex method for linear programming, while not literally a fixed-point method, shares the same underlying philosophy: convert the problem into an iteration, prove the iteration shrinks something, and bound the convergence.

The theorem’s quiet ubiquity

Banach’s fixed-point theorem is one of those results that, once you know it, you start seeing everywhere. Whenever a sequence converges by repeated application of a map, whenever an existence theorem is proved by constructing the solution as a limit, whenever a numerical iteration’s convergence is established — it is more likely than not a Banach-style argument in disguise.

The reason for this ubiquity is twofold. First, the conditions of the theorem — completeness and strict contraction — are flexible. Contraction can be checked in many different metric spaces, including infinite-dimensional ones, so the same theorem applies to ODEs in function space, to PDEs in Sobolev space, to functional equations in Hilbert space, and many other settings. Second, the conclusion is constructive: not only does the fixed point exist, but it can be found by iteration with an explicit error bound. This makes the theorem useful in pure existence proofs and in numerical computation.

What Banach really gave us in 1922 was a template for constructing solutions: define a function whose fixed point is what you want, verify it shrinks distances, iterate. The simplicity of the recipe and the breadth of its applications has made it one of the small handful of theorems that working analysts truly cannot do without. A theorem you can prove in a page underlies a century of subsequent existence proofs and most of the numerical methods used in scientific computing. That is the mark of a foundational result.

Frequently asked

Who was Banach?

Stefan Banach was a Polish mathematician who founded modern functional analysis. He proved his fixed-point theorem in his 1920 doctoral dissertation, published in expanded form in 1922 in the journal Fundamenta Mathematicae. Banach was self-taught — he had no formal university training in mathematics until his late 20s — and went on to revolutionise the study of infinite-dimensional vector spaces, which now bear his name (Banach spaces). His theorem on contraction mappings is one of the cleanest and most widely applied results in all of analysis.

What is a contraction mapping?

A map T from a metric space to itself is a contraction if there exists a constant q with 0 ≤ q < 1 such that d(T(x), T(y)) ≤ q · d(x, y) for all x, y in the space. In words: T shrinks distances by a factor of at most q every time you apply it. The crucial requirement is that q is strictly less than 1 — q = 1 is not enough. A simple example on the real line is T(x) = (x + c)/2 for any constant c, which has contraction constant q = 1/2 and fixed point at c.

Why does a unique fixed point exist?

Start from any point x₀, and iterate: x₁ = T(x₀), x₂ = T(x₁), and so on. Because T contracts, successive iterates get closer and closer to each other: d(xₙ₊₁, xₙ) ≤ q^n · d(x₁, x₀). The sequence is Cauchy, and since the metric space is complete, it converges to some limit x*. By continuity of T, applying T to both sides of x_(n+1) = T(xₙ) and taking the limit gives x* = T(x*), so x* is a fixed point. Uniqueness follows from the contraction property: if T had two fixed points y and z, then d(y, z) = d(T(y), T(z)) ≤ q · d(y, z) forces d(y, z) = 0.

What is the theorem actually used for?

It is the standard tool for proving that something exists by constructing it as a fixed point of a contraction. Picard's theorem on the existence and uniqueness of solutions to ordinary differential equations applies Banach's theorem to an integral-equation reformulation. Newton's method for finding roots of equations converges quadratically when the iteration is a contraction in a neighbourhood of the root. The implicit function theorem, the inverse function theorem, and many proofs in dynamical systems rest on similar fixed-point arguments. Iterative numerical algorithms in linear algebra, optimisation, and PDE solvers usually have convergence guarantees that come down to verifying a contraction condition.

Continue reading

Blog

The Weierstrass Function: A Curve That Is Continuous Everywhere and Smooth Nowhere

Until 1872, mathematicians assumed continuous functions had to be differentiable somewhere. Karl Weierstrass constructed one that is differentiable nowhere — and analysis had to be rebuilt.

Read →Blog

The Cauchy–Schwarz Inequality: One Line, a Thousand Uses

For any two vectors in any inner-product space, the dot product is bounded by the product of the lengths. From that one line follow the triangle inequality, variance bounds, and much more.

Read →Blog

Lagrange Multipliers: How to Optimise When You Are Not Free to Move Anywhere

At a maximum of a function on a curve, the contour lines must run parallel to the curve. That geometric fact turns one of the hardest problems in calculus into a tidy system of equations.

Read →