消去法撞上的那堵牆
在前面那一級，你學到了求解 A x = b 的黃金標準：高斯消去法，它把 A 分解成 A = L U 一次，之後再用前代與回代便宜地求解。它是精確的（差個捨入誤差），配上樞軸選取又很穩健，而對一個尺寸為 n 的稠密系統，它大約花 (2/3) n^3 次浮點運算。對 n = 1000 來說，那大約是十億次浮點運算——不到一秒。到目前為止，消去法看起來無懈可擊，而對小型或中型的稠密系統，它確實如此。這一級並不是要取代它；而是要談談它悄悄地、開始裝不下的那個地方。
現在想想巨大系統實際上從哪裡來。把熱傳導方程或應力場離散化在一個 100 x 100 x 100 的三維網格上，你就會在每個網格點上得到一個未知數——一個 n = 一百萬的系統。稠密消去法的 (2/3) n^3 成本，現在大約是 7 x 10^17 次浮點運算，即使每秒一兆次浮點運算，單單解一次也要算上大約一星期。更糟的是，光是儲存稠密矩陣 A 就要 n^2 = 10^12 個數，雙精度下是八兆位元組（八 TB）。無論時間還是記憶體，都遠遠付不起。稠密的做法不是稍微變慢，而是直接墜崖，因為 n^3 與 n^2 增長得太凶猛。
稀疏性：消去法一再摧毀的那個結構
那些網格矩陣有一個救命的恩典：它們是稀疏的。一個網格點只跟它周圍少數幾個鄰居耦合，所以 A 的每一列大概只有 5 個或 7 個非零元素，而不是一百萬個。那個稠密儲存時需要八兆位元組的矩陣，當你只存非零元素時，只需要大約七百萬個數——區區幾十 MB，輕鬆。稀疏性正是讓「百萬未知數問題」根本變得可以想像的那份禮物。但有個陷阱：你必須用一種尊重這份禮物的方式來處理矩陣，而天真的消去法做不到。
痛苦的部分來了。當消去法消去一個變數時，它會把某一列的倍數加到其他列上，於是原本是零的位置可能變成非零。那些新冒出的非零元素叫做填入（fill-in）。一個一開始每列只有 7 個非零元素的稀疏矩陣，可能一路填入到它的 L 和 U 因子變成稠密，把記憶體預算又重新炸回去。對未知數做巧妙的重排序能把填入壓低——這正是稀疏直接求解器背後的藝術，而對二維問題它運作得漂亮極了。但對三維網格，填入在最壞情況下無可避免，因子的增長遠超線性，又把記憶體拖回你想逃離的那道懸崖。
所以真正的張力很尖銳。直接消去法精確又可靠，但它與稀疏性作對——它老是想去填滿那些「讓問題變得可解」的零。我們想要一種只以「保留稀疏性」的方式去碰 A 的方法。而對一個稀疏矩陣，剛好有一種運算幾乎不花成本、又從不製造填入：用矩陣去乘一個向量。就是這單單一個觀察，成了出路的那扇門。
迭代的想法：猜測、衡量、改進
一個迭代法放棄了「在固定步數內抵達精確的 x」。取而代之，它從一個猜測 x_0 出發——常常就是全零——並產生一串 x_1、x_2、x_3、...，若一切順利，它會朝著真正的解前進。當目前的猜測夠好時，你就停下來。這跟你在求根時已經見過的精神一樣，那時不動點迭代把 x = g(x) 變成 x_{n+1} = g(x_n)，再讓一個收縮映射把你拉向答案。用迭代求解 A x = b，就是把那個想法從單一個數，提升到一整個向量。
在不知道真正的 x 的情況下，方法怎麼知道一個猜測好不好？它衡量殘差 r = b - A x_current。如果 x 是精確的，A x 就會等於 b，殘差就會是零；r 的大小告訴你 A x 落在離 b 多遠的地方。關鍵在於，計算殘差只需要一次稀疏的「矩陣乘向量」乘積 A x，外加一次減法——正是我們剛剛指認出的那個便宜、又保留稀疏性的運算。這一級裡的每一個迭代法，骨子裡都是一份巧妙的食譜，把殘差轉化成一個修正量，把 x 推得更近。
the skeleton every iterative solver shares:
x = x0 # initial guess (often all zeros)
repeat:
r = b - A*x # residual: one sparse mat-vec, no fill-in
if ||r|| / ||b|| < tol: # close enough? stop.
break
x = x + (correction from r) # the method's secret sauce lives here
cost per step is dominated by the single product A*x ,
which for a sparse A with ~7 nonzeros/row is O(n), not O(n^2).你交換出去的，與你換回來的
這個交換是真實的，所以兩邊都要誠實面對。你放棄了精確性：迭代求解器回傳的是一個近似值，而你必須透過替相對殘差 ||b - A x|| / ||b|| 選一個容忍度，來決定「多準才算夠準」。（我們會在後面的篇章仔細處理殘差與停止準則，因為小殘差不會自動代表小誤差——那道落差由條件數掌管，跟條件性那一級講的一模一樣。）你也放棄了「分解一次、求解多次」這個可愛的性質：一個 LU 分解能幾乎免費地對許多右端向量 b 求解 A x = b，而一個基本的迭代法面對每個新的 b 都得重新開始它的長征。
你換回來的，是一切讓「百萬未知數問題」裝得下的東西。記憶體：迭代求解器從不建構 L 和 U，所以它除了 A 的非零元素和幾個長度為 n 的工作向量之外，什麼都不需要——有時它甚至不顯式儲存 A，只需要一個能回傳 A x 的常式，這正是無矩陣方法背後的想法。時間：對稀疏的 A，每一步花 O(n)，而如果方法所需的步數隨 n 增長得很慢，整個求解就能跑在幾乎 O(n) ——正是我們一直追求的那個近乎線性的增長率。這就是那筆划算的交易：用精確性和固定步數，去換你真的付得起的記憶體，以及一個能隨規模擴展的成本。
先嚐一口：那個小小的定常食譜，以及它通往何處
讓我們用最早的一族迭代法——定常方法——把這個抽象變得摸得到。它們來自一個叫「矩陣分裂」的把戲：把 A 拆成一個容易求逆的部分 M 加上剩餘，A = M - (M - A)。於是 A x = b 變成 M x = (M - A) x + b，這暗示了迭代 x_{n+1} = M^{-1} ((M - A) x_n + b)。你每一步是去解一個便宜的、跟 M 有關的系統，而不是那個跟 A 有關的難系統。下一篇會把這個搭建成雅可比法與高斯-賽德爾法，但你已經能看見它的形狀了：挑一個容易的 M、掃一遍、重複。
但這裡正是誠實最要緊的地方，因為定常迭代並非總是收斂。x_n 究竟朝真正的 x 前進、還是永遠地漂走，是由迭代矩陣 M^{-1}(M - A) 的「譜半徑」決定的——也就是它絕對值最大的那個特徵值的大小。如果這個數小於 1，誤差每一步就按這個倍數縮小，你就贏了；如果它等於或大於 1，你就輸了，等多久都沒用。所以收斂是一個貨真價實、需要去檢查的條件，而不是一個保證——這正是你在不動點求根時所需的那個收縮條件的直接對應物。而且即使這些簡單方法收斂，它們也可能很慢，這恰恰是推動後面那些更聰明的方法登場的原因。
當你攀爬這一級其餘的部分時，這份路線圖值得記在腦中。定常方法是熱身。從它們生長出一個更深的想法——在由 b、A b、A^2 b、... 張成的Krylov 子空間裡逐步建構出解，這引向了用於對稱正定系統的共軛梯度法，以及用於一般系統的 GMRES。而那把能把「終究會收斂」變成「收斂得快」的實用鑰匙，就是預條件子：一個便宜的近似反矩陣，它重塑問題，讓迭代飛奔起來。多重網格法（接近尾聲時會瞥見它）在對的問題上，甚至能逼近那個近乎 O(n) 的理想。而這一切，仍然全都立在你剛剛遇見的那個謙卑地基上——那個稀疏的乘積 A x，一再重複。