為何以迭代求特徵值
特徵值問題 一般不能通過有限次有理運算解出,所以計算必須是迭代的。對大型矩陣,通常不需要全部特徵對,只需要最大的一個,或最接近某目標的一個。冪法與逆迭代只用矩陣與向量乘積或線性求解便能做到。它們是最簡單的特徵值算法,也是更複雜算法的基礎。本單元用到消去法與迭代求解各單元中的線性方程組求解與分解概念;浮點運算的誤差分析只在此提及,並不展開。
定義與假設
設 為實 矩陣。全篇假設 可對角化且特徵值皆為實數 ,特徵向量 構成一組基。
定義 17.1.1
(嚴格主導特徵值)
若對所有 有 ,稱 為嚴格主導。此時其餘特徵值排成 ,而比值 滿足 。
把初始向量寫成 。係數 量度初始向量含有多少所求的特徵向量;以下定理假設 。
定義 17.1.2
(冪法與瑞利商)
冪法產生 ,即 。非零向量 的瑞利商(Rayleigh quotient)為 ;當 對稱時它最為有用。
定義 17.1.3
(位移為 的逆迭代)
設實數 不是 的特徵值。位移為 的逆迭代是對 施行冪法:解 ,再歸一化 。
矩陣 只分解一次,此後每步只需兩次三角求解。
收斂定理
定理 17.1.4
(冪法的收斂)
設 嚴格主導,,且 。則
因此 ,其中 。於是 以幾何速率 趨近 所生成的直線(若 , 的正負號交替)。
證明
(在特徵基中展開初始向量)
展開 並用 ,得 。除以 得恆等式;再用三角不等式及 得不等式。把趨近 的向量歸一化,所得單位向量趨近 ;當 時,因子 造成正負號交替。
定理 17.1.5
(對稱情形下的瑞利商)
在冪法收斂定理的假設下,再設 對稱,並取 為標準正交基。則對冪法的迭代,
故特徵值估計以速率 收斂,是向量收斂速度的兩倍。
證明
(瑞利商的標準正交展開)
瑞利商不受縮放影響,所以 ,其中 ,。由標準正交性,,,故
利用 、分母 ,以及 。
證明透視
誤差為何變成平方
對稱性只用了一次:它容許取標準正交特徵基,使 與 都只是平方 之和,沒有交叉項 。減去 後,分子中 的項消失,只剩下各個小係數的平方。每一項除以 後都帶有 , 正由此而來。主導性經由 進入,而 使分母不為零。對非對稱矩陣,交叉項以一階大小保留下來,速率退回 ;下文常見錯誤一節會檢驗一個具體矩陣。
定理 17.1.6
(逆迭代的收斂)
設 不是特徵值,且對所有 有 ,並設 。則迭代以幾何速率 趨近 所生成的直線。
證明
(逆迭代就是對逆矩陣施行冪法)
,故 。 的特徵值為 ,模最大者對應下標 ,由假設它嚴格主導。對 應用冪法收斂定理,比值為 。
選取更接近 的 可使速率更快,而每步成本不變。此時 接近奇異,但實際上並不損害所算得解的方向,因為大的誤差正好落在 自身的方向上。
例題
例題 17.1.7
(冪法與瑞利商)
設 ,特徵值為 (向量 )與 (向量 ),。此處 。未歸一化的迭代為 ,即 。瑞利商為
| 0 | |||
| 1 | |||
| 2 | |||
| 3 |
例如 時 ,,。相繼誤差之比 、、 趨近 ,與瑞利商定理的預測一致。
例題 17.1.8
(帶位移的逆迭代)
對同一個 取 ,最接近 。此時 ,行列式為 ,速率為 。由 出發,解一次得(差一個比例),再解一次得 。在特徵基下,,且 ;對 有 ,,,與預測相符。瑞利商為 ,,趨近特徵值 ;這是不帶位移的冪法找不到的。
例題 17.1.9
(負的主導特徵值)
設 、,故 ,。於是 ;歸一化後的 在 為偶數時趨近 ,在 為奇數時趨近 。數列 沒有極限,但它趨近的直線正是特徵值 的特徵向量所在直線,與冪法收斂定理所說一致。瑞利商則確實收斂:
時誤差為 及 ,比值接近 。對稱情形的誤差界 給出 及 ,確實大於實際誤差。
常見錯誤與細微之處
常見錯誤
(以為必定有主導特徵值)
若 (例如 ),便沒有主導特徵值,迭代未必趨近任何直線。位移 把所有特徵值移動同一數量,或可恢復主導性。
常見錯誤
(忽略初始向量的分量)
若 ,在精確運算下迭代收斂到另一個特徵向量;浮點捨入誤差通常會重新引入 的分量,但很慢,所以 極小的初始向量並不好。
常見錯誤
(期望向量本身收斂)
向量只在比例和正負號之內收斂,負主導特徵值的例子正說明這一點;應用瑞利商或分量之比來估計 。
冪法每步是一次矩陣向量乘積;逆迭代每步是用已存分解作一次求解,絕不顯式求逆。不可對角化或含複特徵值的情形需要另行分析,上述定理並不涵蓋。瑞利商定理中的對稱假設也不是可有可無的。
反例模式
加倍的速率需要對稱性
斷言:冪迭代的瑞利商總以速率 收斂。取非對稱矩陣 ,特徵值為 (向量 )與 (向量 ),故 ;再取 。則 ,其中 ,且 。因此
()時誤差為 ;()時為 。比值約為 ,接近 而非 ;事實上誤差的大小約為 。修正後的陳述正是定理本身:對稱 的速率為 ,一般可對角化的 的瑞利商只承襲向量的速率 。
習題
快速檢查
(對 (特徵值 與 )及 ,計算 的 ,並用特徵向量寫出 的公式。)
先求特徵值 與 的特徵向量,再以它們展開 。
解答 · 答案
,,。特徵向量為: 對應 , 對應 ,且 。因此 。 時:,,與直接計算一致。第一分量之比 正趨近 。
快速檢查
(證明 、 時冪法不收斂,並提出一個可補救的位移。)
先計算頭幾個迭代向量及 的特徵值。
解答 · 答案
特徵值為 ,模相等,沒有主導特徵值。迭代為 ,來回交替而不收斂。矩陣 的特徵值為 與 ,對它用冪法有嚴格主導的特徵值 (特徵向量 ,比值 ),再減去 便得 的特徵值。
快速檢查
(某冪迭代的誤差按 下降。要把誤差縮小到 倍,需要多少次迭代才有保證?)
兩邊取對數。
解答 · 答案
需要 ,即 。故需 次迭代。
快速檢查
(對 及位移 ,給出逆迭代的收斂速率,並由 作兩次求解。)
最接近 的特徵值是 ,另一個是 。
解答 · 答案
速率為 。 的行列式為 ,逆矩陣為 。第一次求解:。第二次求解:。分量之比由 變為 ,趨近特徵值 的特徵向量 的比值 。