Abstract Nonsense

Crushing one theorem at a time

Banach Fixed Point Theorem


Point of Post: In this post we discuss and prove the famous result known as the Banach Fixed Point Theorem or the Contraction Mapping Principle.

\text{ }

Motivation

There is an old (anonymous) saying among mathematicians and math enthusiasts: “All of topology comes down to a fixed point theorem”. Now, while this is clearly a gross exaggeration it is definitely a moral truth. In fact, when one thinks of some of the most famous [“basic”] results in topology one is often thinking of theorems which, if not fixed point theorems themselves, have a definite fixed point feel: the Lefschetz fixed point theorem, the Brouwer fixed point theorem, the Borsuk-Ulam theorem, etc. This oversimplified truth can, in some small way, also be said of analysis. Often certain, seemingly intractable, problems in analysis are killed right away if one applies a certain fixed point theorem. Probably the most famous of the ‘analytic feeling’ fixed point theorems (analytic feeling is pretty vague, but most often has to do with metric spaces e.g. this theorem) is the Banach fixed point theorem which first appeared in the Ph.D. thesis of Stefan Banach (the same Banach as in Banach space of course). Roughly, it says that if you have a contraction mapping from a complete metric space to itself must have a unique fixed point. This is so intuitive (once you’ve been told it of course) that the intuition is the proof: since the mapping is a contraction the points x_0,f(x_0),f(f(x_0)),\cdots, (for any x_0) must be getting close together (i.e. the sequence is Cauchy) and thus we know from the completeness of our space the sequence must converge to some \lim f^{(n)}(x_0)=y. But, since f is continuous (evidently since it’s a contraction>Lipschitz>uniform continuity>continuity) we know that acting on y by f should be the same as considering \lim f^{(n+1)}(x) which, if there is any justice in the world, is just y. The uniqueness is clear since if two points where fixed by f then acting on them by f couldn’t take them any closer.

\text{ }

Banach Fixed Point Theorem

So, we first recall that a contraction mapping between two metric spaces (M,d) and (N,d') is a mapping f:M\to N such that there exists some c\in(0,1) such that d'(f(x),f(y))\leqslant c\,d(x,y) for all x,y\in M. With that in mind we first make one trivial observation and prove one lemma:

\text{ }

Observation: Every contraction mapping f:(M,d)\to (N,d') is uniformly continuous.

\text{ }

and

\text{ }

Lemma: Let f:(M,d)\to (N,d') be a contraction mapping and x_0\in M. Then, the sequence \left\{f^{(n)}(x_0)\right\}_{n\in\mathbb{N}} (where, as usual, f^{(n)} denotes the n-fold composition of f) is a Cauchy sequence in N.

Proof: We note by induction that if n\geqslant m\geqslant 1 then  d(f^{(m)}(x_0),f^{(n)}(x_0))\leqslant c^n d(f^{(m)}(x_0),x_0). But, similarly by induction we see that

\text{ }

\displaystyle \begin{aligned} d\left(f^{(m)}(x_0),x_0\right) &\leqslant \sum_{j=1}^{m}d\left(f^{(j)}(x_0),f^{(j-1)}(x_0)\right)\\ &\leqslant d(f(x_0),x_0)\sum_{j=1}^{m}c^{j-1}\\ &=d(f(x_0),x_0)\frac{1-c^m}{1-c}\end{aligned}

\text{ }

Thus, for m\geqslant n\geqslant 1 we have that

\text{ }

\displaystyle d\left(f^{(m)}(x_0),f^{(n)}(x_0)\right)\leqslant c^n d(f^{(m)}(x_0),x_0)\leqslant c^n\frac{1-c^m}{1-c}d(f(x_0),x_0)\leqslant \frac{c^n}{1-c}d(f(x_0),x_0)

\text{ }

Thus, we see that given a \varepsilon>0 if we choose N large enough so that \displaystyle \frac{c^N}{1-c}d(f(x_0),x_0)<\varepsilon the above shows that m>n\geqslant N implies that d(f^{(m)}(x_0),f^{(n)}(x_0))<\varepsilon. Since \varepsilon was arbitrary the conclusion follows. \blacksquare

\text{ }

\text{ }

With this lemma we see now that the Banach Fixed Point theorem now becomes easy:

\text{ }

Theorem (Banach Fixed Point Theorem/Contraction Mapping Principle): Let (M,d) be a complete metric space and f:M\to M a contraction. Then, f has a unique fixed point \xi given by \xi=\lim f^{(n)}(x_0) for any x_0\in M.

Proof: We have by the previous lemma that the sequence \left\{f^{(n)}(x_0)\right\}_{n\in\mathbb{N}} is Cauchy and thus, by the completeness of M, has some limit \lim f^{(n)}(x_0)=\xi. But, since f is continuous we have that

\text{ }

f(\xi)=f\left(\lim f^{(n)}(x_0)\right)=\lim f\left(f^{(n)}(x_0)\right)=\lim f^{(n+1)}(x_0)=\xi

\text{ }

where we used the fact that for a convergent sequence every subsequence converges to the same value. To see that this limit point is unique we merely note that if \eta were another such fixed point (distinct from \xi) then d(\xi,\eta)=d(f(\xi),f(\eta))\leqslant c\, d(\xi,\eta)<d(\xi,\eta) which is evidently ridiculous. The conclusion follows. \blacksquare

\text{ }

\text{ }

References:

1. Rudin, Walter. Principles of Mathematical Analysis. New York [u.a.: McGraw-Hill, 2008. Print.

Advertisements

June 13, 2011 - Posted by | Analysis, General Topology | , , , , , ,

1 Comment »

  1. […] is a contraction mapping and so by the Banach fixed point theorem there is a unique solution to in . But, note that […]

    Pingback by The Inverse Function Theorem (Proof) « Abstract Nonsense | September 8, 2011 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: