克雷洛夫子空間
/ KREE-loff /
想像你對矩陣 A 只被允許做一件事：拿它乘一個向量。你不能分解它、不能窺看它的內部、甚至不能儲存它——你只能遞給它一個向量，拿回 A 乘那個向量。光憑這一招，你能建出 A x = b 的哪些解？從右端項 b 開始。對它作用 A，得 A b。再作用一次 A，得 A^2 b。繼續下去。由 b, A b, A^2 b, A^3 b, ... 一直到 A^{k-1} b 所張成的空間，就是維度為 k 的克雷洛夫子空間。它是「只用矩陣向量乘積、從 b 出發所能觸及」的整個向量宇宙。
為什麼這是該找的地方？因為一個深刻的代數事實：由凱萊-哈密頓定理，A^{-1} b——精確解——本身就是「A 的某個多項式」作用在 b 上的結果，所以真答案就「住在」某個克雷洛夫子空間裡（維度至多 n）。因此克雷洛夫方法在不斷成長的子空間 span{b, A b, ..., A^{k-1} b} 中，尋找它在那裡能找到的最佳近似解；而隨著子空間長大，它終究必定包含精確答案。不同方法對「最佳」的定義不同——共軛梯度法最小化能量，GMRES 最小化殘差範數，MINRES 對對稱問題最小化殘差——但它們全是克雷洛夫方法，差別只在於從同一個克雷洛夫子空間中取出哪個最佳向量。
這個想法是超越定常迭代的一大躍進。像雅可比法這類定常方法，機械地重複一個固定的步；克雷洛夫方法則記住它探索過的所有方向，挑出最佳組合，這正是它能用遠少的步數收斂的原因。整套機制只倚賴一個便宜的運算——矩陣向量乘積——這正是稀疏與無矩陣場合所能提供的。唯一的實務困擾是：原始的克雷洛夫向量 A^k b 很快會變得幾乎平行（它們都朝主特徵向量傾斜），所以實務上會先用阿諾迪或蘭索斯程序為子空間建一組正交基底，再做最佳化。
三步之後，克雷洛夫子空間為 span{b, A b, A^2 b}。克雷洛夫方法在這個三維空間中尋找使某種誤差量度最小的 x_3。若 A 只有 3 個相異特徵值，精確解早已落在此子空間中，方法便在 3 步內結束，不論 n 多大。
從 b, A b, A^2 b, ... 建出解——只用矩陣向量乘積。
原始的冪向量 b, A b, A^2 b, ... 很快在數值上變得近乎線性相依（它們對齊主特徵向量），所以絕不直接使用；阿諾迪／蘭索斯程序會把它們正交化。克雷洛夫收斂強烈取決於譜，這正是預條件如此重要的原因。