Difference between revisions of "Banach's fixed-point theorem"

From Citizendium
Jump to: navigation, search
m (solution of a linear ordinary differential equation: typesetting improved)
(Solution of a linear ordinary differential equation: metric space for the iteration corrected)
 
Line 47: Line 47:
 
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
 
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>
 
:<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
+
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
 
:<math> y(x) = c+\int_{x_0}^x g(t) -l(t)y(t) \,\mathrm{d}t</math>
 
:<math> y(x) = c+\int_{x_0}^x g(t) -l(t)y(t) \,\mathrm{d}t</math>
 
and to show that the iteration
 
and to show that the iteration
Line 53: Line 53:
 
is contracting if we reduce the interval to [''x''<sub>0</sub>-ε,''x''<sub>0</sub>+ε] with ε < 1/max |l| on [''a'',''b''].
 
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
+
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 (i.e. there is an ε > 0) as long as the implicit ODE
 
:<math> F(y^{(d)},y^{(d-1)},\dots,y) = 0</math>
 
:<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>.
+
is continuous in all ''y''s and ''F'' has a partial derivative with respect to the highest order ''y''<sup>(''d'')</sup> is bounded away from 0.
  
 
=== Uniqueness of self-similar fractals ===
 
=== Uniqueness of self-similar fractals ===

Latest revision as of 11:49, 16 January 2012

This article is developing and not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and subject to a disclaimer.

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:XX with a constant c<1 such that

we consider the sequences x0X and xn+1 = f(xn) which are Cauchy sequences, because for mn we have

.

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 yX we observe

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 {xn} ⊂ X, i.e. for every ε>0, there is an N such that m, nN implies ρ(xm,xn) < ε, has a limit, i.e. a point xX such that every ε>0 has an N such that nN implies ρ(x,xn) < ε. Given further a contracting map f: XX, i.e. there is a c < 1 such that

,

then there is a unique xX such that

,

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

Note that if f is not contracting, e.g. we can only assert , then there might neither be a fixed-point, e.g. the map f:RR:xx+1, nor if there is any fixed-point need it be unique, e.g. the map id:XX:xx. If the map is only weakly contracting, i.e. 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

has a unique positive solution.

In the case r=2, Heron found the iterative formula which converges for any x0 > 0 to the square root of a, because the map f:RR: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) = xr-a and build the iteration

.

For the derivative we have

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

for some 0<c<1.


Solution of a linear ordinary differential equation

Let

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

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

and to show that the iteration

is contracting if we reduce the interval to [x0-ε,x0+ε] 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

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

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

where Sδ is the δ-parallel extension of S there is a unique compact nonempty set FX 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.