特徵值求解器傳回的數值結果需要加以詮釋。冪迭代提供了一個簡單的例子:反覆的矩陣乘法可以揭示主導特徵方向,但前提是起始向量本身含有該方向。殘差提供了一項有用的獨立檢驗,然而單憑細小的殘差,並不足以識別最大的特徵值。
實對稱矩陣的迭代
設 A ∈ R n × n A\in\mathbb R^{n\times n} A ∈ R n × n 為對稱矩陣,具有標準正交特徵向量 u 1 , … , u n u_1,\ldots,u_n u 1 , … , u n ,而其實特徵值滿足
∣ λ 1 ∣ > ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n ∣ , λ 1 ≠ 0. |\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n|,\qquad \lambda_1\ne0. ∣ λ 1 ∣ > ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n ∣ , λ 1 = 0.
寫 v 0 = ∑ i a i u i v_0=\sum\limits_i a_i u_i v 0 = i ∑ a i u i ,並假設 a 1 ≠ 0 a_1\ne0 a 1 = 0 。冪迭代產生 v m = A m v 0 / ∥ A m v 0 ∥ 2 v_m=A^mv_0/\|A^mv_0\|_2 v m = A m v 0 /∥ A m v 0 ∥ 2 。要評價算得的向量,會用到兩個數。
定義 14.1.1
(Rayleigh 商與特徵值殘差)
對單位向量 v ∈ R n v\in\mathbb R^n v ∈ R n ,Rayleigh 商 為 ρ ( v ) = v T A v \rho(v)=v^TAv ρ ( v ) = v T A v ,特徵值殘差 為 ∥ A v − ρ ( v ) v ∥ 2 \|Av-\rho(v)\,v\|_2 ∥ A v − ρ ( v ) v ∥ 2 。殘差為零,當且僅當 v v v 是特徵向量且特徵值為 ρ ( v ) \rho(v) ρ ( v ) 。若向量長度不是一,則取 ρ = v T A v / v T v \rho=v^TAv/v^Tv ρ = v T A v / v T v 。
令 θ m ∈ [ 0 , π / 2 ] \theta_m\in[0,\pi/2] θ m ∈ [ 0 , π /2 ] 為 v m v_m v m 與 u 1 u_1 u 1 所生成的直線之間的夾角,即 cos θ m = ∣ ⟨ v m , u 1 ⟩ ∣ \cos\theta_m=|\langle v_m,u_1\rangle| cos θ m = ∣ ⟨ v m , u 1 ⟩ ∣ 。
在上述假設下,設 r = ∣ λ 2 / λ 1 ∣ < 1 r=|\lambda_2/\lambda_1|<1 r = ∣ λ 2 / λ 1 ∣ < 1 (n ≥ 2 n\ge2 n ≥ 2 ):
對所有 m m m 都有 A m v 0 ≠ 0 A^mv_0\ne0 A m v 0 = 0 ,且 tan θ m ≤ r m tan θ 0 \tan\theta_m\le r^m\tan\theta_0 tan θ m ≤ r m tan θ 0 ,其中 tan θ 0 = ( ∑ i ≥ 2 a i 2 ) 1 / 2 / ∣ a 1 ∣ \tan\theta_0=\bigl(\sum\limits_{i\ge2}a_i^2\bigr)^{1/2}/|a_1| tan θ 0 = ( i ≥ 2 ∑ a i 2 ) 1/2 /∣ a 1 ∣ 。
Rayleigh 商滿足 ∣ ρ ( v m ) − λ 1 ∣ ≤ 2 ∣ λ 1 ∣ sin 2 θ m ≤ 2 ∣ λ 1 ∣ r 2 m tan 2 θ 0 |\rho(v_m)-\lambda_1|\le2|\lambda_1|\sin^2\theta_m\le2|\lambda_1|\,r^{2m}\tan^2\theta_0 ∣ ρ ( v m ) − λ 1 ∣ ≤ 2∣ λ 1 ∣ sin 2 θ m ≤ 2∣ λ 1 ∣ r 2 m tan 2 θ 0 。
若 λ 1 > 0 \lambda_1>0 λ 1 > 0 ,則 v m → sign ( a 1 ) u 1 v_m\to\operatorname{sign}(a_1)u_1 v m → sign ( a 1 ) u 1 ;若 λ 1 < 0 \lambda_1<0 λ 1 < 0 ,則 u 1 u_1 u 1 分量的符號交替,所以 v m v_m v m 未必收斂,但其方向收斂。
展開得 A m v 0 = ∑ i λ i m a i u i = λ 1 m ( a 1 u 1 + ∑ i ≥ 2 a i ( λ i / λ 1 ) m u i ) A^mv_0=\sum\limits_i\lambda_i^ma_iu_i=\lambda_1^m\bigl(a_1u_1+\sum\limits_{i\ge2}a_i(\lambda_i/\lambda_1)^mu_i\bigr) A m v 0 = i ∑ λ i m a i u i = λ 1 m ( a 1 u 1 + i ≥ 2 ∑ a i ( λ i / λ 1 ) m u i ) 。u 1 u_1 u 1 的係數 λ 1 m a 1 \lambda_1^ma_1 λ 1 m a 1 非零,所以 A m v 0 ≠ 0 A^mv_0\ne0 A m v 0 = 0 。由標準正交性,tan θ m \tan\theta_m tan θ m 是與 u 1 u_1 u 1 正交部分的範數除以 u 1 u_1 u 1 部分的大小:
tan θ m = ( ∑ i ≥ 2 λ i 2 m a i 2 ) 1 / 2 ∣ λ 1 ∣ m ∣ a 1 ∣ ≤ r m ( ∑ i ≥ 2 a i 2 ) 1 / 2 ∣ a 1 ∣ , \tan\theta_m=\frac{\bigl(\sum_{i\ge2}\lambda_i^{2m}a_i^2\bigr)^{1/2}}{|\lambda_1|^m|a_1|}\le r^m\frac{\bigl(\sum_{i\ge2}a_i^2\bigr)^{1/2}}{|a_1|}, tan θ m = ∣ λ 1 ∣ m ∣ a 1 ∣ ( ∑ i ≥ 2 λ i 2 m a i 2 ) 1/2 ≤ r m ∣ a 1 ∣ ( ∑ i ≥ 2 a i 2 ) 1/2 , 因為 i ≥ 2 i\ge2 i ≥ 2 時 ∣ λ i ∣ ≤ ∣ λ 2 ∣ |\lambda_i|\le|\lambda_2| ∣ λ i ∣ ≤ ∣ λ 2 ∣ 。這就是第 1 部分。寫 v m = ∑ c i u i v_m=\sum c_iu_i v m = ∑ c i u i ,其中 ∑ c i 2 = 1 \sum c_i^2=1 ∑ c i 2 = 1 ,sin 2 θ m = ∑ i ≥ 2 c i 2 \sin^2\theta_m=\sum\limits_{i\ge2}c_i^2 sin 2 θ m = i ≥ 2 ∑ c i 2 ,則 ρ ( v m ) − λ 1 = ∑ i ≥ 2 c i 2 ( λ i − λ 1 ) \rho(v_m)-\lambda_1=\sum\limits_{i\ge2}c_i^2(\lambda_i-\lambda_1) ρ ( v m ) − λ 1 = i ≥ 2 ∑ c i 2 ( λ i − λ 1 ) ,且 ∣ λ i − λ 1 ∣ ≤ 2 ∣ λ 1 ∣ |\lambda_i-\lambda_1|\le2|\lambda_1| ∣ λ i − λ 1 ∣ ≤ 2∣ λ 1 ∣ ,得第 2 部分(並用 sin θ ≤ tan θ \sin\theta\le\tan\theta sin θ ≤ tan θ )。第 3 部分:v m v_m v m 的 u 1 u_1 u 1 分量與 λ 1 m a 1 \lambda_1^ma_1 λ 1 m a 1 同號,當 λ 1 > 0 \lambda_1>0 λ 1 > 0 時符號不變,當 λ 1 < 0 \lambda_1<0 λ 1 < 0 時符號交替。
證明透視
起始向量與間隙的作用 證明的每一步都依賴一個分解:提出 λ 1 m \lambda_1^m λ 1 m 後,和式變成一個主導項加上一些比值 ( λ i / λ 1 ) m (\lambda_i/\lambda_1)^m ( λ i / λ 1 ) m ,而由於嚴格間隙 ∣ λ 2 ∣ < ∣ λ 1 ∣ |\lambda_2|<|\lambda_1| ∣ λ 2 ∣ < ∣ λ 1 ∣ ,這些比值全都趨向零。假設 a 1 ≠ 0 a_1\ne0 a 1 = 0 用來在 tan θ 0 \tan\theta_0 tan θ 0 中除以 ∣ a 1 ∣ |a_1| ∣ a 1 ∣ ,也正是它保證主導係數 λ 1 m a 1 \lambda_1^ma_1 λ 1 m a 1 永不為零;沒有它,tan θ 0 \tan\theta_0 tan θ 0 是無窮大,界便甚麼也沒說。對稱性(標準正交特徵向量)使各部分的範數可按 ∑ a i 2 \sum a_i^2 ∑ a i 2 相加,並使 Rayleigh 商的誤差是夾角的二次式:ρ ( v m ) − λ 1 \rho(v_m)-\lambda_1 ρ ( v m ) − λ 1 中的一階項互相抵消,因為 u 1 u_1 u 1 是 v ↦ v T A v v\mapsto v^TAv v ↦ v T A v 在單位球面上的臨界點。收斂速率是比值 r r r ,所以間隙很小時,即使其他條件都有利,收斂也很慢。
若 a 1 = 0 a_1=0 a 1 = 0 ,主導方向便不出現在任何 A m v 0 A^m v_0 A m v 0 中,這個論證失效。對非對稱矩陣,重複或虧損特徵值需要額外分析;不要在沒有這些假設的情況下搬用此證明。
迭代例子詳解
取 A = diag ( 4 , 2 ) A=\operatorname{diag}(4,2) A = diag ( 4 , 2 ) 、v 0 = ( 1 , 1 ) T / 2 v_0=(1,1)^T/\sqrt2 v 0 = ( 1 , 1 ) T / 2 。頭兩個正規化迭代值為
v 1 = ( 2 , 1 ) T 5 , v 2 = ( 4 , 1 ) T 17 . v_1=\frac{(2,1)^T}{\sqrt5},\qquad
v_2=\frac{(4,1)^T}{\sqrt{17}}. v 1 = 5 ( 2 , 1 ) T , v 2 = 17 ( 4 , 1 ) T . 此處 r = 1 / 2 r=1/2 r = 1/2 ,tan θ 0 = 1 \tan\theta_0=1 tan θ 0 = 1 ,而確實 tan θ 1 = 1 / 2 \tan\theta_1=1/2 tan θ 1 = 1/2 、tan θ 2 = 1 / 4 \tan\theta_2=1/4 tan θ 2 = 1/4 ,所以定理第 1 部分取等號。對單位向量 v v v ,Rayleigh 商 ρ = v T A v \rho=v^TAv ρ = v T A v 是特徵值的估計。在 v 2 v_2 v 2 處,
ρ = 4 ⋅ 16 + 2 17 = 66 17 , A v 2 − ρ v 2 = ( 8 , − 32 ) T 17 17 , ∥ A v 2 − ρ v 2 ∥ 2 = 8 17 . \rho=\frac{4\cdot16+2}{17}=\frac{66}{17},\qquad
Av_2-\rho v_2=\frac{(8,-32)^T}{17\sqrt{17}},\qquad
\|Av_2-\rho v_2\|_2=\frac8{17}. ρ = 17 4 ⋅ 16 + 2 = 17 66 , A v 2 − ρ v 2 = 17 17 ( 8 , − 32 ) T , ∥ A v 2 − ρ v 2 ∥ 2 = 17 8 . 殘差不為零,所以這還不是精確的特徵對。商的誤差是 4 − 66 / 17 = 2 / 17 ≈ 0.118 4-66/17=2/17\approx0.118 4 − 66/17 = 2/17 ≈ 0.118 ,小於界 2 ⋅ 4 / 17 ≈ 0.47 2\cdot4/17\approx0.47 2 ⋅ 4/17 ≈ 0.47 。商趨近 4 這個結論用到起始向量和譜間隙的假設,而不是單靠殘差。
取 A = diag ( − 3 , 1 ) A=\operatorname{diag}(-3,1) A = diag ( − 3 , 1 ) 、v 0 = ( 1 , 1 ) T / 2 v_0=(1,1)^T/\sqrt2 v 0 = ( 1 , 1 ) T / 2 ,故 r = 1 / 3 r=1/3 r = 1/3 。則 v 1 = ( − 3 , 1 ) T / 10 v_1=(-3,1)^T/\sqrt{10} v 1 = ( − 3 , 1 ) T / 10 ,v 2 = ( 9 , 1 ) T / 82 v_2=(9,1)^T/\sqrt{82} v 2 = ( 9 , 1 ) T / 82 :第一個分量的符號交替,所以向量並不收斂,但 tan θ m = 3 − m \tan\theta_m=3^{-m} tan θ m = 3 − m 顯示其方向收斂。商為 ρ ( v 1 ) = ( − 27 + 1 ) / 10 = − 2.6 \rho(v_1)=(-27+1)/10=-2.6 ρ ( v 1 ) = ( − 27 + 1 ) /10 = − 2.6 和 ρ ( v 2 ) = ( − 243 + 1 ) / 82 ≈ − 2.951 \rho(v_2)=(-243+1)/82\approx-2.951 ρ ( v 2 ) = ( − 243 + 1 ) /82 ≈ − 2.951 ,趨近 − 3 -3 − 3 。
殘差界及其局限
設 A A A 為實對稱矩陣,v v v 為單位向量。對每個實數 ρ \rho ρ ,∥ A v − ρ v ∥ 2 ≥ min i ∣ λ i − ρ ∣ \|Av-\rho v\|_2\ge\min\limits_i|\lambda_i-\rho| ∥ A v − ρ v ∥ 2 ≥ i min ∣ λ i − ρ ∣ 。因此在 ρ = ρ ( v ) \rho=\rho(v) ρ = ρ ( v ) 處範數為 η \eta η 的殘差保證某個 特徵值落在 [ ρ − η , ρ + η ] [\rho-\eta,\rho+\eta] [ ρ − η , ρ + η ] 內。
對 v = ∑ i c i u i v=\sum\limits_i c_i u_i v = i ∑ c i u i ,∑ ∣ c i ∣ 2 = 1 \sum|c_i|^2=1 ∑ ∣ c i ∣ 2 = 1 ,
∥ A v − ρ v ∥ 2 2 = ∑ i ∣ c i ∣ 2 ( λ i − ρ ) 2 ≥ min i ∣ λ i − ρ ∣ 2 ∑ i ∣ c i ∣ 2 = min i ∣ λ i − ρ ∣ 2 . \|Av-\rho v\|_2^2=\sum_i |c_i|^2(\lambda_i-\rho)^2
\ge\min_i|\lambda_i-\rho|^2\sum_i|c_i|^2=\min_i|\lambda_i-\rho|^2. ∥ A v − ρ v ∥ 2 2 = i ∑ ∣ c i ∣ 2 ( λ i − ρ ) 2 ≥ i min ∣ λ i − ρ ∣ 2 i ∑ ∣ c i ∣ 2 = i min ∣ λ i − ρ ∣ 2 . 開方即得不等式。
因此,這個界只說某個 特徵值在 ρ \rho ρ 附近,並沒有說是哪一個。
反例模式
殘差為零不一定表示主導特徵值 斷言:若單位向量的殘差很小,其商就估計最大特徵值。取 A = diag ( 4 , 2 ) A=\operatorname{diag}(4,2) A = diag ( 4 , 2 ) 、v = ( 0 , 1 ) T v=(0,1)^T v = ( 0 , 1 ) T ,商為 ρ = 2 \rho=2 ρ = 2 ,A v − ρ v = ( 0 , 2 ) T − ( 0 , 2 ) T = 0 Av-\rho v=(0,2)^T-(0,2)^T=0 A v − ρ v = ( 0 , 2 ) T − ( 0 , 2 ) T = 0 ,所以殘差恰好為零,但主導特徵值是 4 4 4 。由這個 v v v 起步的冪迭代會停留在 v v v ,因為 a 1 = 0 a_1=0 a 1 = 0 。在精確算術下,零殘差證明了一個特徵對;它並不證明主導性。
在第一個迭代例子的 v 2 v_2 v 2 處,ρ = 66 / 17 ≈ 3.882 \rho=66/17\approx3.882 ρ = 66/17 ≈ 3.882 ,η = 8 / 17 ≈ 0.471 \eta=8/17\approx0.471 η = 8/17 ≈ 0.471 ,所以某個特徵值落在 [ 58 / 17 , 74 / 17 ] ≈ [ 3.41 , 4.35 ] [58/17,74/17]\approx[3.41,4.35] [ 58/17 , 74/17 ] ≈ [ 3.41 , 4.35 ] 內。diag ( 4 , 2 ) \operatorname{diag}(4,2) diag ( 4 , 2 ) 的譜是 { 4 , 2 } \{4,2\} { 4 , 2 } ,只有 4 4 4 在這個區間內。是知道了譜才排除 2 2 2 ;單靠殘差而不知道譜,是排除不了的。
常見錯誤
(對未正規化的向量使用 Rayleigh 商)
對 w = ( 4 , 1 ) T w=(4,1)^T w = ( 4 , 1 ) T (即 17 v 2 \sqrt{17}\,v_2 17 v 2 ),w T A w = 66 w^TAw=66 w T A w = 66 ,離任何特徵值都很遠。正確的商是 w T A w / w T w = 66 / 17 w^TAw/w^Tw=66/17 w T A w / w T w = 66/17 。漏掉除以 w T w w^Tw w T w ,答案便被向量長度的平方放大。
MATLAB 風格的實驗
以下示範假設 A A A 是有限實對稱矩陣,v0 是尺寸相容的非零列向量,maxSteps 是正整數。可重用的程式應驗證這些輸入;這裏使用固定迭代次數,令終止條件明確。
function [v,rho,res,k] = power_demo(A,v0,maxSteps)
v = v0/norm(v0,2);
for k = 1:maxSteps
w = A*v;
scale = norm(w,2);
if scale == 0
error('PowerDemo:ZeroImage','Iteration reached a zero image');
end
v = w/scale;
rho = v'*A*v;
res = norm(A*v-rho*v,2);
end
end
此函數傳回最終向量、商、殘差及已完成的迭代次數。它不會僅因 res 細小便將結果標示為主導。在這個簡單實驗中,正規化有助控制數值增長,但浮點溢位、下溢及捨入誤差仍需小心處理。
小測
快速檢查
(對 A = diag ( 4 , 2 ) A=\operatorname{diag}(4,2) A = diag ( 4 , 2 ) 及 v 0 = ( 1 , 1 ) T / 2 v_0=(1,1)^T/\sqrt2 v 0 = ( 1 , 1 ) T / 2 ,要多少步才能保證 tan θ m ≤ 1 / 100 \tan\theta_m\le1/100 tan θ m ≤ 1/100 ?)
使用 tan θ m ≤ r m tan θ 0 \tan\theta_m\le r^m\tan\theta_0 tan θ m ≤ r m tan θ 0 ,其中 r = 1 / 2 r=1/2 r = 1/2 、tan θ 0 = 1 \tan\theta_0=1 tan θ 0 = 1 。
解答 · 答案 需要 2 − m ≤ 1 / 100 2^{-m}\le1/100 2 − m ≤ 1/100 。因 2 − 6 = 1 / 64 > 1 / 100 2^{-6}=1/64>1/100 2 − 6 = 1/64 > 1/100 而 2 − 7 = 1 / 128 < 1 / 100 2^{-7}=1/128<1/100 2 − 7 = 1/128 < 1/100 ,故 m = 7 m=7 m = 7 步足夠。
快速檢查
(某單位向量的商為 ρ = 3 \rho=3 ρ = 3 ,殘差範數為 0.5 0.5 0.5 。關於特徵值可得甚麼結論?)
解答 · 答案 某個特徵值落在 [ 2.5 , 3.5 ] [2.5,3.5] [ 2.5 , 3.5 ] 內。至於是哪一個,以及是否最大,並無所說。
快速檢查
(若 a 1 = 0 a_1=0 a 1 = 0 ,冪迭代能否趨近 u 1 u_1 u 1 ?)
看看 A m v 0 A^mv_0 A m v 0 中出現哪些特徵向量。
解答 · 答案 不能。此時對每個 m m m ,A m v 0 A^mv_0 A m v 0 都在 u 2 , … , u n u_2,\dots,u_n u 2 , … , u n 的生成空間內,與 u 1 u_1 u 1 正交,不可能趨近它。