特征值求解器返回的数值结果需要加以解读。幂迭代提供了一个简单的例子:反复的矩阵乘法可以揭示主导特征方向,但前提是起始向量本身含有该方向。残差提供了一项有用的独立检验,然而仅凭很小的残差,并不足以识别最大的特征值。
实对称矩阵的迭代
设 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 正交,不可能趋近它。