第4章 線性系統的迭代解法#

章前言#

解線性方程組 \(A\mathbf{x} = \mathbf{b}\) 是科學計算用量最大的運算。直接法（如高斯消去、LU 分解）在矩陣為 \(n \times n\) 時成本 \(O(n^3)\) ，且會破壞矩陣的稀疏性。但現實中的巨型線性系統——流體力學網格、電路網、頁面排名、影像重建——動輒千萬維度，且極度稀疏（每列只有幾個非零元素）。此時直接法在時間與記憶體上都不可行，迭代法成為唯一選擇：反覆精煉一個近似解，每步只做矩陣-向量乘法 \(O(\text{nnz})\) ，並保留稀疏結構。

本章依難度遞進介紹三代方法。4.1 節的 Jacobi 與 Gauss-Seidel 法是不動點迭代（第 2 章框架）在線性系統的直接應用：把 \(A\) 拆開、解出對角部分、反覆代入。4.2 節的 SOR 在其上加「鬆弛因子」加速，展示如何用一個參數調收斂速度。4.3 節的共軛梯度法則是質的飛躍：不只修正方向，而是讓每步誤差方向互相「正交」，理論上 \(n\) 步內精確收斂，是對稱正定系統的標準解法。

全章的統一視角仍是不動點迭代： \(\mathbf{x}_{k+1} = G(\mathbf{x}_k)\) 的收斂條件是迭代矩陣的譜半徑小於 1——這是 2.2 節壓縮映像原理在矩陣世界的化身。