2.2 巴拿赫不動點定理#

概念說明#

巴拿赫不動點定理（壓縮映像原理）是不動點理論的支柱，敘述如下：

設 \((X, d)\) 為完備度量空間， \(g: X \to X\) 為壓縮映像，即存在常數 \(0 \le L < 1\) 使得對所有 \(x, y \in X\) ，

\[ d(g(x), g(y)) \le L \cdot d(x, y) \]

則 \(g\) 恰有一個不動點 \(x^*\) ，且從任何 \(x_0\) 出發，迭代序列 \(x_{k+1} = g(x_k)\) 都收斂到 \(x^*\) 。

定理的威力在於三合一的結論：存在、唯一、全域收斂——不挑起點。證明思想也極優雅，值得一觀：

柯西性： \(d(x_{k+1}, x_k) \le L\, d(x_k, x_{k-1})\) ，遞推得 \(d(x_{k+m}, x_k) \le \dfrac{L^k}{1-L} d(x_1, x_0)\) 。 \(L^k \to 0\) ，序列是柯西列； \(X\) 完備，故收斂到某極限 \(x^*\) 。
極限即不動點： \(g\) 連續（壓縮性保證），取極限 \(x^* = \lim x_{k+1} = \lim g(x_k) = g(x^*)\) 。
唯一性：若有兩個不動點 \(x^*, y^*\) ，則 \(d(x^*, y^*) = d(g(x^*), g(y^*)) \le L\, d(x^*, y^*)\) ，因 \(L < 1\) 只能 \(d(x^*, y^*) = 0\) 。

在實數區間上， \(L\) 常取 \(|g'|\) 的上界：若 \(|g'(x)| \le L < 1\) 對區間內所有 \(x\) 成立，則由均值定理 \(|g(x) - g(y)| = |g'(\xi)|\,|x - y| \le L |x-y|\) ，即為壓縮映像。例如 \(g(x) = \cos x\) ： \(|g'(x)| = |\sin x| \le \sin 1 < 1\) ，故 \(x = \cos x\) 在 \(\mathbb{R}\) 上有唯一不動點，任何起點都收斂——這解釋了 2.1 節實驗的成功。

注意 \(L\) 必須嚴格小於 1。 \(g(x) = x\) （恆等）與 \(g(x) = 1 - x\) （震盪）都滿足 \(|g'| = 1\) ，前者不動點無窮多、後者迭代不收斂，正好是兩種失敗模式。

生活類比#

影印縮小 90% 再影印再縮小：不論原稿多大，反覆套用後必然縮到一個點附近——縮小率 \(L = 0.9\) 就是壓縮常數。市場價格調整亦然：超額供給時降價、超額需求時漲價，只要每次調整幅度小於差距（ \(L<1\) ），價格終將穩定於均衡。

演算法步驟#

用壓縮映像原理設計收斂的迭代：

把問題改寫為 \(x = g(x)\) ， \(g\) 映某完備集 \(X\) （如閉區間）到自身。
驗證壓縮性：找出 \(L = \sup_{x \in X} |g'(x)| < 1\) （或直接用 Lipschitz 估計）。
從任意 \(x_0 \in X\) 開始迭代 \(x_{k+1} = g(x_k)\) 。
用 2.3 節的後驗誤差界 \(\dfrac{L}{1-L}|x_{k+1} - x_k|\) 決定停機。

Python 範例#

以 \(g(x) = 1 + x/2\) 求不動點 \(x^* = 2\) ，並驗證理論誤差界：

def banach_demo(x0=100.0, n=20):
    L = 0.5                      # 壓縮常數 |g'|
    xs = [x0]
    for _ in range(n):
        xs.append(1 + xs[-1] / 2)
    true = 2.0
    print(f"{'k':>3} {'x_k':>18} {'實際誤差':>12} {'理論上界':>12}")
    for k, x in enumerate(xs):
        bound = (L**k / (1 - L)) * abs(xs[1] - xs[0]) if k else abs(x - true)
        print(f"{k:>3} {x:>18.10f} {abs(x - true):>12.3e} {bound:>12.3e}")

banach_demo()

輸出顯示實際誤差始終不超過理論上界，且以 \(L^k\) 的速度遞減。

複雜度與收斂性分析#

誤差界有兩個實用形式：

先驗界： \(|x_k - x^*| \le \dfrac{L^k}{1-L}|x_1 - x_0|\) ，可在動手前預估需要幾次迭代。
後驗界： \(|x_k - x^*| \le \dfrac{L}{1-L}|x_k - x_{k-1}|\) ，用相鄰兩項差距控制停機。

達到精度 \(\varepsilon\) 所需迭代數 \(k \ge \log\!\big(\tfrac{\varepsilon(1-L)}{|x_1-x_0|}\big) / \log L\) 。每次迭代成本為 \(O(\text{cost}(g))\) ，總成本為兩者乘積。 \(L\) 越接近 1 收斂越慢； \(L \ge 1\) 時定理失效，需改寫方程或改用牛頓法。

練習#

證明 \(g(x) = \frac{1}{2}(x + 3/x)\) 在 \([\sqrt{3}, \infty)\) 上是壓縮映像，求 \(L\) ，並用先驗界估計達 \(10^{-10}\) 精度所需迭代數，再實測比較。
\(g(x) = 1/x\) 在 \([0.5, 2]\) 映到自身嗎？是壓縮映像嗎？不動點唯一嗎？迭代 \(x_{k+1} = 1/x_k\) 會發生什麼？
停車入庫：每次修正方向使誤差縮為一半（ \(L = 0.5\) ）。若初始偏差 2 公尺、要求 1 公分內，至少修正幾次？