Banach's fixed-point theorem

In the area of metric spaces a category of Mathematics, the Banach's fixed-point theorem states that a contracting map in a complete metric space has a unique fixed-point.

Proof

Given a contracting map, i.e. f:X→X with a constant c<1 such that

$\forall x,y\in X:\rho (f(x),f(y))\leq c\rho (x,y)$

we consider the sequences x₀ ∈ X and x_n+1 = f(x_n) which are Cauchy sequences, because for m ≤ n we have

$\rho (x_{m},x_{n})\leq \rho (x_{m},x_{m+1})+\dots +\rho (x_{n-1},x_{n})\leq (c^{m}+\dots +c^{n-1})\rho (x_{0},x_{1})\leq {\frac {c^{m}}{1-c}}\rho (x_{0},x_{1})$.

If we can ensure that Cauchy sequences converge (the completeness condition), then we have a fixed point.

Uniqueness follows, because for two fixed points x and y ∈ X we observe

$\rho (x,y)=\rho (f(x),f(y)\leq c\rho (x,y)\Rightarrow \rho (x,y)=0$

which implies x=y due to the properties of the metric.

Statement

Given a complete metric space (X,ρ), i.e. a metric space in which every Cauchy sequence {x_n} ⊂ X, i.e. for every ε>0, there is an N such that m, n ≥ N implies ρ(x_m,x_n) < ε, has a limit, i.e. a point x ∈ X such that every ε>0 has an N such that n ≥ N implies ρ(x,x_n) < ε. Given further a contracting map f: X→X, i.e. there is a c < 1 such that

$\forall x,y\in X:\rho (f(x),f(y))\leq c\rho (x,y)$,

then there is a unique x ∈ X such that

$f(x)=x$,

i.e. x is a fixed-point of f.

Note that if f is not contracting, e.g. we can only assert $\rho (f(x),f(y))\leq \rho (x,y)$, then there might neither be a fixed-point, e.g. the map f:R→R:x→x+1, nor if there is any fixed-point need it be unique, e.g. the map id:X→X:x→x. If the map is only weakly contracting, i.e. $\rho (f(x),f(y))<\rho (x,y)$ there might not be a fixed-point, but if there is one, then it is unique.

Applications

rth root

Heron's and Newton's formulas for computing the rth root of a positive number. Let a > 0 and r > 0 be any positive numbers. from continuity and monotonicity we know that the equation

$x^{r}-a=0$

has a unique positive solution.

In the case r=2, Heron found the iterative formula $x_{n+1}=(x_{n}+a/x_{n})/2$ which converges for any x₀ > 0 to the square root of a, because the map f:R→R:x→ (x+a/x)/2 is contracting on the interval (ε,a) with ε=2a/(a+1) which can be checked estimating the derivative of f on the interval.

For arbitrary r we consider the function g(x) = x^r-a and build the iteration

$f(x_{n})=x_{n}-{\frac {g(x_{n})}{g'(x_{n})}}$.

For the derivative we have

$f'(x)=(1-{\tfrac {1}{r}})x^{r-1}{\frac {x^{r}-a}{x^{2r-2}}}$

which vanishes at the fixed-point. Therefore there is a neighborhood of the fixed point for which the Newton iteration converges better than linear, namely quadratic, i.e. the error decreases as

$\rho (x_{n},x)\leq \rho (x_{0},x)c^{n^{2}}$

for some 0<c<1.

Solution of a linear ordinary differential equation

Let

$y'+ly=g$

be an ordinary differential equation with continuous functions l and g on some interval [a,b]. Let further x₀ ∈ [a,b] together with c ∈ R. Then the ODE with the initial condition

$y(x_{0})=c$

has locally a unique solution. The idea dating back to Picard is to use the complete metric space C[a,b] of continuously functions on the interval, to replace the differential equation by the integral equation

$y(x)=c+\int _{x_{0}}^{x}g(t)-l(t)y(t)\,\mathrm {d} t$

and to show that the iteration

$F(f_{n})(x)=c+\int _{x_{0}}^{x}g(t)-l(t)f_{n}(t)\,\mathrm {d} t$

is contracting if we reduce the interval to [x₀-ε,x₀+ε] with ε < 1/max |l| on [a,b].

Gluing together solutions we obtained for the smaller intervals, we can construct a unique solution on the whole interval [a,b]. Using the vector valued version of the theorem, we can also prove the existence and uniqueness of solutions of dth order linear ODEs. The statement in the nonlinear case is a local one (i.e. there is an ε > 0) as long as the implicit ODE

$F(y^{(d)},y^{(d-1)},\dots ,y)=0$

is continuous in all ys and F has a partial derivative with respect to the highest order y^(d) is bounded away from 0.

Uniqueness of self-similar fractals

Another application is in the realm of fractals, namely an iterated function system is the union of a number of contracting maps

$S\colon 2^{X}\to 2^{X}:F\mapsto \bigcup _{i=1}^{N}S_{i}(F)$

where the S_i: X→X are all contracting. The theorem then states that in the complete metric space of compact nonempty subsets of X with the Hausdorff metric

$\rho (S,T)=\inf\{\delta \geq 0:S\subset T_{\delta }\land T\subset S_{\delta }\}$

where S_δ is the δ-parallel extension of S there is a unique compact nonempty set F ⊂ X such that S(F) = F, i.e. a fixed-set.

Literature

The theorem is standard in analysis and can thus be found in every introductory textbook about analysis.