一個慢吞吞的迭代法其實悄悄在蓋什麼
在上一篇，你看著雅可比法與高斯-賽德爾法一步步爬向答案，只有當它們迭代矩陣的譜半徑小於 1 時才收斂——而且常常爬得慢得令人心痛。它們共有一個值得盯著看的樸素習慣：從當前猜測出發，算出殘差 r = b - A x，而它們對矩陣做的唯一昂貴動作，就是「乘上它」。它們從不分解 A，甚至從不窺看它的內部。那一次乘法——A 乘上一個向量——就是全部的預算。
現在問一個狡猾的問題。從 x_0 = 0 出發，於是第一個殘差就是 r_0 = b。做一次矩陣乘法後，你也看得到 A b。做兩次後，A^2 b。做 k 次乘法後，你能用「看過的東西」組合出來的所有向量，就只是 b、A b、A^2 b 一直到 A^{k-1} b 的加權和。這個不斷長大的張成空間有個名字：維度為 k 的克雷洛夫子空間，寫作 K_k。每一個只用 A 做乘法的迭代法，無論它自己知不知道，都被困在這道子空間階梯上——每一階都比前一階高一個維度。
把 A x = b 變成滾下山坡
共軛梯度法處理一個特殊但極其常見的情形：A 是對稱正定（SPD）的——對稱，且對每個非零 x 都有 x^T A x > 0。彈簧、最小平方法的正規方程、熱傳與靜電裡離散化的拉普拉斯算子，給你的正是這類矩陣。對 SPD 矩陣有個魔術：求解 A x = b 等同於「找一只碗的底部」。定義能量 phi(x) = (1/2) x^T A x - b^T x。因為 A 是 SPD，這個曲面是一只完美的向上開口的碗，只有單一個最低點，而在那一點上它的梯度恰好是 A x - b。梯度消失——碗觸底——的時刻，恰恰就是 A x = b 成立之時。
於是「解線性方程」變成了「求極小」，而殘差 r = b - A x 就是字面意義上的下坡方向（負梯度）。最顯而易見的點子是最速下降法：反覆沿著 r 走一步。它有效，但對一只又長又扁的碗，它會令人抓狂地之字形前進：每一步都抵銷掉上一步的部分進展，因為新的下坡方向不知道舊步伐已經指向哪裡。之字形的次數與 A 的條件數同階——一只被拉長的病態碗就是一條又長又窄的山谷，天真的下降法會在它的兩壁之間永遠彈來彈去。
共軛的訣竅：彼此永不干擾的搜尋方向
賦予共軛梯度法其名的修正，是去挑選一組搜尋方向，使它們在「被 A 扭曲過的幾何」裡彼此垂直——稱為 A-共軛：兩個方向 p 與 q 滿足 p^T A q = 0 時，就是 A-共軛的。回報美得驚人。如果你沿著一組 A-共軛方向各自做精確的極小化，那麼沿著一個新方向最佳化，永遠不會破壞你在舊方向上已經贏得的最佳性。沒有抵銷，沒有之字形。每一步都是乾淨而永久的進展，而在精確算術下，你最多 n 步就能解出一個 n×n 系統的精確答案。
接下來這部分簡直像變魔術。你或許會擔心：要建出一整組 A-共軛方向，豈不是得記住所有先前的方向、並對它們一一重新正交化——既昂貴又吃記憶體？對 SPD 矩陣，不必。一條短短的三項遞迴式就包辦了全部：下一個方向 = 新殘差 + 一個純量乘上前一個方向。CG 只存少數幾個向量、每次迭代只做一次矩陣-向量乘積，然而每個新方向都自動地與所有先前方向 A-共軛。這近乎奇蹟的精簡，正是 A 的對稱性替你買來的；一旦失去對稱性它就消失，這也是為什麼下一篇需要更笨重的 GMRES。
Conjugate Gradient for SPD system A x = b (start x = 0)
r = b # residual = negative gradient of the bowl
p = r # first search direction
repeat:
Ap = A * p # the ONE matrix-vector product per step
alpha = (r . r) / (p . Ap) # exact 1-D minimum along p
x = x + alpha * p # take the step
r_new = r - alpha * Ap # update residual (no extra A multiply)
if ||r_new|| <= tol * ||b||: break # relative stopping test
beta = (r_new . r_new) / (r . r)
p = r_new + beta * p # new direction, auto A-conjugate to all past
r = r_new有多快，以及何時該停
「最多 n 步」這個保證在理論上很可愛，但實務上無關緊要——對於有上百萬個未知數的系統，你根本不會想跑 n 步。CG 之所以被珍視，真正的原因是它通常在遠遠更少的步數內就達到夠好的答案。誠實的收斂估計說：k 步之後誤差大約以 ((sqrt(kappa) - 1)/(sqrt(kappa) + 1))^k 的速率縮小，其中 kappa 是 A 的條件數。把它跟最速下降法對條件數的依賴比一比：CG 依賴的是 sqrt(kappa)，而非 kappa——這可能就是「幾千次迭代」與「幾十次迭代」之間的差別。
那條公式帶著一個直白的警告。收斂速度由 kappa 決定，所以一個病態的 A 仍會讓 CG 龜速前進。這正是第五篇存在的全部理由：預處理子 M 近似 A 但求解起來很便宜，把 CG 套用在條件數更好的「變換後系統」上，迭代次數就會崩塌式地下降。對一個討厭的拉普拉斯算子，純 CG 可能要幾千步；配上好的預處理子，只要幾十步。面對難題時，永遠不要在沒打算預處理的情況下就抓起 CG。
因為你會提早停下，你需要一個誠實的停止準則，而 CG 免費奉送你一個：它每一步都更新殘差，所以你可以盯著 ||r|| 下降，並在 ||b - A x|| <= tol 乘以 ||b|| 時停手——這是個相對測試，因為沒有尺度的話，絕對大小毫無意義。不過要說兩個誠實的警告。第一，殘差小並不保證 x 的誤差小：兩者之間的橋樑又是條件數，所以在病態系統上，你可能殘差極小、x 卻仍明顯偏差。第二，在真實的浮點算術裡，那美麗的 A-共軛性會因捨入誤差而緩慢侵蝕，所以課本上的「n 步內精確」從來不會真正成立；CG 是被當成一個誠實的迭代法來用——跑到殘差夠小為止——而不是一個有限步的直接法。
為什麼這很重要，又通往何處
退一步衡量這筆划算的交易。對一個稠密的 n×n SPD 矩陣做直接的喬列斯基分解，要花 O(n^3) 的運算與 O(n^2) 的儲存，而在稀疏矩陣上它還可能因填入而把兩者都撐大。CG 每次迭代只花一次矩陣-向量乘積，且只存幾個向量。如果 A 每列只有寥寥幾個非零元——離散化 PDE 的常態——那次乘積就是 O(n)，而一旦 n 跑到上百萬，幾百次迭代就以天文數字般的差距勝過 O(n^3)。這正是本級第一篇「為何要迭代而非分解」的承諾，如今變得鋒利明確。
「A 只透過『A 乘上一個向量』被碰到」這句話裡，藏著一個更深的回報。你根本完全不需要把 A 當成一個明確的數字陣列——只需要一個常式：給它一個向量 v，回傳 A v。這就是無矩陣的點子，而它令人解放：一個龐大離散化算子的「作用」，可以由一個差分樣板即時算出，而矩陣從不被組裝或儲存。克雷洛夫方法是無矩陣計算的天生夥伴，求解器正是靠這個，才搆得到那些「以明確矩陣形式根本塞不進記憶體」的問題規模。