PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (200)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
[parent] proof of Banach fixed point theorem (Proof)

Let $ (X,d)$ be a non-empty, complete metric space, and let $ T$ be a contraction mapping on $ (X,d)$ with constant $ q$. Pick an arbitrary $ x_0 \in X$, and define the sequence $ (x_n)_{n=0}^{\infty}$ by $ x_n:=T^nx_0$. Let $ a:=d(Tx_0,x_0)$. We first show by induction that for any $ n\ge 0$,

$\displaystyle d(T^nx_0,x_0)\le\frac{1-q^n}{1-q} a. $
For $ n=0$, this is obvious. For any $ n\ge 1$, suppose that $ d(T^{n-1}x_0,x_0)\le\frac{1-q^{n-1}}{1-q}a$. Then
$\displaystyle d(T^nx_0,x_0)$ $\displaystyle \le$ $\displaystyle d(T^nx_0,T^{n-1}x_0)+d(x_0,T^{n-1}x_0)$  
  $\displaystyle \le$ $\displaystyle q^{n-1}d(Tx_0,x_0)+\frac{1-q^{n-1}}{1-q}a$  
  $\displaystyle =$ $\displaystyle \frac{q^{n-1}-q^n}{1-q}a+\frac{1-q^{n-1}}{1-q}a$  
  $\displaystyle =$ $\displaystyle \frac{1-q^n}{1-q}a$  

by the triangle inequality and repeated application of the property $ d(Tx,Ty)\le qd(x,y)$ of $ T$. By induction, the inequality holds for all $ n \ge 0$.

Given any $ \epsilon>0$, it is possible to choose a natural number $ N$ such that $ \frac{q^n}{1-q}a<\epsilon$ for all $ n\ge N$, because $ \frac{q^n}{1-q}a\to 0$ as $ n\to\infty$. Now, for any $ m,n\ge N$ (we may assume that $ m\ge n$),
$\displaystyle d(x_m,x_n)$ $\displaystyle =$ $\displaystyle d(T^mx_0,T^nx_0)$  
  $\displaystyle \le$ $\displaystyle q^nd(T^{m-n}x_0,x_0)$  
  $\displaystyle \le$ $\displaystyle q^n\frac{1-q^{m-n}}{1-q}a$  
  $\displaystyle <$ $\displaystyle \frac{q^n}{1-q}a<\epsilon,$  

so the sequence $ (x_n)$ is a Cauchy sequence. Because $ (X,d)$ is complete, this implies that the sequence has a limit in $ (X,d)$; define $ x^*$ to be this limit. We now prove that $ x^*$ is a fixed point of $ T$. Suppose it is not, then $ \delta:=d(Tx^*,x^*)>0$. However, because $ (x_n)$ converges to $ x^*$, there is a natural number $ N$ such that $ d(x_n,x^*)<\delta/2$ for all $ n\ge N$. Then
$\displaystyle d(Tx^*,x^*)$ $\displaystyle \le$ $\displaystyle d(Tx^*,x_{N+1})+d(x^*,x_{N+1})$  
  $\displaystyle \le$ $\displaystyle qd(x^*,x_N)+d(x^*,x_{N+1})$  
  $\displaystyle <$ $\displaystyle \delta/2+\delta/2=\delta,$  

contradiction. So $ x^*$ is a fixed point of $ T$. It is also unique. Suppose there is another fixed point $ x'$ of $ T$; because $ x'\neq x^*$, $ d(x',x^*)>0$. But then
$\displaystyle d(x',x^*)=d(Tx',Tx^*)\le qd(x',x^*)<d(x',x^*), $
contradiction. Therefore, $ x^*$ is the unique fixed point of $ T$.



"proof of Banach fixed point theorem" is owned by asteroid. [ full author list (2) | owner history (2) ]
(view preamble)

View style:


This object's parent.
Log in to rate this entry.
(view current ratings)

Cross-references: contradiction, converges, fixed point, limit, implies, Cauchy sequence, natural number, inequality, property, triangle inequality, obvious, induction, sequence, contraction mapping, metric space, complete

This is version 2 of proof of Banach fixed point theorem, born on 2002-11-10, modified 2007-11-10.
Object id is 3581, canonical name is ProofOfBanachFixedPointTheorem.
Accessed 7421 times total.

Classification:
AMS MSC: 54A20 (General topology :: Generalities :: Convergence in general topology )
 47H10 (Operator theory :: Nonlinear operators and their properties :: Fixed-point theorems)
 54H25 (General topology :: Connections with other structures, applications :: Fixed-point and coincidence theorems)
Pending Errata and Addenda
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy
You like stars too? I give up! by NeuRet on 2002-11-11 03:00:35
Ok, so it seems you like to denote the fixed point by x^* as well. I give up. If the world wants stars, I'll give them stars.

(What I mean is that I will modify the original statement of the theorem to put in a star.)

By the way, nice proof! I like your style.

- J"
[ reply | up ]
Interact
post | correct | update request | add example | add (any)