Notes - Metric Spaces MT23, Contractions

Created: July 31, 2023

Flashcards

What does it mean for a function $f: X \to X$ to be a contraction?
\[f \text{ contraction} \iff \exists 0 \le K < 1 \text{ s.t. } d(f(x), f(y)) \le Kd(x, y)\]

When is a function $f : X \to X$ a contraction in terms of $f$ being Lipschitz?

When $f$ is Lipschitz with Lipschitz constant $K \in [0, 1)$.

Can you state the contraction mapping theorem?

Let $X$ be a non-empty complete metric space and suppose that $f : X \to X$ is a contraction. Then $f$ has a unique fixed point, i.e. $\exists x \in X \text{ s.t. } f(x) = x$.

What are the conditions on $X$ in the contraction mapping theorem?
  • $X$ is non-empty
  • $X$ is complete
  • (and $X$ is a metric space)

Can you give an example of a function where it’s almost a contraction but where it has no fixed points, as would be implied by the contraction mapping theorem?
\[f : [1, \infty) \to [1, \infty)\]

where $f(x) = x + \frac 1 x$.

What sequence do you consider in the proof of the contraction mapping theorem for some $f : X \to X$?
\[x_0 \in X, x_{i+1} = f(x_i)\]

Suppose we are proving the contraction mapping theorem. We have

  • $f : X \to X$, Lipschitz with constant $K \in [0, 1)$.
  • A sequence $x _ 0 \in X, x _ {i+1} = f(x _ i)$

Quickly prove that:

  • This is a Cauchy sequence
  • The limit satisfies $f(x) = x$.

Note that for any $n > 0$

\[\begin{aligned} d(x_n, x_{n-1}) &= d(f(x_{n-1}), f(x_{n-2})) \\\\ &\le Kd(x_{n-1}, x_{n-2}) \\\\ &\le K^2 d(x_{n-2}, x_{n-1}) \\\\ &\le \cdots \\\\ &\le K^{n-1} d(x_1, x_0) \end{aligned}\]

We want to show that for $m > n$, we can make $d(x _ n, x _ m)$ arbitrarily small. Suppose $n, m \ge N$. Then:

\[\begin{aligned} d(x_n, x_m) &\le d(x_n, x_{n-1}) + \cdots + d(x_{m+1}, x_m) \\\\ &\le (K^{n-1} + K^{n-2} + \cdots + K^m)d(x_1, x_0) \\\\ &\le K^m(K^{n-m-1} + K^{n - m -2} + \cdots + K + 1)d(x_1, x_0) \\\\ &\le K^m \sum^\infty_{i = 0} K^i \\\\ &= K^m C\\\\ &\le K^N C \end{aligned}\]

where $C$ is the sum of the infinite series (which exists, since $K \in [0, 1)$. This can be made aribrarily small, so the sequence is a Cauchy sequence.

To see the limit satisfies $f(x) = x$, since $f$ is continuous

\[f(x) = \lim_{n \to \infty} f(x_n) = \lim_{n \to \infty} x_{n+1} = x\]

Quickly prove the following variant of the contraction mapping theorem: Suppose

  • $(X, d)$ is a compact, non-empty metric space
  • $g : X \to X$ is a mapping such that $\forall x, y \in X$ where $x \ne y$, we have $d(g(x), g(y)) < d(x, y)$.

Then:

  • $\exists x _ 0 \in X$ such that $g(x _ 0) = x _ 0$
  • $x _ 0$ is unique

(the changes are: we are considering compact metric spaces rather than complete ones, and we have a strict inequality rather than $\exists K \in [0, 1)$ such that $d(g(x), g(y)) \le Kd(x, y)$).

Existence: consider $F(x) = d(g(x), x)$ for $x \in X$. Then

\[\begin{aligned} |F(x) - F(y)| &= |d(g(x), x) - d(g(y), y)| \\\\ &= |d(g(x), x) - d(x, g(y)) + d(x, g(y)) - d(g(y), y)| \\\\ &\le |d(g(x), x) + d(x, g(y))| + |d(x, g(y) + d(g(y), y| \\\\ &\le |d(g(x), g(y))| + |d(x, y)| &&(\text{triangle ineq.})\\\\ &< 2d(x, y) && (\text{assumption on }g) \end{aligned}\]

for all $x, y$ so it is in fact Lipschitz, and so continuous. Since $X$ is compact, $F$ achieves its minimum on $X$, so $\exists x _ 0 \in X$ such that

\[d(g(x_0), x_0) = \inf_{x \in X} d(g(x), x)\]

Suppose $g(x _ 0) \ne x _ 0$. Then $d(g(g(x _ 0)), g(x _ 0)) < d(g(x _ 0), x _ 0) = F(x _ 0)$ by assumption, so then $F(g(x _ 0)) < F(x _ 0)$ which would contradict the fact that $x _ 0$ is the infimum of $F$. Thus $g(x _ 0) = x _ 0$.

Uniqueness: suppose $x, y$ are two seperate fixed points. Then

\[d(x, y) = d(g(x), g(y)) < d(x, y)\]

a contradiction.

What condition relates the derivative of a function and whether it is Lipschitz?
\[\text{Lipschitz} + \text{differentiable} \iff \text{bounded derivative}\]

What’s a quick way to check whether a differentiable function $f : X \to X$ is a contraction?

The derivative is strictly less than $1$ in magnitude.

Quickly prove that if $X$ is a convex domain in $\mathbb C$ and $f$ is a holomorphic function on $X$, if

\[|f'(z)| \le \lambda\]

for some $\lambda \in (0, 1)$ and $f(X) \subseteq X$, then $f$ is a contraction on $X$.

We want to show that

\[|f(z) - f(w)| \le \lambda|z - w|\]

Define the path $\gamma : X \to X$ by $\gamma(t) = tz + (1 - t)w$. Then note that the length of $f \circ \gamma$ must be at least $ \vert f(z) - f(w) \vert $. Hence

\[\begin{aligned} |f(z) - f(w)| &\le \ell(f \circ \gamma) \\\\ &= \int^1_0 |(f \circ \gamma)' (t)| \text dw \\\\ &= \int^1_0 |f'(\gamma(t))\gamma'(t)| \text dw \\\\ &\le \lambda \int^1_0 |\gamma'(t)| \text dw \\\\ &= \lambda | z - w| \end{aligned}\]

Proofs

Prove that every contraction is continuous.

Todo.



Related posts