共軛梯度法

共軛梯度法是迭代求解器的皇冠寶石，專用於 A 為對稱正定（SPD）的特殊情形——這類矩陣來自彈簧、電路、與離散化橢圓型偏微分方程中的能量最小化。魔法始於一次改寫：解 A x = b 恰恰等同於找一個碗狀函數的谷底，即能量 phi(x) = (1/2) x^T A x - b^T x。因為 A 是對稱正定，這個曲面是一個完美向上的碗、只有單一最低點，而那最低點就是解。於是解線性系統變成滾下坡到最小值。

下坡最天真的辦法是最速下降法：永遠沿最陡下降方向走（負梯度，正好是殘差 r = b - A x）。但在一個拉長、橢圓的碗上，最速下降法令人抓狂地之字形繞行，反覆走回它已探索過的方向。CG 用一個絕妙的想法解決：挑選彼此 A-正交（也稱共軛）的搜尋方向，意思是不同方向滿足 p_i^T A p_j = 0。有了共軛方向，沿某方向取得的進展，永不被後續步驟推翻——每個方向都「一次了結」。其驚人的後果是：在精確算術下，CG 至多 n 步就抵達精確解，因為 n 個共軛方向張成整個空間。而它做到這點，只儲存少數幾個向量、每步一次矩陣向量乘積——無需顯式記住整段歷史。

實務上你幾乎從不跑滿 n 步。CG 在能量範數下的誤差幾何衰減，速率由 A 的條件數 kappa 決定：大致上，k 步後的誤差受一個如 ((sqrt(kappa) - 1)/(sqrt(kappa) + 1))^k 的因子所限。所以良態系統（kappa 小）幾步就收斂；病態的則爬行。更妙的是，若 A 的特徵值聚成少數幾群，CG 能用約等於群數的步數收斂——遠少於 n。這正是為什麼預條件（把 A 變換得使其譜聚集）是讓 CG 變快的關鍵，而帶預條件的 CG 是科學與工程中求解大型稀疏對稱正定系統的預設主力。