把附近的特徵值變成佔優特徵值
冪迭代放大與最大模特徵值對應的特徵向量。要尋找接近給定位移 的特徵值,可以改為對 使用冪迭代。實際運算透過求解線性方程組進行,不必顯式形成逆矩陣。
設 且 對稱,具有標準正交特徵向量 和實特徵值 。選取不是特徵值的位移 ,並假設
定義 5.4.1
(帶位移的反冪迭代)
從 、 出發,以位移 作反冪迭代,即求解並歸一化:
在精確算術中, 可逆,故 。固定位移時,一次矩陣分解可以用於後續所有求解。
定理 5.4.2
(迭代直線的幾何收斂)
假設 ,則 生成的直線與 生成的直線之間的夾角至少以幾何速度趨於零。更精確地,令
則
這裏的夾角是直線之間的夾角,因此 的符號交替不會妨礙收斂。
證明
(位移逆矩陣的冪)
由 (2) 歸納可知, 是下式的歸一化結果:
每個係數除以 的係數。所得正交部分的歐幾里得(Euclidean)範數等於兩條直線夾角的正切,且不超過 (3) 右側。條件 (1) 保證 。
證明透視
位移為甚麼改變目標
位移後逆矩陣的特徵值是 。 中最接近 的特徵值,在取逆後變成模最大的特徵值。要得到上述一維收斂結論,必須有嚴格唯一的最近特徵值,還必須有非零的初始對應係數。
二維計算
例題 5.4.3
(對角矩陣的反冪迭代)
取 、 和 。逆矩陣的特徵值為 和 ,所以誤差比率 。第 步後第二座標與第一座標的比為 。向量可能反向,但其生成的直線迅速接近第一座標軸。
常見錯誤
(以為位移後的矩陣必定正定)
這個位移比起 更接近 ,但 是不定矩陣。對稱性仍然保留,正定性卻沒有保證。因此不能假定要求矩陣對稱正定的 Cholesky 求解器適用於每一種位移。
殘差提供事後證書
定理 5.4.4
(對稱矩陣的殘差證書)
對該對稱矩陣 、任意單位向量 和實數 ,定義 。則
因此區間 至少包含一個特徵值。
證明
(在特徵基中展開)
展開 ,則
由於係數的平方和為一,便得到 (4)。
對於非零非單位向量,類似的界需將殘差範數除以 。該形式的證書依賴對稱性。僅憑該結論,無法確定它定位的是哪一個特徵值,也無法在特徵值聚集時證明某個特徵向量方向。
命題 5.4.5
(Rayleigh 商使殘差最小)
對固定的單位向量 ,Rayleigh 商 使 在實數 中最小。
證明
(對位移配方)
將平方展開:。這是 的二次函數,首項係數為正,其導數 只在 處為零。
常見錯誤
(輕信隨便算出來的殘差)
在精確算術中,小殘差給出數學證書。實際計算的殘差本身也必須有足夠的精度,才能支援預期保證:若 與 幾乎相等,它們在浮點運算中的差可能被捨入誤差主導。
反例模式
位移不能憑空產生缺失的分量
令 、,並取 。反冪迭代始終留在第二座標軸上。在精確算術中,它永遠不會到達目標特徵向量,因為初始對應係數為零。同樣,位移恰好等於特徵值時方程組奇異,不滿足上述假設。實際計算的捨入誤差可能引入缺失分量。兩個不同特徵值到位移等距也可能使迭代不收斂:取 、,當兩個分量都非零時迭代會在兩條直線之間交替。
帶證書的例題
例題 5.4.6
(較差的向量給出的寬鬆證書)
設 ,單位向量 。則 ,,所以 。區間為 ,其中含有特徵值 ,但不含 。界 (4) 並不尖銳:。殘差大時,得到的結論較弱,但仍然正確。
例題 5.4.7
(沿迭代過程的證書)
繼續取 、 和 。在每個迭代向量處計算 和 :
| 0 | 2.5 | 1.5 |
| 1 | 1.01523 | 0.21320 |
| 2 | 1.000078 | 0.015306 |
當 時,區間 的兩個端點恰好是兩個特徵值,所以 (4) 取等號。 時區間為 ,其中含有 ; 時 ,而證書半徑為 。證書半徑依次縮小約 倍和 倍;漸近地每一步的倍數為 。
例題 5.4.8
(兩個特徵值到位移等距)
對 、 和 ,逆矩陣的特徵值為 和 。第一次求解得 ,於是 ,下一次求解得 。迭代向量在兩條不同的直線之間交替,並不收斂;但取 時,每個殘差證書 都等於 ,並正確地把一個特徵值定位在 內。
練習與解答
快速檢查
(對特徵值 和位移 ,反冪迭代的比率 是多少?)
比較兩個特徵值到位移的距離。
解答 · 答案
。
快速檢查
(為甚麼即使 生成的直線收斂,向量也可能交替改變符號?)
看 的符號。
解答 · 答案
當 時,佔優的逆矩陣特徵值 為負,因此 的係數每一步都會變號,而它生成的直線不變。
快速檢查
(一個單位向量的 Rayleigh 商為 、殘差範數為 。由 (4) 可得到甚麼保證?)
取 、。
解答 · 答案
至少有一個特徵值位於 ;僅憑該證書不能確定它是哪一個。
快速檢查
(如果最接近位移的特徵值重數為二,為甚麼上面收斂到指定單個特徵向量的證明不適用?)
哪一個假設不成立?
解答 · 答案
嚴格不等式 (1) 不成立,佔優逆特徵空間為二維。若初始向量在該空間上的投影非零,迭代直線收斂到該投影生成的直線;否則在精確算術中永遠不會到達該空間。