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

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 | + | 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 | + | 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

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.

## Contents

## Proof

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

we consider the sequences *x*_{0} ∈ *X* and *x*_{n+1} = *f*(*x*_{n}) which are Cauchy sequences, because for *m* ≤ *n* 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 *y* ∈ *X* 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 {*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

- ,

then there is a unique *x* ∈ *X* 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*:**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. 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

has a unique positive solution.

In the case *r*=2, Heron found the iterative formula which converges for any *x*_{0} > 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*^{r}-*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 *x*_{0} ∈ [*a*,*b*] together with *c* ∈ *R*. 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 [*x*_{0}-ε,*x*_{0}+ε] 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 (i.e. there is an ε > 0) as long as the implicit ODE

is continuous in all *y*s 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 *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

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.