蘭索斯演算法
/ LAN-tsosh /
想像一個大到連存成完整陣列都辦不到、只能拿來做乘法的對稱矩陣——數百萬列。你不想要它全部的特徵值；你只要極端處的少數幾個（最大的幾個，或最小的幾個），這正是振動分析、量子化學、譜圖方法中會遇到的需求。QR 演算法在此毫無指望：它需要完整矩陣且會把全部都找出來。蘭索斯演算法（Lanczos）正是為這份工作打造的工具——只用矩陣乘向量，求一個巨大稀疏對稱矩陣的少數極端特徵值。
它是冪法的聰明表親。冪法把每個中間向量 A v、A^2 v、A^3 v 都丟掉，只留最後一個；蘭索斯把它們留下，並記得它們合起來張成一個克雷洛夫子空間（Krylov subspace），其中蘊含的譜資訊遠多於任何單一向量。從一個向量 q_1 出發，它一次造一個向量，建立克雷洛夫空間的正交歸一基底，而對稱性的魔法讓這成為一個「短」的三項遞迴：每個新基底向量只需前兩個（q_{j+1} 來自 A q_j 減去它在 q_j 與 q_{j-1} 上的投影）。在那個基底下，巨大的矩陣 A 由一個大小為 k 的微小三對角矩陣 T_k 表示。你計算 T_k 的特徵值（便宜，因為 k 很小）——這些是 Ritz 值，其極端者驚人地快速收斂到 A 的極端特徵值。
兩個誠實的告誡。第一，在精確算術下基底向量正交，但在浮點下，一旦某個 Ritz 值收斂，它們就「喪失正交性」——已找到特徵值的幽靈副本會冒出來。實務的蘭索斯必須重新正交化（完全、選擇性或部分）才能保持可靠，或偵測並丟棄那些假副本。第二，蘭索斯在「極端」特徵值上發光；內部特徵值收斂很慢，所以要瞄準內部區域，得搭配移位反求（shift-and-invert）步驟（把內部變成極端，代價是解線性系統）。用得好，蘭索斯能找出一個十億乘十億稀疏矩陣的最大十個特徵值，這是任何稠密方法都碰不得的。
要找一個一千萬乘一千萬的圖拉普拉斯矩陣（你只擁有它作為一個會把向量相乘的函式）的最大兩個特徵值，跑蘭索斯，比方說 50 步。你建出一個 50x50 的三對角 T，計算它的特徵值，最上面兩個 Ritz 值已與 A 的最大兩個特徵值吻合到許多位數——代價是 50 次矩陣乘向量，而非一千萬的三次方的浮點運算。
蘭索斯用三項遞迴把巨大稀疏對稱矩陣投影到一個小的克雷洛夫子空間，再從一個小的三對角矩陣讀出極端特徵值。
浮點下喪失正交性是核心的實務陷阱：它會產生假的重複（幽靈）特徵值，所以任何正式的蘭索斯都採用某種重新正交化方案。沒有它的素樸教科書蘭索斯，會悄悄把同一個特徵值回報好幾次。