[數學分析] 淺論收縮寫像定理-Contraction Principle

這次要介紹 收縮寫像定理 (Contraction Principle) 此為分析學中非常強大的工具。最大的應用是用來證明 微分方程 ODE 的解存在性與唯一性。我們在此將簡介此定理，介紹之前我們先介紹甚麼叫做 contraction ?


=============================
Definition: Contraction
令 $(X,d)$ 為 metric space。
我們說一個函數 $\Phi: X \to X$ 為 contraction 若下列條件成立：
存在常數 $c$ 滿足 $0 \le c <1$ 且 $$d(\Phi(x), \Phi(y)) \le c \cdot d(x,y)$$
=============================

Comments: 
1. 注意到我們要求常數 $c <1$ !! (不可等於 $1$)
2. 上述定義中的 $d(\cdot, \cdot)$ 為 $X$ 上 metric 。


現在我們看一些例子讓我們熟悉上述的定義

Example 1: 考慮 $\mathbb{R}$ 且裝備標準 metric 作為 metric space。試判斷 $f: \mathbb{R} \to \mathbb{R}$ 且
$$f(x) := x+1$$ 是否為 contraction?

Proof:
為了要判斷 $f$ 是否為 contraction，我們直接檢驗其 metric：
$$\begin{array}{l} d\left( {f\left( x \right),f\left( y \right)} \right): = \left| {f\left( x \right) - f\left( y \right)} \right|\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{}&{} \end{array} = \left| {x + 1 - \left( {y + 1} \right)} \right|\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{}&{} \end{array} = 1 \cdot \left| {x - y} \right| \end{array}$$ 注意到 上式中 $c:=1$ 不滿足 contraction 定義。故此函數 $f$ 不為 contraction。$\square$

Example 2: 考慮 $g: I \to I$ 其中 $I:=[0,a], \; a\in \mathbb{R}$且
$$g(x) := x^2$$ 試找出 $a$ 參數使得 $g$ 為 contraction。

Proof:
我們檢驗 metric ：
$$\begin{array}{l} d\left( {g\left( x \right),g\left( y \right)} \right): = \left| {g\left( x \right) - g\left( y \right)} \right|\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = \left| {{x^2} - {y^2}} \right|\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = \left| {x + y} \right|\left| {x - y} \right|\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} \le \left| a \right|\left| {x - y} \right| \end{array}$$ 可看出 $c:= |a|$ ，若我們希望 $g$ 為 contraction 則選 $|a| < 1$即可。 $\square$



如果一個函數為 contraction 有甚麼用呢?? 用處是可以幫我們不斷的 "收縮" 函數 最終收到某個 不動點 (fixed point)。 不過該如何辦到這件事? 我們要先引入 函數的 n-th iteration 。

=============================
Definition: n-th iteration of a function
我們稱 $f^n(a)$ 為函數 $f$ 在 $a$ 點的 n-th iteration 定義為
$${f^n}(a): = \underbrace {f \circ f \circ ...f(a)}_{n{\rm{ - }}times}$$ =============================

利用上述定義我們可以建構 sequence $\{a_n\}$ 且 $a_n := f^n(a)$

現在回頭看前面兩個例子，

--------------------------
Example 1 (continued)
回憶 Example 1 中的 $f(x) = x+1$；令 $x:=a=0$ 試問 若讓 $n \rightarrow \infty$，函數 sequence $\{a_n\} = \{f^n(0)\}$ 的極限為何?
--------------------------
Proof:
我們首先觀察 $f$ 的 n-th iteration：
$$\left\{ \begin{array}{l} f\left( x \right) = x + 1\\ {f^2}\left( x \right) = f\left( {f\left( x \right)} \right) = f\left( x \right) + 1 = x + 2\\ {f^3}\left( x \right) = {f^2}\left( {f\left( x \right)} \right) = f\left( x \right) + 2 = x + 3\\ \begin{array}{*{20}{c}} {}&{} \end{array} \vdots \\ {f^n}\left( x \right) = x + n \end{array} \right.$$ 故若 $a=0$ 我們得到
$$f^n(0) = n$$ 現在讓 $n \rightarrow \infty$，可推得 $f^n(0) \to \infty$

--------------------------
Example 2 (continued)

回憶 Example 2 中的 $g(x) = x^2$；令 $|a|<1$ 試問 若讓 $n \rightarrow \infty$，函數 sequence $\{a_n\} = \{g^n(0)\}$ 的極限為何?

--------------------------

Proof:

觀察 $g$ 的 n-th iteration
$$\left\{ \begin{array}{l} g\left( x \right) = {x^2}\\ {g^2}\left( x \right) = g\left( {g\left( x \right)} \right) = {x^4}\\ \begin{array}{*{20}{c}} {}&{} \end{array} \vdots \\ {g^n}\left( x \right) = {x^{2n}} \end{array} \right.$$ 故若 $|a|<1$ 讓 $n \to \infty$ 我們可得 $g^n(a) \to 0$。因此 $g^n(0) =0$。


==========================
Theorem: 收縮寫像定理 Contraction Principle
若 $(X,d)$ 為 complete metric space 且 $\Phi$ 為 contraction on $X$，則
$\Phi$ 有 唯一 不動點 $x^*$ (unique fixed point)；亦即 存在 $x^* \in X$ 使得 $\Phi(x^*) = x^*$
==========================
Proof: omitted.

Comments:
1. 收縮寫像定理要求  1. completeness 2. 要有 contraction $\Phi :X \to X$。
2. 注意到 若條件為 $X$ compact 則 contraction principle 亦為成立 (因為 compact = totally bounded + complete)


現在看幾個 contraction principle 的應用：

==========================
Corollary: 令 $\Phi : X \to X$ 為 contraction 且 $X$ 為 complete。若 $\Phi^N$ 為 N-th iterate of $\Phi$ 且 $\Phi^N$ 仍為 contraction，則 $\Phi$ 具有 唯一的固定點。亦即 存在 $x^*$ 使得 $\Phi(x^*) = x^*$ 
==========================

Proof:
我們要證明 存在 $x^*$ 使得 $\Phi(x^*) = x^*$ 

由於 $\Phi^N$ 為 contraction，由 contraction principle 可知 $\Phi^N$ 有 唯一 不動點，我們記做 $\bar x$，亦即
$${\Phi ^N}\left( {{\bar x}} \right) = {\bar x} \ \ \ \ (*)$$ 如果我們在跌代一次  可得 $${\Phi ^N}\left( {\Phi \left( {{\bar x}} \right)} \right) = \Phi \left( {{ \bar x}} \right)  \ \ \ \ (\star)$$ 觀察 $(*)$ 與 $(\star)$ 可知若我們令 $x^* := \Phi(\bar x)$ 即為其唯一的不動點。$\square$



Example 3: 考慮 $T \in C([0,1])$ 定義如下：
$$T[f](x) := \int_0^x f(t) dt$$ 試證 $T$ 有 唯一固定點。

Proof:

注意到 $C([0,1])$ 為 complete space，故我們只須證明 $T[f](x) := \int_0^x f(t) dt$ 為 contraction。回憶 $C([0,1])$ 上的 metric 為 supnorm 故現在觀察
$$\begin{array}{l} \left\| {T[f] - T[g]} \right\| = \mathop {\sup }\limits_x \left| {T[f](x) - T[g](x)} \right|\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = \left| {\int_0^x f (t)dt - \int_0^x g (t)dt} \right|\\ \begin{array}{*{20}{c}} {}&{}&{}&{}&{}&{} \end{array} = \left| {\int_0^x {f(t) - g(t)} dt} \right| \le \int_0^x {\left| {f(t) - g(t)} \right|} dt \le \left\| {f - g} \right\|x \end{array}$$ 故選 $c:=x$ 滿足 $0\le x<1$ 即可說 $T$ 為有唯一固定點。利用 contraction principle 可知其具備唯一固定點。 

Example 4
令 $K$ 為 compact metric space 且其中至少包含兩相異點，現在令 $\Phi : K \to K$ 為 contraction。試證 $\Phi$ 並非 onto。

Proof:
令 $K$ 為 compact metric space 且其中至少包含兩相異點，要證明  $\Phi$ 並非 onto；亦即 存在 $x^* \in K$ 使得 $\forall x \in K$，$\Phi(x) \neq \Phi(x^*)$。
首先 注意到由於 $K$ 為 compact  且 $\Phi : K \to K$ 為 contraction，由 contraction principle 可知存在唯一固定點 $x^*$ 使得 $\Phi(x^*) = x^*$，由於此固定點為唯一 且 $K$ 至少有兩相異點，此暗示了對任意  $x \in K$，$\Phi(x) \neq \Phi(x^*)$。