為何用迭代而非分解

假設你要解 A x = b，其中 A 是一個百萬乘百萬的矩陣，但幾乎每個元素都是零——比方說每一列只有五個非零元，這正是把物理問題在網格上離散化、每個點只跟鄰居互動時會發生的情形。像高斯消去法這類直接法，原則上能在有限步內給出精確答案。麻煩在於：消去過程進行時，會在原本是零的地方產生新的非零元——這叫做填入（fill-in）——於是原本稀疏的矩陣變得稠密。要儲存並處理一個稠密的百萬乘百萬矩陣，大約需要 10^12 個數字與 10^18 次運算，根本無望。所以我們不去「算出」答案，而是「逼近」它。

迭代法從一個猜測 x_0（通常就取零）出發，產生一個序列 x_1, x_2, x_3, ...，若一切順利，這序列會朝真正的解前進。每一步只要做幾次矩陣向量乘積 A 乘一個向量，而稀疏的 A 乘向量很便宜——運算量大約等於非零元的個數，這裡約 500 萬，而非 10^12。我們從不更動 A、從不製造填入、也從不儲存任何稠密的東西。一旦目前的 x 夠接近，就停下來，這通常遠在 n 步之前就達成。代價是答案是近似的，且我們得判斷何時該停；報酬是有幾百萬個未知數的問題終於變得可解。

經驗法則：矩陣小、或中等大小且稠密、或當你要用同一個 A 解很多個右端項（分解一次重複使用）時，用直接法。當 A 又大又稀疏時，就改用迭代法——而最關鍵的是，迭代的好壞完全取決於它的預條件子。對一個難題做天真的迭代會慢如蝸牛甚至停滯；真正的工夫在於挑一個好的預條件子，讓收斂變快。這就是為什麼面對離散化偏微分方程所產生的巨大稀疏系統時，預設做法是迭代而非分解。