View source for Banach's fixed-point theorem

{{subpages}}
In the area of [[metric space]]s 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
:<math>\forall x,y\in X: \rho(f(x),f(y))\le c\rho(x,y)</math>
we consider the sequences ''x''<sub>0</sub> ∈ ''X'' and ''x''<sub>''n''+1</sub> = ''f''(''x''<sub>''n''</sub>) which are Cauchy sequences, because for ''m'' ≤ ''n'' we have
:<math> \rho(x_m,x_n)\le\rho(x_m,x_{m+1})+\dots+\rho(x_{n-1},x_n)\le (c^m+\dots+c^{n-1})\rho(x_0,x_1) \le \frac{c^m}{1-c}\rho(x_0,x_1)</math>.
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
:<math> \rho(x,y)=\rho(f(x),f(y)\le c\rho(x,y) \Rightarrow \rho(x,y)=0</math>
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''<sub>''n''</sub>} ⊂ ''X'', i.e. for every ε>0, there is an ''N'' such that ''m'', ''n'' ≥ ''N'' implies ρ(''x''<sub>''m''</sub>,''x''<sub>''n''</sub>) < ε, has a [[limit (Mathematics)|limit]], i.e. a point ''x'' ∈ ''X'' such that every ε>0 has an ''N'' such that ''n'' ≥ ''N'' implies ρ(''x'',''x''<sub>''n''</sub>) < ε.  Given further a contracting map ''f'': ''X''→''X'', i.e. there is a ''c'' < 1 such that
:<math>\forall x,y\in X: \rho(f(x),f(y))\le c\rho(x,y)</math>,
then there is a unique ''x'' ∈ ''X'' such that
:<math> f(x)=x</math>,
i.e. ''x'' is a fixed-point of ''f''.

Note that if ''f'' is not contracting, e.g. we can only assert <math>\rho(f(x),f(y))\le\rho(x,y)</math>, 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. <math>\rho(f(x),f(y)) < \rho(x,y)</math> there might not be a fixed-point, but if there is one, then it is unique.


== Applications ==
=== ''r''th root ===
Heron's and Newton's formulas for computing the ''r''th root of a positive number.  Let ''a'' > 0 and ''r'' > 0 be any positive numbers.  from continuity and monotonicity we know that the equation 
:<math> x^r-a = 0</math>
has a unique positive solution.

In the case ''r''=2, Heron found the iterative formula <math>x_{n+1} = (x_n +a/x_n)/2</math> which converges for any ''x''<sub>0</sub> > 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 ε=2''a''/(''a''+1) which can be checked estimating the derivative of ''f'' on the interval.

For arbitrary ''r'' we consider the function ''g''(''x'') = ''x''<sup>''r''</sup>-''a'' and build the iteration
:<math> f(x_n) = x_n -\frac{g(x_n)}{g'(x_n)}</math>.
For the derivative we have
:<math> f'(x) = (1-\tfrac1r)x^{r-1}\frac{x^r-a}{x^{2r-2}}</math>
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
:<math> \rho(x_n,x)\le \rho(x_0,x)c^{n^2}</math>
for some 0<''c''<1.


=== Solution of a linear ordinary differential equation ===
Let 
:<math> y'+ly = g</math> 
be an ordinary differential equation with continuous functions ''l'' and ''g'' on some interval [''a'',''b''].  Let further ''x''<sub>0</sub> ∈ [''a'',''b''] together with ''c'' ∈ ''R''.  Then the ODE with the initial condition
:<math> y(x_0) = c</math>
has locally a unique solution.  The idea dating back to Picard is to use the complete metric space C<sup>1</sup>[''a'',''b''] of continuously differentiable functions on the interval, to replace the differential equation by the integral equation
:<math> y(x) = c+\int_{x_0}^x g(t) -l(t)y(t) \,\mathrm{d}t</math>
and to show that the iteration
:<math> F(f_n)(x) = c+\int_{x_0}^x g(t) -l(t)f_n(t) \,\mathrm{d}t</math>
is contracting if we reduce the interval to [''x''<sub>0</sub>-ε,''x''<sub>0</sub>+ε] 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 ''d''th order linear ODEs.  The statement in the nonlinear case is a local one as long as the implicit ODE
:<math> F(y^{(d)},y^{(d-1)},\dots,y) = 0</math>
is continuous in all ''y''s and ''F'' has a partial derivative bounded away from 0 with respect to the highest order ''y''<sup>(''d'')</sup>.

=== 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
:<math> S\colon 2^X\to 2^X: F\mapsto \bigcup_{i=1}^N S_i(F)</math>
where the ''S''<sub>''i''</sub>: ''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
:<math> \rho(S,T) = \inf\{\delta\ge0: S\subset T_\delta \land T\subset S_\delta\}</math>
where ''S''<sub>δ</sub> 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.