上一節在二維情形研究的無位移 QR 迭代只是線性收斂,速度由特徵值之比決定,而且對稠密的 矩陣,每一步都要做一次階數為 的完整 QR 分解。實際使用的方法消除了這兩個障礙。第一,先用正交相似把矩陣一次性約化為接近三角形的上 Hessenberg 形。第二,每個 QR 步用特徵值的估計值作位移,使最後一個次對角元迅速變小。第三,一旦該元素可以忽略,就把問題分出來(收縮),在較小的矩陣上繼續。本節證明使每個階段成立的事實。本節用到 Householder QR 一節中的 Householder 反射、QR 迭代恆等式 ,以及本章前面各節的反冪迭代。
定義
定義 5.6.1
(上 Hessenberg 矩陣)
實矩陣 稱為上 Hessenberg 矩陣,若 時 ;它在對角線及其以上,以及第一條次對角線上可以非零。
定義 5.6.2
(Householder 反射與 Givens 旋轉)
Householder 反射為 ( 為非零向量),它是對稱的正交矩陣。作用於第 行的 Givens 旋轉 除下面的分塊外與單位矩陣相同:
對於給定的 ,取 ,,便使 的第二個分量為零。
定義 5.6.3
(帶位移的 QR 步與 Rayleigh 位移)
位移為 的帶位移 QR 步取方陣 ,計算分解 ( 正交, 上三角),並構造
Rayleigh 位移為 ,即最後一個對角元。
因為 ,所以 ,即 與 正交相似,具有相同的特徵值。
定義 5.6.4
(收縮)
若把次對角元 置零,使矩陣成為塊上三角,就稱矩陣被收縮。
Hessenberg 約化
定理 5.6.5
(約化為 Hessenberg 形)
對每個實 矩陣 ,存在由 Householder 反射相乘得到的正交矩陣 ,使 為上 Hessenberg 矩陣。若 對稱,則 為三對角矩陣。
證明
(逐列消去)
令 ,對 構造 ,其中 , 是 中如下選取的 Householder 反射。設 為 第 列對角線以下的部分。取 ,其中當 時 ,否則 (這個符號避免相消),並在 時取 (當 時取 )。則 。
左乘 只改變第 行,並使第 列在第 行的元素為零。對列 ,其第 行的元素本來就是零(因為 ),零的線性組合仍為零,所以這些列不變。右乘 只組合第 列,所以第 列保持其全部零元素。做到 時,每一列 在第 行都是零,所以 是上 Hessenberg 矩陣,並且由於每個 都是對稱正交矩陣,,其中 。若 ,則 對稱;對稱的 Hessenberg 矩陣在第一條次對角線以下為零,由對稱性在第一條超對角線以上也為零,所以是三對角矩陣。
證明透視
為甚麼反射從對角線以下開始
約化依賴於每次乘法觸及哪些行和列。向量 取自第 列、從第 行開始,所以 只作用於第 行與列。左乘使第 列在第 行以下化為零,並且不動第 行;右乘只組合第 列,碰不到第 列,所以已經造出的零得以保留。若反射改為從對角元開始構造,右乘就會把第 列本身與後面的列組合,剛造出的零一般會重新被填上。因此相似變換只能負擔得起清除第一條次對角線以下的元素;剩下的次對角線,正是後面的 QR 迭代要驅使趨於零的部分。符號 另有作用:由於 ,只要 就有 ,並且 的第一個分量的計算不會發生相消。
約化所需的運算次數與 成正比,而且只需做一次。
Hessenberg 矩陣上帶位移的 QR 步
定理 5.6.6
(QR 步保持 Hessenberg 形)
設 為上 Hessenberg 矩陣,。從 出發,對 ,令 為作用於第 行的 Givens 旋轉,其選取使當前矩陣的 元素為零。則 為上三角矩陣, 為正交矩陣且 ,並且 是上 Hessenberg 矩陣。每一步的代價為 次運算。
證明
(以旋轉化為三角形,再乘回)
矩陣 是 Hessenberg 矩陣,所以第 列在對角線以下只有一個非零元素,位於第 行。施加 時,前面的旋轉 已使第 列成為上三角,並且只改變了第 行;第 行仍是原樣,所以 元素就是原來的元素。旋轉把它化為零,並且不影響第 列(它們在第 行的元素為零)。做完 次旋轉後,矩陣是上三角矩陣,即 。由 得 。
為了計算 ,把 依次右乘 、 等等; 把第 列與第 列換成它們自身的線性組合。令 。我們用歸納法證明: 的第 列只在第 行有非零元素(而當 時只在第 行有非零元素)。 時這就是 的三角性。在 中,第 列只在第 行有元素(它是 的第 列的組合,或者就是 的第 列),而第 列就是 的第 列,元素在第 行。於是它們在 中的組合只在第 行有元素,這對 和 滿足所述性質;其他列不變。取 ,即知 是上 Hessenberg 矩陣, 亦然。每個旋轉改變兩行(左乘)或兩列(右乘),長度至多為 ,所以代價為 次運算,一步的代價為 。
對一般稠密矩陣,同樣的分解需要 ,所以 Hessenberg 形使每一步的代價降低約一個 的因子。
定理 5.6.7
(Q 的最後一列是反冪迭代向量)
若 非奇異,其中 正交, 上三角,則 的最後一列 滿足 ,其中 是 的最後一個對角元。因此 。並且 的最後一個次對角元滿足 。
證明
(逆轉置的最後一列)
由 得 。矩陣 是下三角矩陣,所以它的最後一列是 。因此 。取範數,由 得 的公式。 的最後一行是 ,所以 的最後一行是 最後一行的 倍,位置 的元素為 ,且 。
當 對稱時,,所以 是以位移 、從 出發的一步反冪迭代;並且恰當這一步放大得很強時, 才小,也就是 接近某個特徵值,而該特徵向量的最後一個分量非零。對於對稱的 及其特徵對 ,其中 、 且 ,有 ,因此 。Rayleigh 位移 是 的 Rayleigh 商,所以是這種特徵值的自然估計。本節不證明 Rayleigh 位移的收斂速度;對於對稱三對角矩陣,實際上是三次收斂,下面的例子可見。
Rayleigh 位移在實際中效果很好,但「它必定有進展」這個說法並不成立。
反例模式
Rayleigh 位移可能令矩陣原封不動
很容易以為,取 Rayleigh 位移 的每一步都會令最後一個次對角元變小。取 ,它本來已是 Hessenberg 矩陣,所以 。此時 ,其 QR 分解(取 的對角元為正,這時分解唯一)為 ,。於是 :這一步重現了 ,次對角元仍然等於 。實際程式改用 Wilkinson 位移,即右下角 塊中最接近 的特徵值。這裏該塊就是 本身,兩個特徵值 和 與 同樣接近,取其中任何一個都能一步使矩陣收縮。
算法與收縮
EIGENVALUES(A):
reduce A to Hessenberg form H = Q^T A Q
m = n
while m > 1:
repeat
choose a shift mu (for example h[m][m])
apply one shifted QR step to the leading m-by-m block of H
until |h[m][m-1]| is negligible
record h[m][m] as an eigenvalue; set h[m][m-1] = 0; m = m - 1
record h[1][1]
若 ,則 ,兩個對角塊為方陣,且 ,所以 的特徵值就是 與 的特徵值(按重數計)。因此當 時, 是特徵值,問題化為左上角的 塊。在浮點運算中,「可忽略」指小於單位捨入誤差乘以 的一個小倍數;把這樣的元素置零,相當於對 作了同樣大小的擾動。實矩陣若有共軛複特徵值,就不能用實正交相似化為三角形:迭代最後得到 對角塊,只看單個次對角元的停止準則可能永遠不能滿足,需要複位移或雙位移,本節不討論。對稱矩陣的特徵值全為實數。
概念視角結構
次對角元為零即不變子空間
寫 ,,其中 是前 列。由 得 ,而 恰好等價於 ,即 的前 列所生成的子空間在 之下不變。因此收縮就是分出一個不變子空間, 的特徵值正是 限制在該子空間上的特徵值。
例題
例題 5.6.8
(3 階矩陣的 Hessenberg 約化)
設
只需要一個反射()。第 列對角線以下的向量為 ,。因為 ,取 ,與 成比例。則 ,。取 ,
相似不變量的檢查:跡為 ; 的行列式為 ;兩個矩陣的 主子式之和都是 。 元素為零,所以 是 Hessenberg 矩陣。
例題 5.6.9
(以特徵值作位移,一步收縮)
設 ,特徵值為 和 ,取 。則 ,其中 ,,並且
一步就得到兩個特徵值。這是退化的情形: 是奇異矩陣,,所以關於最後一列的定理不能照原樣應用;但界 與此結果一致,因為當 時右端趨於 。
例題 5.6.10
(三對角矩陣上帶位移的 QR 步)
設 ,取 Rayleigh 位移 。則 。第一個旋轉取 :,。施加它之後,第二列在第 行的元素為 ,然後第二個旋轉取 ,得主元 ,,。結果為
且 。計算 得
其跡為 。以 重複,得到下表(已捨入):
| 步數 | ||
|---|---|---|
| 0 | 1 | 1 |
| 1 | 0.2711 | 0.5714 |
| 2 | 0.003859 | 0.53950 |
| 3 | 0.5394951 |
三步之後,次對角元可以忽略,所以 是 的特徵值,精確到約八位數字。剩下的塊 含有另外兩個特徵值,它的跡 等於 ,與應有的結果一致。最後兩次縮小與三次收斂相符:,而實際觀察到的是 。
常見錯誤與細節
常見錯誤
(Hessenberg 形不是三角形)
約化為 Hessenberg 形是正交相似,所以特徵值保持不變,但結果是 Hessenberg 矩陣而不是三角矩陣:第一條次對角線一般非零,所以還不能直接讀出特徵值。
常見錯誤
(忘記加回位移)
帶位移的 QR 分解的是 而不是 。若算出 後不加回 ,得到的矩陣的特徵值就是 的特徵值平移 。
常見錯誤
(一直使用同一個位移)
位移應當在每次迭代時更新;固定的位移只給出向離位移最近的特徵值的線性收斂,與固定位移的反冪迭代相同。
已經對稱的矩陣在每一步(正交相似)之後仍保持對稱,所以對稱矩陣的 Hessenberg 形的三對角結構也被保持。
Rayleigh 位移並不保證對每個初始矩陣都收斂,上面的反例就說明了這一點。三次收斂是對稱三對角矩陣上觀察到的現象,本節沒有證明。
把很小但不為零的次對角元收縮為零,是一種向後穩定的近似(對 的小擾動),並不是精確的陳述。
練習
快速檢查
(證明若對稱矩陣 用正交矩陣 約化為 Hessenberg 形 ,則 是三對角矩陣。)
先證明 是對稱的。
解答 · 答案
滿足 ,所以 對稱。若 ,由 Hessenberg 性質 ,由對稱性 (此時 ),所以只要 就有 。因此 是三對角矩陣。
練習 5.6.11
(對 ,證明位移 (另一個特徵值)也能一步收縮。)
核心
用 Givens 旋轉計算該 QR 步。
解答(3)
- 1
構造位移後的矩陣
- 2
選取使次對角元為零的旋轉
關鍵一步
依據: 取 ,,旋轉把 變為 。
- 3
乘回並加上位移
次對角元為零,兩個特徵值都出現在對角線上。
快速檢查
(證明若上 Hessenberg 矩陣 有 ,則 的譜是其左上 塊與右下 塊的譜的並集。)
當 時, 是甚麼形狀?
解答 · 答案
若 ,則第 行、第 列中對角線以下的元素全為零(Hessenberg 結構本來已使 處為零),所以 。塊上三角矩陣的行列式等於各對角塊行列式之積,所以 ,其根就是兩個因子的根。
練習 5.6.12
(對 及 ,利用最後一列的公式精確計算 ,並對照三對角矩陣的例題檢驗 。)
核心
這裏 是對稱矩陣,所以 。
解答(3)
- 1
解一個線性方程組
解 。第三個方程給 ;第一個 給 ;第二個 給 。
依據: 定理用 表示 。
- 2
應用範數公式
關鍵一步
與算出的 的最後一個對角元一致。
- 3
與次對角元比較
該元素為 ,其中 ,所以 。
快速檢查
(稠密矩陣的一步 QR 約需 量級的運算,Hessenberg 矩陣的一步 QR 約需 量級。對 ,忽略常數,比較兩者的量級,並說明當 個特徵值各需要少數幾步時節省了甚麼。)
把代價沿逐漸縮小的活動塊加起來。
解答 · 答案
當 時,,,比值為 。若 個特徵值各需要少數幾步(隨著特徵值被收縮,活動塊越來越小),Hessenberg 迭代的總代價為 量級,而用稠密步則為 量級;節省的是一個 量級的因子,代價是另加一次 量級的一次性約化。