> [!definition] > > Let $(X, d)$ be a [[Metric Space|metric space]] and $f: X \to X$ be a [[Function|function]]. $f$ is a **contractor** if $\exists 0 \le k < 1$ such that > $ > d(f(x), f(y)) \le kd(x, y) \quad \forall x, y \in X > $ > The minimum possible value of $k$ is called the **Lipschitz constant** of $f$. > [!theorem] > > Let $(X, d)$ be a metric space and $f: X \to X$ be a contractor, then $f$ is uniformly continuous. > > *Proof*. Let $L$ be the Lipschitz constant of $f$, $\varepsilon > 0$, and $\delta = \varepsilon/2L$, then for any $x, y \in X$ with $d(x, y) < \delta$, $d(f(x), f(y)) \le \varepsilon/2 < \varepsilon$. > [!theoremb] Banach Fixed-Point Theorem > > Let $(X, d)$ be a [[Complete Metric Space|complete]] metric space and $f: X \to X$ be a contractor, then there exists a unique $x \in X$ such that > 1. $x$ is a fixed point. > 2. $\limv{n}f^n(y) = x$ for all $y \in X$. > > ### Existence > > For any $y \in Y$, let $y_n = f^n(x)$, then $\limv{n}y_n$ exists. > > *Proof.* Let $L$ be the Lipschitz constant of $f$, then for any $n \in \nat$, > $ > d(y_n, y_{n + 1}) = L^nd(y, y_1) > $ > which means that for any $m, n \in \nat$ with $m \le n$, > $ > \begin{align*} > d(y_m, y_n) &\le \sum_{k = m}^{n - 1}d(y_k, y_{k + 1}) \\ > &\le \sum_{k = m}^{n - 1}L^kd(y, y_1) \\ > &\le d(y, y_1) \cdot \sum_{k \ge m}L^k \\ > \end{align*} > $ > which goes to $0$ with $m \to \infty$. Therefore $\seq{y_n}$ is a [[Cauchy Sequence|Cauchy sequence]] and has a limit. > > ### Uniqueness > > For any $x, y \in X$, $\limv{n}f^n(x) = \limv{n}f^n(y)$. > > *Proof*. Since $f$ is a contractor $\limv{n}d(f^n(x), f^n(y)) = 0$ and the limit point is unique. > > ### Fixed > > Let $x \in X$, then $y = \limv{n}f^n(x)$ is a fixed point of $f$. > > *Proof*. Since $f$ is uniformly continuous, > $ > y = \limv{n}f^n(y) = f\paren{\limv{n}f^{n - 1}(y)} = f(y) > $