共軛梯度法

共軛梯度法，簡稱 CG，是面向對稱正定系統 Ax = b 的 Krylov 求解器。它背後有一個優美的重新詮釋：求解 Ax = b 等價於極小化二次能量 phi(x) = (1/2) x^T A x - b^T x，其唯一極小點就是解。CG 在這個碗狀曲面上向下走，但走得很巧妙。

樸素的最速下降在被拉長的碗裡來回曲折，效率很差。CG 通過選取 A-共軛的搜尋方向來糾正這點：方向 p_i, p_j 滿足當 i 不等於 j 時 p_i^T A p_j = 0。共軛方向之間從不互相抵消進展。結果是，在精確算術下，CG 至多 n 步就到達 n 階系統的精確解——它技術上是一種直接法，儘管我們總是迭代地使用它。

使 CG 實用的是它驚人的節儉：每步只需一次矩陣-向量乘積、幾個內積和少數幾次向量更新，且無論 n 多大都只存幾個向量。它構造的 Krylov 子空間與眾人相同，但憑藉對稱性，用一個簡短的三項遞推就找到能量極小點，而無須儲存整組基。

收斂與條件數 kappa = lambda_max / lambda_min 掛鉤。經典界說，k 步後的 A-範數誤差大致按 ((sqrt(kappa) - 1) / (sqrt(kappa) + 1))^k 縮小。良態或特徵值聚集的矩陣幾步就收斂；病態的則爬行——這正是 CG 幾乎總要配預條件子執行的原因。