PDF《第四讲 非对称特征值问题》

第四讲 非对称特征值问题

1 幂迭代

2 反迭代

3 正交迭代

4 QR 迭代

5 带位移的隐式 QR 迭代

6 特征向量的计算

7 广义特征值问题

8 应用:多项式求根 非对称矩阵特征值/特征向量的计算 基本约定 1: A ∈ Rn*n 、 非对称 、 稠密 基本约定 2: |λ1| ≥ |λ2|λn| ≥

0 本讲主要讨论如何计算 A 的全部特征值和/或特征向量.

主要介绍以下方法: ? 幂迭代方法 ? 反迭代方法(位移策略,Rayleigh 商迭代) ? 正交迭代方法 ? QR 方法 2/78 关于稠密矩阵特征值计算的参考资料有: ? J. H. Wilkinson, The Algebraic Eigenvalue Problem,

1965 ? B. N. Parlett, The Symmetric Eigenvalue Problem, 2nd Eds.,

1998 ? G. W. Stewart, Matrix Algorithms, Vol II: Eigensystems,

2001 ? G. H. Golub and C. F. Van Loan, Matrix Computations,

2013 ? P. Arbenz, The course 252-0504-00 G, Numerical Methods for Solving Large Scale Eigenvalue Problems, 2018. (该课程的主页)

1 幂迭代 幂迭代 是计算特征值和特征向量的一种简单易用的算法. 虽然简单, 但它却建立了计算特征值和特征向量的算法的一个基本框架. 算法 1.1 幂迭代算法 (Power Iteration) 1: Choose an initial guess x(0) with ∥x(0) ∥2 =

1 2: set k =

0 3: while not convergence do 4: y(k+1) = Ax(k) 5: x(k+1) = y(k+1) /∥y(k+1) ∥2 6: ?k+1 = (x(k+1) , Ax(k+1) ) % 内积 7: k = k +

1 8: end while 4/78 幂迭代的收敛性 假设 1: A ∈ Rn*n 可对角化, 即A=VΛV ?1 , 其中 Λ = diag(λ1,λn), V = [v1,vn] ∈ Cn*n , ∥vi∥2 =

1 假设 2: |λ1| >

|λ2| ≥ |λ3|λn|. 由于 V 的列向量组构成 Cn 的一组基, 因此 x(0) 可表示为 x(0) = α1v1 + α2v2 αnvn = V [α1, α2,αn] ? . 我们假定 α1 ?= 0, 即x(0) 不属于 span{v2, v3,vn} (由于 x(0) 是随机选取的, 从概率意义上讲, 这个假设通常是成立的). 5/78 于是我们可得 Ak x(0) = (V ΛV ?1 )k V ? ? ? ? ? ? α1 α2 . . . αn ? ? ? ? ? ? = V Λk ? ? ? ? ? ? α1 α2 . . . αn ? ? ? ? ? ? = V ? ? ? ? ? ? α1λk

1 α2λk

2 . . . αnλk n ? ? ? ? ? ? = α1λk 1V ? ? ? ? ? ? ? ? ? ?

1 α2 α1 ( λ2 λ1 )k . . . αn α1 ( λn λ1 )k ? ? ? ? ? ? ? ? ? ? . 又|λi/λ1| <

1, i = 2, 3,n, 所以 lim k→∞ ( λi λ1 )k = 0, i = 2, 3,n. 6/78 故当 k 趋向于无穷大时, 向量 [ 1, α2 α1 ( λ2 λ1 )k αn α1 ( λn λ1 )k ]? , k = 0, 1, 2, . . . 收敛到 e1 = [1, 0,0]? . 所以向量 x(k) = Ak x(0) /∥Ak x(0) ∥2 收敛到 ±v1, 即λ1 的特征向量. 而?k = (x(k) )? Ax(k) 则收敛到 v? 1Av1 = λ1. ? 幂迭代的收敛快慢取决于 |λ2/λ1| 的大小, |λ2/λ1| 越小, 收敛越快. ? 幂迭代只能用于计算 (模) 最大的特征值和其相应的特征向量. ? 当|λ2/λ1| 接近于

1 时, 收敛速度会非常慢. ? 如果模最大的特征值是一对共轭复数, 则幂迭代可能会失效. 7/78 加速技巧: 位移策略 出发点: 加快幂迭代算法的收敛速度 ?? 尽可能地减小 |λ2/λ1| 位移策略 (shift): 计算 A ? σI 的特征值 我们称 σ 为位移 (shift), 满足 (1) λ1 ? σ 是A?σI 的模最大的特征值;

(2) max 2≤i≤n λi ? σ λ1 ? σ 尽可能地小. 其中第一个条件保证最后所求得的特征值是我们所要的, 第二个条件用 于加快幂迭代的收敛速度. 缺点: (1) σ 很难选取;

(2) 加速效果有限 改进: 与反迭代相结合, 能起到很好的加速效果 8/78

2 反迭代 用幂迭代求 A?1 的模最小特征值, 这就是反迭代 算法 2.1 反迭代算法 (Inverse Iteration) 1: Choose a scalar σ and an initial vector x(0) with ∥x(0) ∥2 =