2.1 不動點的觀念#

概念說明#

給定函數 \(g: D \to D\) ，若 \(x^* = g(x^*)\) ，則稱 \(x^*\) 為 \(g\) 的不動點。幾何直觀：不動點就是曲線 \(y = g(x)\) 與直線 \(y = x\) 的交點。迭代過程 \(x_{k+1} = g(x_k)\) 的圖形呈現「階梯狀」或「蛛網狀」：從 \((x_0, x_0)\) 垂直走到曲線得 \(g(x_0)\) ，再水平走回對角線得 \(x_1\) ，如此反覆；交點處階梯停止移動。

三個立即的問題：

存在性： \(g\) 一定有不動點嗎？不一定。 \(g(x) = x + 1\) 沒有不動點。連續函數把區間 \([a,b]\) 映到自身時，由中間值定理必有不動點（Brouwer 定理的一維情形）。
唯一性： \(g(x) = x^2\) 在 \([0, 1]\) 有兩個不動點（0 與 1）。若 \(g\) 是壓縮映像則唯一。
收斂性：就算不動點存在，迭代 \(x_{k+1} = g(x_k)\) 也未必靠近它。在 \(x^*\) 附近， \(x_{k+1} - x^* \approx g'(x^*)(x_k - x^*)\) ，故若 \(|g'(x^*)| > 1\) ，迭代會被推離不動點——導數絕對值小於 1 是局部收斂的關鍵。

求解方程 \(f(x) = 0\) 可化成無窮多種不動點形式，例如 \(f(x) = x - g(x)\) 。形式選得好（ \(|g'|\) 小），收斂飛快；選得不好，直接發散。這說明：不動點迭代是設計出來的，不是撿來的。

生活類比#

照鏡子裡的鏡子會產生無窮遞縮的影像，每一層都是前一層的「縮小版」——這正是壓縮映像的視覺版本：反覆套用後，所有影像收斂到同一點。調水溫也類似：每次轉一點龍頭、感覺、再修正，逐步穩定在舒適溫度（不動點）。

演算法步驟#

基本不動點迭代：

選定 \(g\) 與初始值 \(x_0\) （最好落在不動點附近）。
重複 \(x_{k+1} = g(x_k)\) 。
檢查停止條件： \(|x_{k+1} - x_k| < \varepsilon\) 或達最大迭代次數。
回傳 \(x_{k+1}\) 。若迭代次數用盡仍未停機，應懷疑不收斂。

Python 範例#

求 \(x = \cos(x)\) 的不動點（Dottie number，約 0.7390851332）：

import math

def fixed_point(g, x0, eps=1e-12, max_iter=200):
    x = x0
    for k in range(max_iter):
        x_new = g(x)
        if abs(x_new - x) < eps:
            return x_new, k + 1
        x = x_new
    raise RuntimeError("不收斂：超過最大迭代次數")

val, n = fixed_point(math.cos, 1.0)
print(f"x = cos(x) 的不動點 ≈ {val:.12f}，迭代 {n} 次")

# 反例：g(x) = x^2 + 1 無實不動點，迭代會發散
try:
    fixed_point(lambda x: x*x + 1, 0.5, max_iter=50)
except RuntimeError as e:
    print("失敗：", e)

複雜度與收斂性分析#

單次迭代成本即 \(g\) 的計算成本。若 \(|g'(x)| \le L < 1\) ，誤差滿足 \(|x_k - x^*| \le L^k |x_0 - x^*|\) （線性收斂）。要達精度 \(\varepsilon\) 約需 \(k \ge \ln(\varepsilon/|x_0 - x^*|)/\ln L\) 次迭代。 \(L\) 越小越快：把方程改寫使 \(|g'|\) 接近 0，是改善收斂最廉價的手段。收斂階的嚴格定義見 2.3 節。

練習#

把 \(f(x) = x^3 - 2\) 改寫成至少兩種不動點形式 \(x = g(x)\) ，畫出 \(|g'(2^{1/3})|\) 的大小，判斷哪種會收斂。
用 fixed_point 求 \(x = e^{-x}\) 的不動點，並驗證答案代入後誤差小於 \(10^{-12}\) 。
畫出（或手繪） \(g(x) = 1 + x/2\) 的蛛網圖，說明為什麼收斂是單調且線性的。