# Function Space - Banach Contraction Theorem

:::warning
**Def (Fixed Point)**
假定 $f : M \to M$，其中 $M$ 是個 *metric space*。假定 $p\in M$ 滿足：
$$
f(p) = p
$$
則稱 $p$ 是一個 *fixed point*
:::

## Contraction Map

:::warning
**Def (Contraction)**
假定 $f : M\to M$ ，其中 $M$ 是一個 *metric space*。假定存在 $k < 1$，使得：
$$
d(f(x_1), f(x_2)) \leq kd(x_1, x_2)
$$
則稱 $f$ 為一個 *contraction map*。
:::

直覺上來說，就是把一個不斷重複帶進去 $f$，那麼兩次迭代的艱鉅會越來越小。

:::danger
**Observation (Contraction Map 連續)**
假定 $f : M\to M$ ，其中 $M$ 是一個 *metric space*，則：
$$
\begin{align}
& f\text{ is contraction map } \newline
& \Rightarrow f \text{ is continuous}
\end{align}
$$
:::

## Banach Contration Theorem

:::danger
**Thm (Banach Contraction Theorem)**
假定 $f : M\to M$ 是一個 *contraction map*，則：
$$
M \text{ complete} \Rightarrow \exists ! p.f(p) = p
$$
即：在 *complete metric space* 上的 *contraction map*，存在唯一的 *fined point*。
:::

其實就是隨便找一個起始點，不斷的帶入 $f$，就會自己跑回那個 *fixed-point* 了。因為：

$$
\{x_i\} = \begin{cases}
x_0 & \text{if }i = 0 \newline
f(x_{i-1}) & \text{if }i > 0
\end{cases}
$$

換句話說，就是令 $x_i = f^i(x)$。由於 $f$ 是 *contraction map*，因此對於任意 $0 < m < n 0$，有：

$$
\begin{align}
d(x_m, x_n) &= d(f^m(x_0), f^n(x_0)) \newline
&\leq d(f^m(x_0), f^{m+1}(x_0)) + d(f^{m+1}(x_0), f^{m+2}(x_0)) \dots d(f^{n-1}(x_0), f^{n}(x_0))\newline
&= \sum_{i = m}^{n}k^id(x_0, f(x_0))
< \frac {k^n}{1-k}d(x_0, f(x_0))
\end{align}
$$

因為 $k < 1$，所以當 $n$ 夠大時，$d(x_m, x_n)$ 可以任意小。所以 $\{x_i\}$ *Cauchy*。又因為 $M$ *complete*，所以 $\{x_i\}$ 收斂。

更進一步宣稱：假定 $x_i \to p$，則 $f(p) = p$。這和 *contraction map* 連續有關。因為：

$$\lim_{i\to\infty}x^{i+1} = \lim_{i \to \infty} x^i = p$$

接著因為 *contraction map* 連續，所以：

$$
\lim_{i\to\infty}x^{i+1} = \lim_{i \to \infty}f(x_i) = f\left(\lim_{i\to \infty}x_i\right) = f(p)
$$

因此：

$$
f(p) = \lim_{i\to\infty}x^{i+1} = \lim_{i \to \infty} x^i = p
$$

更進一步，這個 $p$ 是唯一的。假定存在 $p_1, p_2$，使得 $f(p_1) = p_1$ 且 $f(p_2) = p_2$。用 *contraction map* 有：

$$
d(f(p_1),f(p_2)) \leq kd(p_1, p_2)
$$

用 $f(p_1) = p_1$ 且 $f(p_2) = p_2$ 有：

$$
d(f(p_1), f(p_2)) = d(p_1, p_2)
$$

所以綜合以上：

$$
d(f(p_1), f(p_2)) = d(p_1, p_2) \leq kd(p_1, p_2) \Rightarrow d(p_1, p_2) = 0
$$