移位與縮減

素樸的 QR 演算法可行，但可能慢得令人痛苦——它只線性收斂，受制於可能接近 1 的特徵值大小比值。兩項改良把它從一件珍奇玩物變成每個線性代數函式庫裡那快速可靠的引擎：移位（讓收斂爆炸般地快）與縮減（不再把功夫浪費在已找到的特徵值上）。兩者合起來，就是「跛行的演算法」與「飛馳的演算法」之別。

移位利用的洞見與反冪法相同。你不分解 A，而是分解 A - sigma I = Q R，再形成 R Q + sigma I（保留特徵值，但把收斂重新對準 sigma）。把 sigma 選在某特徵值附近，會讓右下角的次對角元素每步以接近零的因子縮小——收斂變成二次，對稱矩陣則三次。標準選擇是維爾金森移位（Wilkinson shift）：取右下角 2x2 角塊中最接近右下元素的那個特徵值，即使兩個特徵值很接近也很穩健。縮減是它的記帳搭檔：一旦某個次對角元素 h_{k+1,k} 降到容差以下（基本上是捨入誤差乘以矩陣範數），你就宣告對應的對角元素為已收斂的特徵值，把那個次對角設為精確的零，然後只在較小的前導分塊上繼續運作。作用中的問題每次縮小一兩個特徵值。

回報巨大：有了移位，每個特徵值通常 2 到 3 次疊代就收斂，而縮減使後面的特徵值成本逐步降低，所以一個 n×n 矩陣的整個譜在 O(n^3) 的功夫內求得。這裡有個微妙的誠實點：縮減把矩陣分裂，但你把一個極小卻非零的次對角元素設為零，引入了向後誤差——你找到的是一個被輕微擾動後的矩陣的精確特徵值。因為那擾動在捨入誤差的等級、而演算法向後穩定，這正是你該預期並接受的精度。