Krylov 子空間

假設對一個巨大的矩陣 A，你唯一能廉價做的就是用它乘一個向量。你能從這一種運算裡搭出什麼？從 b 出發，你能得到 Ab，再得 A(Ab) = A^2 b，如此繼續。維數為 k 的 Krylov 子空間就是這些向量的張成：K_k(A, b) = span{b, Ab, A^2 b, ..., A^{k-1} b}。它是任何唯一工具就是矩陣-向量乘積的方法的天然舞台。

為何這是正確的搜尋空間？因為 A 的多項式都住在這裡。K_k 中任何向量都是某個次數低於 k 的多項式 p 對應的 p(A) b。所以在 K_k 中搜尋 Ax = b 的良好近似解，等同於問哪個多項式 p 使 p(A) b 最接近 A^-1 b。Cayley-Hamilton 定理甚至保證 A^-1 本身就是 A 的一個多項式，故當 k 足夠大時，精確解就落在 Krylov 子空間裡。

現代迭代求解器幾乎無一例外都是 Krylov 方法：共軛梯度、GMRES、MINRES、BiCGStab。它們的差別只在於從這個不斷增長的子空間裡挑哪個向量（極小化殘差？讓殘差與該空間正交？），以及如何通過 Arnoldi 或 Lanczos 廉價地為它構造一組標準正交基。

這一思想的威力在於：當 n 極其巨大時，子空間維數 k 卻可以保持很小。若 A 的特徵值聚集成團，低次多項式就已能使 p(A) b 成為極佳近似，故方法在遠少於 n 步內收斂。這種聚集正是預條件力圖製造的東西。