為甚麼近似特徵向量有用
特徵向量指出線性變換保持的方向,相應特徵值給出沿該方向的縮放。對大型矩陣而言,為了求一個特徵對而構造特徵多項式並求其所有根,可能計算昂貴且在數值上困難。冪迭代則反覆應用矩陣,使主導特徵值對應的分量相對於其他分量增長。這只有在初始向量含有該分量,且各特徵值的模具有嚴格間隔時才按下述方式奏效。
我們先使用實向量和 Euclidean 範數。複特徵值及非對稱矩陣需要額外注意:特徵值的模不同於它們的代數大小,非對稱矩陣的特徵向量也不必正交。除明確討論捨入外,下文迭代結論均指精確算術。
歸一化冪迭代
定義 5.2.1
(歸一化冪迭代)
設 ,起點 。每當 時,計算
第一步後每個迭代向量的範數都是一。歸一化限制向量的增長或下溢;在精確算術中它不改變方向。若某次乘積為零,上述更新無定義,實現時必須停止或選擇其他起點。
定理 5.2.2
(主導特徵值定理)
設 , 有實特徵向量基 ,對應實特徵值滿足
寫 ,並假設 。令 。則每一步都有定義,歸一化迭代趨近 生成的直線。更精確地,對 ,
常數可依賴於 和 。若 ,符號交替:直線收斂,但帶方向的向量一般不收斂。當模的比值接近一時收斂緩慢;初始主導分量的大小也會影響初期表現。
證明
(提出主導冪因子)
在特徵向量基中展開:
括號中除 外的和,由三角不等式知其範數至多為 。其 係數始終為 ,所以 非零。將 歸一化便得到迭代向量。括號中的表達式趨近非零向量 ,因此當 足夠大時,其範數有遠離零的下界。映射 在遠離零的局部區域 Lipschitz,故歸一化保留 誤差。因子 給出所示符號。
證明透視
冪迭代證明中各假設在哪裏起作用
因子 被提出,所以一切都由括號中的向量讀出,該向量收斂到 。嚴格不等式 使每個比值 都以 的速度衰減。假設 用了兩次:它使極限向量非零,因而歸一化在其附近是光滑映射;它也使每一步都有 。實特徵向量基則使展開成為可能。若 、 且 ,同一論證表明迭代改為收斂到 的方向;若 ,比值不衰減,論證甚麼也得不到。
實特徵向量基是充分條件,不是必要條件。缺陷矩陣及複主導特徵值對需要另行分析;不能僅因為某個特徵值在列表中寫在第一位就應用此定理。若 ,所有非主導分量在取一次正整數次冪後便消失,結論立即成立。
例題 5.2.3
(對角矩陣上的冪迭代)
對 、,第 個歸一化迭代為
方向以由 決定的速度趨近 。若改取 ,每次迭代都等於該向量:方法找到特徵值 2,卻永遠不會發現 4。精確乘法的重複不會修復初始主導係數為零的問題。
Rayleigh 商與殘差
定義 5.2.4
(Rayleigh 商)
對非零 ,其 Rayleigh 商為
若 是滿足 的精確實特徵向量,則商等於 。非零縮放(包括改變符號)不改變該商。因此即使歸一化冪迭代的符號交替,它仍可用於估計特徵值。
命題 5.2.5
(對稱矩陣的 Rayleigh 商)
若 為實對稱矩陣,選取特徵值為 的標準正交特徵向量基 。寫 ,則
此商是加權平均,權重非負且和為一。這些界依賴於對稱性和實特徵值;任意實矩陣不一定滿足。
定理 5.2.6
(對稱矩陣的商收斂)
設 為實對稱矩陣, 為標準正交特徵向量基,,初始向量沿 的係數非零,並設 如主導特徵值定理中所定義。則
證明
(在特徵向量基中看商誤差)
記 。商的誤差為 。非主導係數相對於主導係數為 ,其平方給出上述速度。
這個更快的商誤差估計源於正交性,不能對一般非對稱矩陣直接假定。
例題 5.2.7
(向量誤差與商誤差)
對上述對角矩陣例子,
向量方向誤差的尺度是 ,而商誤差的尺度是 。這些速度描述精確算術中 增大時的行為;捨入和有限精度最終會限制改進。
由於 ,最初幾個迭代向量給出:
| 第二座標 | 商誤差 | |
|---|---|---|
| 1 | 0.4472 | 0.4000 |
| 2 | 0.2425 | 0.1176 |
| 3 | 0.1240 | 0.0308 |
第二座標每步大約減半,而商誤差每步縮小的倍數接近四,與尺度 和 相符。
定理 5.2.8
(特徵值殘差證書)
給定候選值 和非零 ,定義特徵對殘差 。其與縮放無關的範數是 。對稱矩陣 滿足
證明
(在特徵向量基中展開)
展開 。殘差範數平方為 ,至少等於最小距離的平方乘以 。開方並除以 即得該界。
常見錯誤
(把小殘差當作鄰近特徵向量)
殘差小只能保證附近有某個特徵值;但它本身不能指出是哪一個,也不能證明 接近指定的特徵向量。後者需要分離的單特徵值及進一步估計。
反例模式
殘差很小卻沒有鄰近特徵值
非對稱矩陣中,相同的特徵值距離結論可能嚴重失效。取 、,其中 。兩個特徵值都是 1,但當 時,
而 到譜的距離始終為一。小殘差仍有後向解釋:擾動 的秩至多為一,滿足 ,其範數為 。但這不必迫使未擾動的非正規矩陣具有鄰近特徵值。
失敗情形與尋找其他特徵值
主導特徵值定理中模的嚴格間隔,不能減弱為 ,下面的例子說明了這一點。
反例模式
模相等時沒有主導直線
對 、,迭代在 和 間交替。對應直線不趨於單一特徵方向。兩個特徵值的模相同,缺少嚴格間隔條件。在實數運算中,一對複主導共軛特徵值也可能產生旋轉行為。
若要尋找選定實位移 附近的特徵值,可以對 使用冪迭代,前提是 可逆。若 ,變換後的特徵值為 ;若距離 唯一最近的實特徵值是單重的,它便成為模唯一最大的變換後特徵值。若 有實特徵向量基且起始向量沿該方向的分量非零,前述定理說明變換算子的冪迭代在精確算術中趨近該特徵方向。計算時每一步求解 ,而不是顯式形成逆矩陣。位移接近特徵值可以加快分離,但也使方程求解變得病態。若 本身是特徵值,逆不存在,上述迭代無定義。
例題 5.2.9
(以反迭代尋找特徵值 4)
設 ,。則 可逆,。逆矩陣的特徵值 來自 ,是模唯一最大的一個,比率 。從 出發, 步後的方向與 成比例。 時它與 成比例,Rayleigh 商為 ; 時它與 成比例,商為 。方向趨近 ,商趨近 ,儘管 既不是 的最大特徵值,也不是最小特徵值:是位移選定了目標。若取 ,則 奇異,迭代便沒有定義。
常見錯誤
(以相鄰迭代向量接近作為停止準則)
停止時,縮放殘差比單純觀察相鄰歸一化迭代向量是否接近更有資訊量。小變化可能反映停滯或符號約定,而 與 代表相同特徵方向。解釋殘差大小時,仍須考慮矩陣結構、尺度、精度及所需特徵值間隔。
練習與解答
快速檢查
(從 出發,對 做一步歸一化冪迭代,並求結果的 Rayleigh 商。)
先把 歸一化。
解答 · 答案
,所以 。其商為 。
快速檢查
(對 、,帶方向的迭代序列是否收斂?其特徵方向和 Rayleigh 商如何變化?)
看 的符號。
解答 · 答案
主導特徵值為 ,對應係數非零。迭代向量趨近符號交替的 ,所以帶方向的序列不收斂;特徵方向趨近 ,Rayleigh 商趨近 。
快速檢查
(對 ,用位移 作反迭代。變換後哪個特徵方向佔主導?說明對初始向量的一個條件。)
算出 的特徵值。
解答 · 答案
變換後的特徵值為 。唯一最大模為 1,對應原特徵值 4 和 。起始向量的第二座標必須非零。
快速檢查
(實對稱矩陣的候選對 滿足 和 。可對其譜得出甚麼結論?若沒有更多資訊,對指定特徵向量不能得出甚麼結論?)
使用殘差證書。
解答 · 答案
至少有一個特徵值與 的距離不超過 。這本身不能確定是哪個特徵值,也不能證明接近指定特徵向量;需要間隔及適當的特徵向量估計。