預條件

迭代求解器在良態、特徵值聚集的矩陣上收斂得快，在病態矩陣上則爬行。預條件就是把後一種掰成前一種的招數：不去解 Ax = b，而是解等價系統 M^-1 A x = M^-1 b，其中 M 選得使 M^-1 A 好得多——特徵值簇擁在 1 附近，條件數很小。解保持不變；只是迭代所穿行的幾何變好了。

訣竅在於 M 內置的取捨。理想的預條件子是 M = A 本身，使 M^-1 A = I 而一步收斂——但施加 M^-1 的代價就和解原問題一樣大。所以好的 M 必須同時是兩件事：A 的不錯近似（使 M^-1 A 良態）且施加起來廉價（使每次迭代仍負擔得起）。每個預條件子都是這兩極之間的折衷。

常見選擇橫跨這一光譜。雅可比（對角）和高斯-賽德爾預條件子幾乎免費但偏弱。像 ILU 或不完全 Cholesky 這樣的不完全分解丟棄完整分解會產生的填入，以適中代價給出更強的 M。多重網格和區域分解預條件子精巧，對它們所針對的偏微分方程，可使迭代次數幾乎與問題規模無關。

這有多決定性，怎麼強調都不為過。對主導科學計算的大型稀疏系統，預條件子的選擇通常遠比 Krylov 方法的選擇重要。一個平庸的求解器配上極佳的預條件子，常常勝過一個極佳的求解器卻沒有預條件子。選好 M 是撬動迭代性能的最大那根槓桿。