第四讲 非对称特征值问题 幂迭代方法 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