第2章 不動點迭代#

章前言#

許多「求解」問題都可以改寫成同一個形式：找一個 \(x\) ，使得 \(x = g(x)\) 。這樣的 \(x\) 稱為不動點。求 \(\sqrt{2}\) 等價於解 \(x = \frac{1}{2}(x + 2/x)\) ；解線性方程組 \(A\mathbf{x} = \mathbf{b}\) 等價於求 \(\mathbf{x} = (I - A)\mathbf{x} + \mathbf{b}\) 的不動點；甚至「一個經濟體的均衡價格」也是供給函數的不動點。不動點觀點把千變萬化的求解問題統一成一種迭代： \(x_{k+1} = g(x_k)\) 。

本章建立這個統一框架的理論核心。2.1 節介紹不動點的直觀與壓縮映像的概念；2.2 節敘述並「示範證明」巴拿赫不動點定理（壓縮映像原理）——它是保證迭代收斂的最重要定理，結論乾淨漂亮：只要 \(g\) 是壓縮映像，不動點存在、唯一，且從任何起點出發迭代都會收斂到它；2.3 節定義收斂階（線性、超線性、平方）與誤差估計，教你比較不同迭代法的快慢，並在實作中判斷何時可以安心停機。

學完本章，第 3 章的牛頓法、第 4 章的 Jacobi 與 Gauss-Seidel 法，都只是這個框架的具體實例。