第四讲 非对称特征值问题 幂迭代方法 2 反迭代方法 3 QR迭代方法 4 带位移的隐式QR迭代 应用：多项式求根* 现代数位分析（数值线性代数），潘建瑜 http://math.ecnu.edu.cn/~jypan
第四讲 非对称特征值问题 1 幂迭代方法 2 反迭代方法 3 QR 迭代方法 4 带位移的隐式 QR 迭代 5 应用：多项式求根 ∗ 现代数值分析（数值线性代数）, 潘建瑜 http://math.ecnu.edu.cn/~jypan
非对称矩阵特征值/特征向量计算 基本约定l:A∈Rnxn、 非对称、 稠密 基本约定2： |A≥A2≥…≥A 本讲主要讨论如何计算A的全部特征值和/或特征向量 主要介绍以下方法 ·幂迭代方法 ·反迭代方法（位移策略，Rayleigh商迭代） ·QR迭代方法（带位移的隐式QR迭代）
非对称矩阵特征值/特征向量计算 基本约定 1： A ∈ R n×n 、 非对称 、 稠密 基本约定 2： |λ1| ≥ |λ2| ≥ · · · ≥ |λn| 本讲主要讨论如何计算 A 的全部特征值和/或特征向量 主要介绍以下方法 • 幂迭代方法 • 反迭代方法（位移策略，Rayleigh 商迭代） • QR 迭代方法（带位移的隐式 QR 迭代）
秦 关于稠密矩阵特征值计算的参考资料 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.E.Van Loan,Matrix Computations,2013 .Z.Bai,J.Demmel,J.Dongarra,A.Ruhe,and H.van der Vorst,2000 Templates for the Solution of Algebraic Eigenvalue Problems:A Practical Guide P.Arbenz,The course 252-0504-00 G, Numerical Methods for Solving Large Scale Eigenvalue Problems,2018. (该课程的主页，有电子讲义) http://math.ecnu.edu.cn/~jypan 3/67
关于稠密矩阵特征值计算的参考资料 • 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 • Z. Bai, J. Demmel, J. Dongarra, A. Ruhe, and H. van der Vorst, 2000 Templates for the Solution of Algebraic Eigenvalue Problems: A Practical Guide • P. Arbenz, The course 252050400 G, Numerical Methods for Solving Large Scale Eigenvalue Problems, 2018. （该课程的主页, 有电子讲义） http://math.ecnu.edu.cn/~jypan 3/67
秦 1 幂迭代方法 幂迭代是计算特征值和特征向量的一种简单易用的算法， 虽然简单，但它却建立了计算特征值和特征向量的一个基本框架 算法l.l暴迭代算法(Power Iteration) 1:Choose an initial guess (0)with(02=1 2:set=0 3:while not convergence do 4: y(k+1)=Ar(k) 5: xk+)=yk+1)/八川yk+1)I2 6: k+1=(ak+),Axk+1) %内积 7: k=k+1 8:end while http://math.ecnu.edu.cn/~jypan 4/67
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 http://math.ecnu.edu.cn/~jypan 4/67
秦 幂迭代的收敛性 假设1：A∈Rnxn可对角化，即A=VAV-1,其中 A=diag(1,…,An,V=[1,…,nl∈Cnxm,l2=1 假设2：|A>|2≥入g≥…≥入n. http://math.ecnu.edu.cn/~jypan 5/67
幂迭代的收敛性 假设 1: A ∈ R n×n 可对角化, 即 A = V ΛV −1 , 其中 Λ = diag(λ1, . . . , λn), V = [v1, . . . , vn] ∈ C n×n , ∥vi∥2 = 1 假设 2: |λ1| > |λ2| ≥ |λ3| ≥ · · · ≥ |λn|. http://math.ecnu.edu.cn/~jypan 5/67
由于V的列向量组构成C”的一组基，因此xo)可表示为 秦 x(0)=aiv+a2v2+...+anvn V[a1;02....,an]. 我们假定a1≠0，即x(o不属于span{v2,3,·,n} (由于xO)是随机选取的，从概率意义上讲，这个假设通常是成立的). 于是我们可得 1 a1X57 是 Ak(0)=(VAV-1)%V a2均 =VAk =V =a1λV ... Lan anxh ) http://math.ecnu.edu.cn/~jypan 6/67
由于 V 的列向量组构成 C n 的一组基, 因此 x (0) 可表示为 x (0) = α1v1 + α2v2 + · · · + αnvn = V [α1, α2, . . . , αn] ⊺ . 我们假定 α1 ̸= 0, 即 x (0) 不属于 span{v2, v3, . . . , vn} (由于 x (0) 是随机选取的, 从概率意义上讲, 这个假设通常是成立的). 于是我们可得 A kx (0) = (V ΛV −1 ) kV α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 http://math.ecnu.edu.cn/~jypan 6/67
又A/入<1，i=2,3,,n,所以 秦 =0 i=2,3,..,n. 故当k趋向于无穷大时，向量 上器(=（会） k=0,1,2, 收敛到e1=[1,0,,0T. 所以向量x=AxO)/川AxO2收敛到士1，即1的特征向量 而：=(x()*Ax()则收敛到AU1=入1 幂迭代的收敛快慢取决于2/入1的大小，2/入1越小收敛越快 http://math.ecnu.edu.cn/~jypan 7167
又 |λi/λ1| < 1, i = 2, 3, . . . , n, 所以 lim k→∞ λi λ1 k = 0, i = 2, 3, . . . , n. 故当 k 趋向于无穷大时, 向量 " 1, α2 α1 λ2 λ1 k , . . . , αn α1 λn λ1 k #⊺ , k = 0, 1, 2, . . . 收敛到 e1 = [1, 0, . . . , 0]⊺ . 所以向量 x (k) = Akx (0)/∥Akx (0)∥2 收敛到 ±v1, 即 λ1 的特征向量. 而 µk = (x (k) ) ∗Ax(k) 则收敛到 v ∗ 1Av1 = λ1. ✍ 幂迭代的收敛快慢取决于 |λ2/λ1| 的大小, |λ2/λ1| 越小收敛越快. http://math.ecnu.edu.cn/~jypan 7/67
秦 幂选代的不足： ·幂迭代只能用于计算（模）最大的特征值和其相应的特征向量 ·当入2/1接近于1时，收敛速度会非常慢. ·如果模最大的特征值是一对共轭复数，则幂迭代可能会失效： http://math.ecnu.edu.cn/~jypan 8/67
幂迭代的不足： • 幂迭代只能用于计算 (模) 最大的特征值和其相应的特征向量. • 当 |λ2/λ1| 接近于 1 时, 收敛速度会非常慢. • 如果模最大的特征值是一对共轭复数, 则幂迭代可能会失效. http://math.ecnu.edu.cn/~jypan 8/67
秦 加速技巧：位移策略 出发点：加快幂迭代算法的收敛速度←→尽可能地减小2/入l 位移策略(shif):计算A-oI的特征值 我们称o为位移(shif),满足 (1)入1-σ是A-σI的模最大的特征值： 入-0 (2) max 尽可能地小 2≤n λ1- 其中第一个条件保证最后所求得的特征值是我们所需要的，第二个条件用于 加快幂迭代的收敛速度. http://math.ecnu.edu.cn/~jypan 9/67
加速技巧: 位移策略 出发点: 加快幂迭代算法的收敛速度 ⇐⇒ 尽可能地减小 |λ2/λ1| 位移策略 (shift): 计算 A − σI 的特征值 我们称 σ 为位移 (shift), 满足 (1) λ1 − σ 是 A − σI 的模最大的特征值; (2) max 2≤i≤n λi − σ λ1 − σ 尽可能地小. 其中第一个条件保证最后所求得的特征值是我们所需要的, 第二个条件用于 加快幂迭代的收敛速度. http://math.ecnu.edu.cn/~jypan 9/67
秦 缺点： (1)σ很难选取： (2)加速效果有限 改进：与反迭代相结合，能起到很好的加速效果 http://math.ecnu.edu.cn/~jypan 10/67
缺点: (1) σ 很难选取; (2) 加速效果有限. 改进: 与反迭代相结合, 能起到很好的加速效果 http://math.ecnu.edu.cn/~jypan 10/67