相似矩陣與變化的元素
特徵值算法可以改變矩陣,而不改變它的特徵值。在無位移 QR 迭代中,先分解當前矩陣,再把兩個因子按相反次序相乘。
定義 5.5.1
(無位移 QR 迭代)
從 出發,分解並重新組合:
這裏 是正交矩陣, 是上三角矩陣。對非奇異矩陣,我們選取 對角元素為正的唯一 QR 分解。
最後一個等式說明 與 正交相似,因此保留對稱性和特徵值。我們希望矩陣逐漸接近對角矩陣,使對角元素成為有用的特徵值近似。
下面只在一個具體的二維情形中證明這種行為,並非斷言它對所有矩陣成立。
定理 5.5.2
(對稱 2 階矩陣的 QR 迭代收斂)
設實對稱正定矩陣 具有標準正交特徵向量 和特徵值 。假設第一座標向量在 方向有非零分量:
則 收斂到 ,非對角元素的絕對值為 ,對角誤差為 。若 ,非對角元素起初就是零。
為甚麼 QR 迭代跟隨原矩陣的冪
記 ,。重複使用相似變換得到 。
引理 5.5.3
(迭代給出冪的 QR 分解)
對每個 ,
並且這是 的正對角 QR 分解。
證明
(對冪次歸納)
先取 ,此時空乘積為 。然後 ;因此將歸納假設左乘 ,得到 。各 的乘積是對角元素為正的上三角矩陣,所以 (1) 是 的正對角 QR 分解。
有了 (1),收斂定理便化為對 的冪迭代。
證明
(由第一列讀出迭代矩陣的行為)
分解 (1) 的第一列是 。在特徵向量基下展開,
它生成的直線與 生成的直線的夾角 滿足 。與其正交的單位向量也接近 生成的直線。在這個變化的標準正交基下,非對角元素的絕對值為 ;第一個對角誤差為 ,第二個則有相反的誤差。因此非對角元素為 ,對角誤差為 。
證明透視
一個算法,兩種觀點
QR 迭代不斷改變座標: 是在隨 變化的標準正交基下寫出的 。等式 (1) 說明這個基來自 的 QR 分解,其第一列就是對 的普通冪迭代;第二列則由正交性決定,所以在二維空間中一列就足夠。各 的對角元素為正,固定了符號,因此第一個基向量是 。假設 使夾角遠離直角, 使其正切衰減。正定性只用來使特徵值的次序與它們的模的次序一致。
例子與停止資訊
例題 5.5.4
(手算第一個迭代矩陣)
對 ,特徵值為 和 ,且 ,所以 。第一步中, 的兩列為 和 。Gram-Schmidt 給出 、;然後 ,餘量 的長度為 ,所以 的第二列是 。因此
這與證明中的公式一致: 給出 、,所以非對角元素為 ,第一個對角元素為 。
推論 5.5.5
(由對角元素得到譜區間)
對稱迭代矩陣 滿足: 的某個特徵值位於 ,並且某個特徵值位於 。
證明
(座標向量的殘差)
將單位向量 和近似特徵值 代入,殘差是 ,範數為 。對對稱矩陣,若單位向量對數值 的殘差範數為 ,則必有特徵值與 相差不超過 :把該向量在標準正交特徵基下展開,殘差平方為 。矩陣 與 有相同的特徵值。對 和 的論證相同。
這是精確算術下的殘差證書。
例題 5.5.6
(後面的迭代矩陣與譜區間)
繼續取 。由 ,公式給出 、 和 (跡為 ):
| 0 | 2 | 1 | 2 |
| 1 | 2.8 | 0.6 | 1.2 |
| 2 | 2.97561 | 0.21951 | 1.02439 |
| 3 | 2.99726 | 0.07397 | 1.00274 |
時,兩個區間 與 重合,都是 ,所以不能用來分開兩個特徵值。 時它們是 和 ; 時是 和 :區間半徑 每步縮小的倍數趨近 ,與速度 的預測一致。
常見錯誤
(把兩個重疊的區間當作兩個特徵值)
每個區間只保證其中有某個特徵值。如果兩個對角區間重疊,如上面 的情形,證書並不保證它們確定不同的特徵值;兩個區間可能指向同一個特徵值。
例題 5.5.7
(已經按正確次序對角化的矩陣)
對 ,,所以 、。正對角分解為 、,於是 ,每個迭代矩陣都等於 。非對角元素起初就是零,與定理對 的陳述一致。
假設排除了甚麼情況
反例模式
QR 迭代永遠不改變的對稱矩陣
很容易以為每個實對稱矩陣都會被驅向對角形式。取 。它既對稱又正交,特徵值為 和 。其正對角 QR 分解是 ,因此每個 QR 迭代都等於 ,非對角元素永遠不消失。此時 在 與 之間交替,故其生成的直線不收斂。這個不定例子不屬於正定定理;特徵值的模相同使冪迭代論證失效。每個迭代矩陣都有正確的譜,但矩陣本身沒有變化:僅有正交相似性並不能迫使非對角元素減小。
常見錯誤
(以為較大的特徵值必定排在前面)
即使 正定,初始分量也影響所述排序:若 ,則 ,所以 ,假設不成立。迭代始終保持這個順序。它已經是對角矩陣,卻沒有變成 。
實用的 QR 特徵值求解器還採用位移和降階等方法;它們的收斂和浮點分析需要單獨論證。
練習與解答
快速檢查
(為甚麼 與 有相同的特徵值?)
把 用 表示出來。
解答 · 答案
,其中 正交,所以 與 相似,而相似矩陣有相同的特徵多項式。
快速檢查
(在正定定理中,第一基方向的幾何速度由甚麼決定?)
看夾角 的正切。
解答 · 答案
幾何速度是 ;初始係數比控制乘法常數。對角誤差每步的速度是 。
快速檢查
(若對稱迭代矩陣的某個對角元素 、非對角元素 ,給出第一列所保證的譜區間。)
使用殘差 。
解答 · 答案
至少有一個特徵值位於 。
快速檢查
(當 時會發生甚麼?若要求較大特徵值排在第一位,定理的哪個假設失效?)
等於哪個特徵向量?
解答 · 答案
每個迭代都是同一個對角矩陣; 在 的特徵方向上沒有分量,所以 不成立。