Function Space - Banach Contraction Theorem

Def (Fixed Point)
假定

$f:M\to M$，其中

$M$ 是個 metric space。假定

$p\in M$ 滿足：

$$f(p)=p$$
則稱

$p$ 是一個 fixed point

Contraction Map

Def (Contraction)
假定

$f:M\to M$ ，其中

$M$ 是一個 metric space。假定存在

$k<1$，使得：

$$d(f(x_1),f(x_2))\le kd(x_1,x_2)$$
則稱

$f$ 為一個 contraction map。

直覺上來說，就是把一個不斷重複帶進去

$f$，那麼兩次迭代的艱鉅會越來越小。

Observation (Contraction Map 連續)
假定

$f:M\to M$ ，其中

$M$ 是一個 metric space，則：

$$\begin{array}{rl}& f\text{ is contraction map }\\ & \Rightarrow f\text{ is continuous}\end{array}$$

Banach Contration Theorem

Thm (Banach Contraction Theorem)
假定

$f:M\to M$ 是一個 contraction map，則：

$$M\text{ complete}\Rightarrow \mathrm{\exists }!p.f(p)=p$$
即：在 complete metric space 上的 contraction map，存在唯一的 fined point。

其實就是隨便找一個起始點，不斷的帶入

$f$，就會自己跑回那個 fixed-point 了。因為：

$$\{x_i\}=\{\begin{array}{ll}{x}_0& \text{if }i=0\\ f(x_{i-1})& \text{if }i>0\end{array}$$

換句話說，就是令

$x_i=f^i(x)$。由於

$f$ 是 contraction map，因此對於任意

$0<m<n0$，有：

$$\begin{array}{rl}d(x_m,x_n)& =d(f^m(x_0),f^n(x_0))\\ & \le 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))\\ & =\sum _{i=m}^n{k}^{i}d(x_0,f(x_0))<\frac{k^n}{1-k}d(x_0,f(x_0))\end{array}$$

因為

$k<1$，所以當

$n$ 夠大時，

$d(x_m,x_n)$ 可以任意小。所以

$\{x_i\}$ Cauchy。又因為

$M$ complete，所以

$\{x_i\}$ 收斂。

更進一步宣稱：假定

$x_i\to p$，則

$f(p)=p$。這和 contraction map 連續有關。因為：

$$\underset{i\to \mathrm{\infty }}{lim}{x}^{i+1}=\underset{i\to \mathrm{\infty }}{lim}{x}^i=p$$

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

$$\underset{i\to \mathrm{\infty }}{lim}{x}^{i+1}=\underset{i\to \mathrm{\infty }}{lim}f(x_i)=f\left(\underset{i\to \mathrm{\infty }}{lim}{x}_i\right)=f(p)$$

因此：

$$f(p)=\underset{i\to \mathrm{\infty }}{lim}{x}^{i+1}=\underset{i\to \mathrm{\infty }}{lim}{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))\le 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)\le kd(p_1,p_2)\Rightarrow d(p_1,p_2)=0$$