The Banach fixed-point theorem

Theorem

The Banach fixed-point theorem

T-081Home MU-301Threads space

Statement

Let \( (X,d) \) be a non-empty complete metric space and let \( T : X \to X \) be a contraction, meaning there exists a constant \( k \) with \( 0 \le k \lt 1 \) such that \( d(Tx,Ty) \le k\, d(x,y) \) for all \( x,y \in X \). Then \( T \) has exactly one fixed point \( x^\ast \in X \), i.e. a unique \( x^\ast \) with \( Tx^\ast = x^\ast \); moreover, for any \( x_0 \in X \), the iterates \( x_{n+1} = Tx_n \) converge to \( x^\ast \), with the explicit a priori error bound \( d(x_n, x^\ast) \le \dfrac{k^n}{1-k}\, d(x_1,x_0) \).

Why it matters

The Banach fixed-point theorem (also called the contraction mapping principle) is the single most useful existence-and-uniqueness engine in analysis. It converts a differential, integral, or functional equation into a statement "\( T \) has a fixed point", and it does so constructively: the proof is the algorithm, and it comes with a computable error bound. This is what makes Picard–Lindelöf, the inverse function theorem, and iterative numerical schemes (Newton's method in disguise, fixed-point iteration for linear systems) all instances of one abstract argument.

Its real force is structural: it isolates exactly two hypotheses — completeness of the space and a uniform contraction ratio — and shows they are jointly sufficient for existence, uniqueness, and algorithmic convergence at a guaranteed geometric rate. Dropping either hypothesis breaks the conclusion, as the counterexamples below show, which is precisely why the theorem is stated with such care.

Hypotheses

Completeness of \( (X,d) \).On \( X=(0,1] \) with the usual metric (incomplete), \( Tx = x/2 \) is a contraction with \( k=1/2 \) but has no fixed point in \( X \): the only candidate is \( x=0 \), which is missing from the space. The Cauchy iterates "want" to converge but have nowhere to land. Non-emptiness of \( X \).If \( X=\varnothing \) the statement "there exists a unique fixed point" is vacuously false (existence fails), so it must be assumed explicitly; every non-trivial application supplies a specific point to start the iteration. Uniformity of the contraction constant \( k \lt 1 \) (a single constant, not merely \( d(Tx,Ty) \lt d(x,y) \) pointwise).On \( X=[1,\infty) \) with \( Tx = x + 1/x \), one has \( d(Tx,Ty) \lt d(x,y) \) for all \( x \ne y \) (strictly non-expansive), yet no single \( k\lt1 \) works uniformly, and indeed \( T \) has no fixed point at all: \( Tx=x \) forces \( 1/x=0 \), impossible. Merely "moving points closer together" is not enough; the contraction ratio must be bounded away from \( 1 \). \( T \) maps \( X \) into itself.If \( T:X\to Y \) with \( Y \not\subseteq X \), the composite iterates \( x_{n+1}=Tx_n \) are not even well-defined as a self-map, so the recursive construction cannot start; this is implicit in writing "\( T:X\to X \)" but worth flagging since in applications (e.g. operators on function spaces) checking self-mapping is often the hard part.

Proof

\text{Fix any } x_0 \in X \text{ and define } x_{n+1} = Tx_n \text{ for } n \ge 0.

Well-defined because \( T:X\to X \); this is the Picard iteration sequence. A

d(x_{n+1},x_n) \le k^n\, d(x_1,x_0) \quad \text{for all } n \ge 0.

Induction on \( n \): the base case \( n=0 \) is trivial, and \( d(x_{n+1},x_n)=d(Tx_n,Tx_{n-1}) \le k\,d(x_n,x_{n-1}) \le k\cdot k^{n-1}d(x_1,x_0)=k^n d(x_1,x_0) \) by the contraction hypothesis applied to \( x_n,x_{n-1} \). A

d(x_{n+p},x_n) \le \sum_{i=0}^{p-1} d(x_{n+i+1},x_{n+i}) \le \sum_{i=0}^{p-1} k^{n+i}\, d(x_1,x_0) \le \frac{k^n}{1-k}\, d(x_1,x_0)

Triangle inequality repeated \( p-1 \) times, then Step 2 termwise, then the geometric series bound \( \sum_{i=0}^{p-1}k^i \le \sum_{i=0}^{\infty}k^i = \frac{1}{1-k} \), valid since \( 0\le k\lt1 \). B

(x_n)_{n\ge0} \text{ is a Cauchy sequence in } (X,d).

Since \( k^n \to 0 \) (as \( 0\le k\lt1 \)), the right-hand side of Step 3 tends to \( 0 \) as \( n\to\infty \), uniformly in \( p \); hence given \( \varepsilon\gt0 \) choose \( N \) with \( \frac{k^N}{1-k}d(x_1,x_0) \lt \varepsilon \), and then \( d(x_{n+p},x_n)\lt\varepsilon \) for all \( n\ge N,\, p\ge0 \), which is precisely the Cauchy criterion. B

\exists\, x^\ast \in X \text{ such that } x_n \to x^\ast.

By hypothesis \( (X,d) \) is complete: every Cauchy sequence in \( X \) converges to a limit in \( X \). Apply this to the Cauchy sequence from Step 4. This is the only place completeness is used, and it is essential (see Fails without). B

Tx^\ast = x^\ast.

\( T \) is continuous, because it is Lipschitz: \( d(Tx,Ty)\le k\,d(x,y) \to 0 \) as \( d(x,y)\to0 \). Continuity lets limits pass through \( T \): \( Tx^\ast = T(\lim_n x_n) = \lim_n Tx_n = \lim_n x_{n+1} = x^\ast \), the last equality because \( (x_{n+1}) \) is a subsequence (indeed a shift) of the convergent sequence \( (x_n) \) and so has the same limit. C

\text{If } Tx=x \text{ and } Ty=y \text{ then } x=y.

Uniqueness. Compute \( d(x,y)=d(Tx,Ty)\le k\,d(x,y) \), so \( (1-k)\,d(x,y)\le 0 \). Since \( 1-k\gt0 \) and \( d(x,y)\ge0 \), this forces \( d(x,y)=0 \), i.e. \( x=y \) by the metric axiom \( d(x,y)=0 \iff x=y \). A

d(x_n,x^\ast) \le \frac{k^n}{1-k}\, d(x_1,x_0)

Error bound. Let \( p\to\infty \) in Step 3 with \( x_{n+p}\to x^\ast \) (Step 5) and use continuity of \( y \mapsto d(x_n,y) \) (a standard consequence of the triangle inequality: \( |d(x_n,y)-d(x_n,y')|\le d(y,y') \)) to pass the limit inside the distance. This gives the explicit, computable convergence rate. C

Result

T:X\to X \text{ contraction on complete } (X,d) \;\Longrightarrow\; \exists! \, x^\ast \in X,\ Tx^\ast=x^\ast,\ \ x_n=T^n x_0 \to x^\ast \ \text{geometrically}

Reading. Repeatedly applying a "distance-shrinking" map on a space with no gaps always settles down onto exactly one point, no matter where you start, and it settles down at a guaranteed exponential rate governed by the contraction constant \( k \).

Scope. Applies to any complete metric space — finite-dimensional \( \mathbb{R}^n \), Banach spaces of functions, spaces of compact sets with the Hausdorff metric, etc. — and to any single map satisfying one uniform Lipschitz bound \( k\lt1 \) globally on \( X \). It does not by itself apply to maps that are only "locally" contractive, only non-expansive (\( k=1 \) allowed), or defined on incomplete spaces; those need separate arguments (see Fails without and Corollaries).

Corollaries & converses

Local version. If \( T \) is a contraction only on a closed ball \( \bar B(x_0,r)\subseteq X \) and maps it into itself, the theorem still applies to \( T \) restricted to \( \bar B(x_0,r) \), which is complete as a closed subset of a complete space — this is the form used in Picard–Lindelöf.
Continuous dependence on parameters. If \( T_\lambda \) is a family of contractions with a common constant \( k \) depending continuously on a parameter \( \lambda \), the fixed point \( x^\ast(\lambda) \) depends continuously on \( \lambda \) (and, under extra smoothness, differentiably — this underlies the implicit function theorem).
Converse is false. A map can have a unique fixed point, and even globally attracting dynamics, without being a contraction in any metric compatible with the topology at all uniform rates; e.g. \( Tx = x/2 \) on \( \mathbb{R} \) works, but many non-contractive maps (e.g. \( Tx=\cos x \) on \( \mathbb{R} \), not a global contraction since \( |T'|\le1 \) with equality approached) still have unique attracting fixed points by other mechanisms. Existence/uniqueness of a fixed point does not imply the hypotheses of this theorem hold.
Weakening \( k\lt1 \) to \( d(Tx,Ty)\lt d(x,y) \) (contractive but not uniformly) is not sufficient in general for existence, only for uniqueness when a fixed point happens to exist — see the Fails without example.

Fails without

Completeness dropped: \( X=(0,1] \) with \( d(x,y)=|x-y| \), \( Tx=x/2 \). This is a contraction with \( k=1/2 \), but \( T \) has no fixed point in \( X \): the iterates \( x_n = x_0/2^n \to 0 \notin X \). The Cauchy sequence from Step 4 exists but Step 5 fails because \( X \) is not complete.
Uniform \( k\lt1 \) dropped (only pointwise contractivity): \( X=[1,\infty) \) with the usual metric, \( Tx = x + \frac1x \). Then \( d(Tx,Ty) \lt d(x,y) \) for all \( x\ne y \) in \( X \) (by the mean value theorem, since \( |T'(x)|=|1-1/x^2|\lt1 \) for \( x\gt1 \)), yet \( \sup_{x\ne y} \frac{d(Tx,Ty)}{d(x,y)} = 1 \) (no uniform gap below \( 1 \)), and indeed \( Tx=x \) has no solution in \( X \) — existence fails entirely, not just uniqueness.
\( T \) not self-mapping: \( X=[0,1] \), \( Tx = x+1 \) restricted to inputs in \( [0,1] \) sends every point outside \( X \); the iteration is not even defined past step one, illustrating why "\( T:X\to X \)" is load-bearing, not decorative.

Common errors

Confusing "non-expansive" (\( d(Tx,Ty)\le d(x,y) \)) or "contractive" (\( d(Tx,Ty)\lt d(x,y) \), no uniform bound) with "contraction" (\( d(Tx,Ty)\le k\,d(x,y) \), fixed \( k\lt1 \)); only the last guarantees existence in general.
Forgetting to check that \( T \) actually maps \( X \) (or the chosen closed ball) into itself before invoking the theorem — a very common gap when \( T \) is an integral or differential operator on a function space.
Applying the theorem on a subset that is complete-looking but is not closed in a complete ambient space (e.g. an open ball), and so is not itself complete.
Estimating the contraction constant \( k \) only "at the fixed point" (via a derivative bound at one point) rather than uniformly over all of \( X \); local Lipschitz behaviour near \( x^\ast \) does not establish the global hypothesis.
Misquoting the error bound as \( d(x_n,x^\ast)\le k^n d(x_1,x_0) \) (missing the \( \frac{1}{1-k} \) factor), or confusing the a priori bound (from \( x_0,x_1 \)) with the sharper a posteriori bound \( d(x_n,x^\ast)\le \frac{k}{1-k}d(x_n,x_{n-1}) \).

Discussion

The theorem is due to Stefan Banach (1922), who abstracted it from earlier iterative existence proofs for differential and integral equations — most notably Picard's method of successive approximations (1890) for ordinary differential equations, and Liouville's and Neumann's iterative solutions of integral equations in the 19th century. Banach's contribution was to strip away the specific setting and recognise completeness plus a uniform contraction ratio as the exact abstract ingredients needed, packaging existence, uniqueness, and a constructive algorithm with an explicit error bound into one statement.

Its reach is enormous precisely because "complete metric space" and "contraction" are so easy to manufacture: one takes a space of candidate solutions (continuous functions, sequences, compact sets) with a suitable metric, defines \( T \) so that fixed points of \( T \) are exactly solutions of the original problem, and checks the two hypotheses. This is how the Picard–Lindelöf existence-and-uniqueness theorem for ODEs, the inverse and implicit function theorems, existence of solutions to certain integral equations, and even the existence of fractal attractors (via the Hutchinson operator on the space of compact sets with the Hausdorff metric) are all proved.

A subtler point: the theorem gives global convergence from any starting point, which is stronger than merely finding a fixed point locally via, say, the intermediate value theorem or degree theory in \( \mathbb{R}^n \) — those give existence without a convergence algorithm or a rate. The trade-off is that the contraction hypothesis is comparatively restrictive: many maps with unique fixed points (e.g. rotations composed with damping, or maps that are merely non-expansive) fall outside its scope and need separate tools (Brouwer, Schauder, or Edelstein's theorem for compact spaces with contractive-but-not-uniform maps).

Common misconception: that "contraction" just means "brings points closer together". As the \( Tx=x+1/x \) counterexample shows, pointwise contractivity without a uniform ratio \( k\lt1 \) is not enough — the sequence of contraction ratios can tend to \( 1 \) as \( x,y\to\infty \), and existence genuinely fails. The uniform bound is what forces the geometric decay in Step 3.

Worked examples

\text{Solve } x = \tfrac12\cos x \text{ in } \mathbb{R}, \text{ i.e. find the fixed point of } Tx=\tfrac12\cos x.

Set up \( X=\mathbb{R} \) with the usual metric (complete, since \( \mathbb{R} \) is complete), and \( T:\mathbb{R}\to\mathbb{R} \), \( Tx=\tfrac12\cos x \). A

|Tx-Ty| = \tfrac12|\cos x-\cos y| \le \tfrac12|x-y| \quad \text{(so } k=\tfrac12\text{)}

By the mean value theorem, \( \cos x - \cos y = -\sin(\xi)(x-y) \) for some \( \xi \) between \( x,y \), and \( |\sin\xi|\le1 \), giving the Lipschitz bound with constant \( \tfrac12 \); since \( 0\le\tfrac12\lt1 \), \( T \) is a contraction on all of \( \mathbb{R} \), and \( T \) maps \( \mathbb{R}\to\mathbb{R} \) trivially. B

x_0=0,\ x_1=\tfrac12,\ x_2=\tfrac12\cos(\tfrac12)\approx0.4388,\ x_3\approx0.4515,\dots

Apply the Picard iteration of Step 1 of the proof; by Step 8 of the proof, \( |x_n-x^\ast|\le \frac{(1/2)^n}{1/2}\,|x_1-x_0| = (1/2)^{n-1}\cdot\tfrac12 \), so accuracy \( 10^{-6} \) needs only about \( n\approx 21 \) iterations. A

\exists! \; x^\ast\in\mathbb{R} \text{ with } x^\ast=\tfrac12\cos x^\ast,\qquad x^\ast \approx 0.45018

Reading. The theorem guarantees this fixed point exists, is unique, and can be computed to any accuracy by simple iteration with a known error bound — no separate existence argument (e.g. IVT) or uniqueness argument is needed.

\text{Prove } y' = f(t,y),\ y(t_0)=y_0 \text{ has a unique local solution when } f \text{ is Lipschitz in } y.

Picard–Lindelöf. Let \( f \) be continuous on a strip and Lipschitz in \( y \) with constant \( L \): \( |f(t,y_1)-f(t,y_2)|\le L|y_1-y_2| \). Reformulate the IVP as the integral equation \( y(t) = y_0 + \int_{t_0}^{t} f(s,y(s))\,ds \), and define \( (Ty)(t) = y_0+\int_{t_0}^t f(s,y(s))\,ds \) on \( X=C[t_0-h,t_0+h] \) with the metric \( d(y,z)=\sup_t |y(t)-z(t)| \), which is complete (uniform limit of continuous functions is continuous). B

|(Ty)(t)-(Tz)(t)| \le \int_{t_0}^{t} |f(s,y(s))-f(s,z(s))|\,ds \le Lh\, d(y,z)

Bound the integrand by the Lipschitz condition on \( f \), then bound the integral length by \( h \) and pull the sup-distance \( d(y,z) \) out of the integral; taking sup over \( t \) gives \( d(Ty,Tz)\le Lh\,d(y,z) \). B

\text{Choose } h \lt \tfrac1L \text{ so that } k:=Lh \lt 1.

This is legal because \( h \) is at our disposal — we only need a local solution, so we may shrink the interval \( [t_0-h,t_0+h] \) until the constant \( Lh \) drops below \( 1 \); this yields a genuine contraction on \( X \). C

\exists! \, y\in C[t_0-h,t_0+h] \text{ with } y(t)=y_0+\int_{t_0}^t f(s,y(s))\,ds \;\Longleftrightarrow\; \exists! \text{ solution to the IVP on } [t_0-h,t_0+h]

Reading. The Banach fixed-point theorem, applied to the "integrate-and-substitute" operator on a space of continuous functions, is the entire content of the Picard–Lindelöf existence-and-uniqueness theorem for ODEs.

Problems

Show that \( Tx = \sqrt{x+2} \) is a contraction on \( X=[1,2] \) (with the usual metric), and find its unique fixed point directly, checking it against the value the theorem's iteration converges to starting from \( x_0=1 \).
Solution
First check \( T \) maps \( [1,2] \) into itself: for \( x\in[1,2] \), \( x+2\in[3,4] \), so \( Tx=\sqrt{x+2}\in[\sqrt3,2]\subseteq[1,2] \). For the Lipschitz bound, \( T'(x)=\frac{1}{2\sqrt{x+2}} \), and on \( [1,2] \), \( \sqrt{x+2}\ge\sqrt3 \), so \( |T'(x)|\le \frac{1}{2\sqrt3}\approx0.2887=:k\lt1 \); by the mean value theorem \( |Tx-Ty|\le k|x-y| \), so \( T \) is a contraction on the complete space \( [1,2] \) (closed subset of \( \mathbb{R} \)). By the theorem a unique fixed point exists. Solving directly: \( x=\sqrt{x+2}\Rightarrow x^2=x+2\Rightarrow x^2-x-2=0\Rightarrow(x-2)(x+1)=0\Rightarrow x=2 \) (rejecting \( x=-1\notin[1,2] \)). Iterating from \( x_0=1 \): \( x_1=\sqrt3\approx1.732,\ x_2=\sqrt{3.732}\approx1.932,\ x_3\approx1.983,\dots\to2 \), matching the direct solution.
Let \( X=\mathbb{R}^n \) with the Euclidean metric and \( A \) an \( n\times n \) real matrix with operator norm \( \|A\|\lt1 \). Show \( Tx=Ax+b \) (for fixed \( b\in\mathbb{R}^n \)) has a unique fixed point, and interpret it as the solution of a linear system.
Solution
\( \mathbb{R}^n \) is complete. For \( x,y\in\mathbb{R}^n \), \( \|Tx-Ty\| = \|A(x-y)\| \le \|A\|\,\|x-y\| \) by definition of the operator norm, and \( k=\|A\|\lt1 \) by hypothesis, so \( T \) is a contraction; the theorem gives a unique \( x^\ast \) with \( Ax^\ast+b=x^\ast \), i.e. \( (I-A)x^\ast=b \). This also reproves that \( I-A \) is invertible whenever \( \|A\|\lt1 \) (via the Neumann series \( (I-A)^{-1}=\sum_{n=0}^\infty A^n \)), with \( x^\ast=(I-A)^{-1}b \) obtained constructively as the limit of the Picard iteration \( x_{n+1}=Ax_n+b \).
Give an example of a map \( T \) on a complete metric space with \( d(Tx,Ty)\lt d(x,y) \) for all \( x\ne y \) (strictly contractive pointwise) that has no fixed point, and explain precisely which step of the proof breaks.
Solution
Take \( X=[1,\infty) \) with the usual (complete) metric and \( Tx=x+\frac1x \). For \( x\ne y \) in \( X \), the mean value theorem gives \( Tx-Ty=(1-\frac{1}{\xi^2})(x-y) \) for some \( \xi \) between \( x,y \), and since \( \xi\ge1 \), \( 0\le 1-\frac1{\xi^2}\lt1 \), so \( |Tx-Ty|\lt|x-y| \) strictly. However \( \sup_{\xi\ge1}(1-1/\xi^2)=1 \) (approached as \( \xi\to\infty \)), so no single \( k\lt1 \) bounds the ratio uniformly. The proof breaks at Step 2/3: the geometric bound \( d(x_{n+1},x_n)\le k^n d(x_1,x_0) \) required a fixed \( k\lt1 \); without it \( (x_n) \) need not be Cauchy. Indeed here \( x_{n+1}-x_n=1/x_n\to0 \) but slowly enough (like \( \sqrt{2n} \) growth, since \( x_n\approx\sqrt{2n} \)) that \( x_n\to\infty \), not converging in \( X \) at all, consistent with \( Tx=x \) having no solution.
Let \( (X,d) \) be complete and let \( T:X\to X \) satisfy: \( T \) itself is not a contraction, but some iterate \( T^m \) (for fixed integer \( m\ge2 \)) is a contraction. Prove \( T \) still has a unique fixed point in \( X \).
Solution
Apply the theorem to \( S:=T^m \), a contraction on the complete space \( X \), to get a unique \( x^\ast \) with \( Sx^\ast=x^\ast \), i.e. \( T^m x^\ast=x^\ast \). Now show \( Tx^\ast=x^\ast \): apply \( T \) to both sides of \( T^m x^\ast=x^\ast \) to get \( T^m(Tx^\ast) = T(T^m x^\ast) = Tx^\ast \), so \( Tx^\ast \) is also a fixed point of \( S=T^m \). By uniqueness of the fixed point of \( S \) (proved in Step 7 of the main proof), \( Tx^\ast = x^\ast \). So \( x^\ast \) is a fixed point of \( T \). For uniqueness under \( T \): any fixed point of \( T \) satisfies \( Tx=x\Rightarrow T^mx=x \), so it is a fixed point of \( S \), hence equals \( x^\ast \) by uniqueness for \( S \). Thus \( T \) has the same unique fixed point as \( T^m \).
Use the theorem to prove the existence of a unique solution \( y\in C[0,1] \) to the linear Fredholm integral equation \( y(t) = g(t) + \lambda\int_0^1 K(t,s)y(s)\,ds \), where \( g\in C[0,1] \), \( K \) is continuous on \( [0,1]^2 \) with \( |K(t,s)|\le M \) for all \( t,s \), and \( |\lambda| \lt 1/M \).
Solution
Let \( X=C[0,1] \) with \( d(y,z)=\sup_{t\in[0,1]}|y(t)-z(t)| \); this is complete since a uniform limit of continuous functions on a compact interval is continuous (standard result from real analysis). Define \( (Ty)(t) = g(t)+\lambda\int_0^1 K(t,s)y(s)\,ds \). \( T \) maps \( X\to X \) because \( K \) and \( y \) are continuous and the integral of a continuous function of \( (t,s) \) over the compact interval \( s\in[0,1] \) is continuous in \( t \) (standard continuity-of-integrals-with-parameter result). For the contraction estimate: \[|(Ty)(t)-(Tz)(t)| = |\lambda|\left|\int_0^1 K(t,s)(y(s)-z(s))\,ds\right| \le |\lambda|\, M \int_0^1 |y(s)-z(s)|\,ds \le |\lambda| M\, d(y,z),\] using \( |K(t,s)|\le M \) and bounding \( |y(s)-z(s)|\le d(y,z) \) uniformly, then the interval has length \( 1 \). Taking sup over \( t \) gives \( d(Ty,Tz)\le |\lambda|M\, d(y,z) \), and \( k:=|\lambda|M\lt1 \) by hypothesis. By the theorem, \( T \) has a unique fixed point \( y^\ast\in C[0,1] \), which is exactly the unique continuous solution of the integral equation, obtainable as the limit of \( y_{n+1}=Ty_n \) (the classical Neumann series / successive-approximations method for Fredholm equations).