共軛梯度法走到無路可走的地方
前一篇把 共軛梯度法 交到你手上，它幾乎像魔法：只用矩陣與向量的乘積就能解 A x = b，只需存幾個向量，然後看著誤差一路融化。但細看條款。共軛梯度法仰賴矩陣是對稱正定的（SPD）——對稱使得 A^T 等於 A，正定使得對每個非零的 x 都有 x^T A x > 0。正是第二個性質讓「解 A x = b」等價於「把一個碗狀的能量最小化」，而那個碗正是 CG 一路滑下的東西。
現在來認識那些破壞這一切的方程組。把一個朝某方向漂移的流動離散化——比方說被流動流體往下游帶走的熱——矩陣就會多出一個歪斜的項：A 不再對稱，因為物理有個偏好方向，而數學把它記了下來。許多電路方程、無矩陣 非線性求解器內部的線性化、以及工程裡的絕大多數情況，都是如此。能量碗於是傾斜成鞍面或螺旋，再沒有一個極小值可供滑向，共軛梯度法也就乾脆失去了立足的定理。
克雷洛夫的想法活了下來——便宜的遞迴關係卻沒有
延續下來的是引擎，而非那個巧技。克雷洛夫子空間 一模一樣：從殘差 r_0 = b - A x_0 出發，不斷乘上 A，建起由 r_0、A r_0、A^2 r_0……一路到 A^{m-1} r_0 所張成、逐漸長大的空間。走 m 步後，這個空間 K_m 裝著你用 m 次矩陣向量乘積所能觸及的每一個向量，而最佳的近似解就會住在它裡面。這一部分完全不需要對稱性，純粹是線性代數。
沒有延續下來的，是共軛梯度法那個美麗的祕密：一條短短的三項遞迴。對 SPD 矩陣，每個新的搜尋方向只需與前一兩個正交——拜對稱所賜，更舊的那些會自己照顧好自己——所以不論走多少步，CG 都跑在固定而微小的記憶體上。這份節省，是 A = A^T 的直接饋贈。一旦抽走對稱性，禮物就消失了：新方向不再自動與舊方向正交，也沒有捷徑能讓它如此。
於是一個非對稱的克雷洛夫法面臨一道殘酷的岔路。要嘛保住短遞迴、卻放棄「每一步都真正最優」的保證（這是 BiCGStab 那一族方法）；要嘛堅持每一步都真正最優、代價是要儲存並對著每一個先前方向做正交化。GMRES 走的是第二條路。它拒絕遺忘——而這份拒絕，既是它的長處，也是它的代價。
GMRES 到底在最小化什麼
GMRES 的整個想法可以用一句話講完：在所有住於克雷洛夫子空間 K_m 的候選解之中，挑出殘差在普通 2-範數下最小的那一個。名字本身就拼出了它——Generalized Minimal RESidual，廣義最小殘差。CG 最小化的是一個只對 SPD 矩陣才有意義的特殊能量範數；GMRES 把它丟掉，改去最小化那個誠實而普適的量 ||b - A x||_2，也就是剩餘量的長度。因為這個量對任何方陣都有意義，GMRES 對任何非奇異的 A 都管用，不論對稱與否。
但要在一個子空間上做最小化，就需要對那個子空間有一個整齊的描述，而原始的克雷洛夫向量 r_0、A r_0、A^2 r_0…… 是個糟糕的基底：它們全都朝著主特徵方向傾斜，很快就變得幾乎平行——在數值上幾乎一模一樣，像是想用三把全指著同一方向的尺去描述一個房間。解方是 阿諾爾迪迭代：它為同一個克雷洛夫空間建出一組單位正交基底 q_1、q_2、……、q_m，每一步生出一個新的垂直向量，並用改良式 格拉姆-施密特 把指向你已有方向的成分減掉。
阿諾爾迪還順手做了一件可愛的事：當它做正交化時，會把係數記錄進一個小小的 (m+1) 乘 m 矩陣，那是上海森堡形——上三角再加一條次對角線。這個小矩陣 H 是巨大的 A 投影到克雷洛夫空間後、被壓縮出來的影子。於是在那個龐大空間上的最小化，便塌縮成一個只牽涉 H 的微小 最小平方問題：在短向量 y 上最小化 ||beta e_1 - H y||_2，其中 beta = ||r_0||。你解的是一個大小為 m 的問題，而非大小為 n 的問題——而 m 通常只有幾十，n 卻可能上百萬。
GMRES, one cycle of m steps:
r_0 = b - A x_0 ; beta = ||r_0||_2 ; q_1 = r_0 / beta
for j = 1, 2, ..., m:
w = A q_j # the ONLY matrix-vector product
for i = 1..j: h_ij = q_i . w ; w = w - h_ij q_i # orthogonalize
h_{j+1,j} = ||w||_2 ; q_{j+1} = w / h_{j+1,j}
solve min_y || beta e_1 - H y ||_2 # tiny (j+1)-by-j least squares
stop when residual ||beta e_1 - H y|| is small enough
x_m = x_0 + Q_m y # combine the orthonormal basis陷阱：每一步都在長大的成本，以及重啟
現在來算誠實的帳。因為 GMRES 保留每一個基底向量，第 m 步必須把最新的向量對著全部 m 個先前向量做正交化。於是第 m 步的工作量像 m 一樣增長，走完 k 步的總工作量像 O(k^2 n) 一樣增長，而記憶體則線性增長——你同時握著 k 個全長向量。對一個有上百萬列的矩陣，光是握住幾百個這種向量就是不小的記憶體，而正交化甚至可能反客為主、蓋過矩陣向量乘積。CG 完全沒有這些；GMRES 用一張每次迭代都往上爬的帳單，換來它的普適性。
標準的脫身之道是重啟式 GMRES，寫作 GMRES(k)：跑 k 步、在那個小克雷洛夫空間裡組出最佳解 x_k，然後把整組基底丟掉，以 x_k 作為新的初始猜測重新開始。記憶體與每一輪的成本現在都被 k 所封頂。但天下沒有白吃的午餐——丟棄累積起來的子空間可能讓收斂停滯、甚至完全凍住，因為這方法忘掉了它曾付出代價才發現的那些方向。選 k 是個真正需要調的旋鈕：太小會原地踏步，太大又會重新淹沒在記憶體裡。
什麼主宰著收斂——以及接下來是什麼
對 CG，收斂的故事很乾淨：當 SPD 矩陣的特徵值聚成一團時較快、散得很開時較慢，全由條件數所概括。對 GMRES，故事則確實混沌得多，而這是這個領域裡誠實而難啃的真相之一。一個非對稱矩陣甚至未必擁有一組像樣的正交特徵向量，所以光憑特徵值無法決定 GMRES 收斂多快——你可以造出特徵值完全相同、收斂卻天差地遠的矩陣。真正的主導因素牽涉到特徵向量本身的條件好壞，而最壞情況下，GMRES 可以連續許多步幾乎平坦不動，然後才一頭栽下去。
實務上的結論，就是下一篇要重重敲進你腦袋的那一個：對一個難纏的系統直接套用 GMRES 往往沒救，而解方並不是一個更聰明的克雷洛夫法，而是一個 預處理器——一個容易求逆、用來近似 A 的 M，好讓你實際去解的是變換過的系統 M^{-1} A x = M^{-1} b，它的特徵值被擠進一個緊貼著 1 的密集團裡。一個預處理良好的 GMRES，能在十幾步內收斂，而未經預處理的版本卻可能永遠跑不完。克雷洛夫的機構是底盤；預處理器才是讓它動起來的引擎。