Mathematics Prelims

July 21, 2008

The Banach Fixed Point Theorem

Filed under: Analysis,Functional Analysis — cjohnson @ 10:06 pm

A mapping T : X \to X from a metric space X to itself is called a contraction if there exists an \alpha \in (0, 1) such that for every x, y \in X we have d(Tx, Ty) \leq \alpha d(x, y).  The Banach fixed point theorem (aka the contraction theorem) says that every contraction on a non-empty complete metric space has exactly one fixed point.

Proof:  Suppose X is a complete metric space and that T : X \to X is a contraction.  Let x_0 \in X be any point.  Define x_1 = T x_0, x_2 = T x_1 = T^2 x_0, x_3 = T x_2 = T^3 x_0 and so forth.  If we write d(x_{n+1}, x_n) in terms of Tx_n andTx_{n-1}, we see that d(x_{n+1}, x_n) \leq \alpha^n d(x_1, x_0).  Now consider d(x_n, x_m) where we assume, without loss of generality, that n > m.  By the triangle inequality we have

\displaystyle d(x_n, x_m) \leq (\alpha^{n-1} + \alpha^{n-2} + ... + \alpha^m) d(x_1, x_0)

\displaystyle \qquad = \frac{\alpha^m (1 - \alpha^{n - m})}{1 - \alpha} d(x_1, x_0)

\displaystyle \qquad \leq \frac{\alpha^m}{1 - \alpha} d(x_0, x_1)

We can obviously make this value as small as we’d like by picking a large enough m, so the sequence (x_n)_{n \in \mathbb{N}} is Cauchy and must converge.  Call the limit of this sequence x.  Now consider the distance between x and Tx.

\displaystyle d(x, Tx) \leq d(x, x_m) + d(x_m, Tx) \leq d(x, x_m) + \alpha d(x_{m-1}, x)

By picking a large enough m, we can make this as small as we’d like as well, so we have d(x, Tx) = 0 so T has a fixed point.  For the uniqueness of x, suppose y is also a fixed point.

\displaystyle d(x, y) = d(Tx, Ty) \leq \alpha d(x, y)

The only way this holds is if d(x, y) = 0, so x = y.  Note that the x we constructed didn’t depend on on our initial value of x_0, so every sequence we construct by picking a point in X and iterating T will result in the same limit.

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

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

Create a free website or blog at WordPress.com.

%d bloggers like this: