第八章第八章 特征值问题的计算方法特征值问题的计算方法 /*Computational Method of Eigenvalue Problem*/本章主要介绍矩阵的本章主要介绍矩阵的特征值特征值和和特征向量特征向量的计算方法。的计算方法。 特征值特征值和和特征向量特征向量的的基本概念与性质基本概念与性质1 基本概念与性质基本概念与性质设设 ，若存在向量，若存在向量 和复数和复数 满足满足，则称，则称 是矩阵是矩阵 的的特征值特征值， 是是对应对应的的特征向量特征向量。特征特征多项式多项式 的根的集合：的根的集合：谱集谱集1其中其中称称 为为 的的代数重数代数重数（简称（简称重数重数）；为为 的的几何重数几何重数。设设 ，对于矩阵对于矩阵 的的特征值特征值 ，如果如果，则称该特征值，则称该特征值 为为 的一个的一个半单半单特征值。特征值。若若 的所有特征值都是的所有特征值都是半单半单的，则称的，则称 是是非亏损非亏损的。的。是是非亏损非亏损的等价条件是的等价条件是 有有n个个线性无关线性无关的特征向量的特征向量2设设 ，若存在矩阵若存在矩阵 ，使得，使得则称则称 和和 是是相似相似的。的。相似相似矩阵有相同的特征值矩阵有相同的特征值设设寻求已知矩阵寻求已知矩阵 的的相似相似矩阵矩阵 ，要求：，要求：矩阵矩阵 的的特征值特征值和和特征向量特征向量容易计容易计算算本章本章QR算法的算法的基本思想：基本思想：3设设 ，有，有 r个个互不相同互不相同的特征值的特征值 ，其其重数重数分别为分别为 ，则一定存在，则一定存在非奇异非奇异矩阵矩阵使得使得（Jordan分解）分解）其中其中且除了且除了 的的排列排列次序次序外，外， 是是唯一唯一的。的。称作称作 的的Jordan标准型标准型4设设 ，则存在，则存在酉酉矩阵矩阵 ，使得：，使得：（Schur分解）分解）其中其中 是是上三角上三角矩阵，且适当选择矩阵，且适当选择 ，可使，可使 的元素的元素按任意指定的顺序排列。按任意指定的顺序排列。设设 ，令，令（圆盘圆盘定理）定理）/*Disc Theorem*/则则5设设 为为对称对称矩阵，则存在矩阵，则存在正交正交矩阵矩阵（谱谱分解定理）分解定理）/*Spectral Decomposition*/其中其中 是是 的的n个特征值。个特征值。使得使得设设 为为对称对称矩阵，且矩阵，且 的特征值为的特征值为（极大极小极大极小定理）定理）其中其中 表示表示 中所有中所有k维子空间的全体。维子空间的全体。则有则有6设设 为为对称对称矩阵，其特征值分别为矩阵，其特征值分别为（Weyl定理）定理）则有则有说明：说明：对称对称矩阵的特征值总是矩阵的特征值总是良态良态的。的。注意注意：实际问题中矩阵一般都是由：实际问题中矩阵一般都是由计算计算或或实验实验得到，得到，本身必然存在本身必然存在误差误差，不妨假设，不妨假设 74 QR 方方 法法 基本基本思想思想利用利用正交相似正交相似变换将一个给定的矩阵逐步约化变换将一个给定的矩阵逐步约化为为上三角上三角矩阵或矩阵或拟上三角拟上三角矩阵的一种矩阵的一种迭代迭代方法方法 QR方法的方法的迭代迭代格式格式设设令令对矩阵对矩阵 进行进行QR分解分解再对矩阵再对矩阵 进行进行QR分解分解一、一、QR基本迭代基本迭代方法方法QR方法是目前计算矩阵方法是目前计算矩阵全部全部特征值的特征值的最最有效有效的方的方法之一；具有法之一；具有收敛快收敛快、算法、算法稳定稳定等特点。等特点。8一般地有：一般地有：矩阵序列矩阵序列 中每一个矩阵都与原矩阵中每一个矩阵都与原矩阵 相似相似QR方法的迭代算法：方法的迭代算法：For m=1,2,3,直到直到 近似近似为为上三角上三角阵阵由由迭代格式迭代格式同时还得到：同时还得到：记记代入代入9等式两端同时右乘等式两端同时右乘记记即即10 QR方法的方法的收敛收敛性性设设 的特征值满足的特征值满足 ，且，且 的的则由则由QR迭代算法产生的矩阵迭代算法产生的矩阵 的对角线以的对角线以第第i行是行是 对应于对应于 的的左特征左特征向量；若向量；若 有有 分解，分解，下的元素趋于下的元素趋于0，同时对角元素，同时对角元素 趋于趋于（QR方法的方法的收敛收敛性质）性质）11实际应用中遇到的多数特征值问题都是关于实际应用中遇到的多数特征值问题都是关于实矩阵实矩阵的，所以自然希望设计只涉及实数运算的的，所以自然希望设计只涉及实数运算的QR迭代。迭代。 实实QR迭代迭代格式格式设设二、实二、实Schur标准形标准形For k=1,2,3,为为正交正交矩阵矩阵为为上三角上三角阵阵（实（实Schur分解）分解）设设，则存在，则存在正交正交矩阵矩阵，满足：，满足：其中其中 为为实数实数或具有或具有一对复共轭一对复共轭特征值的特征值的2阶方阵阶方阵12特征值为特征值为，其中，其中 为为虚单位虚单位见文献见文献13矩阵矩阵称为称为 的的Schur标准形标准形定理定理8.4.2说明：只要求得矩阵的说明：只要求得矩阵的Schur标准形，标准形，就很容易求得矩阵的就很容易求得矩阵的全部全部特征值。特征值。缺陷缺陷： 很难得到很难得到13称下述形状的矩阵为称下述形状的矩阵为上上Hessenberg矩阵矩阵三、上三、上Hessenberg化化14设设 ， 寻求非奇异矩阵寻求非奇异矩阵 ，使得，使得 为上为上Hessenberg 矩阵矩阵，然后再对，然后再对 进行进行 迭代。迭代。 基本基本思想思想和和约化约化过程：过程：记矩阵记矩阵下面采用下面采用Householder变换寻找变换寻找Step1 选取选取Householder变换变换 ，使得，使得其中其中令令15其中其中Step2 选取选取Househoulder变换变换 ，使得，使得下面对作下面对作 同样的处理，以此类推同样的处理，以此类推其中其中令令16令令其中其中记记为为正交正交阵阵17按照前述方法，经过按照前述方法，经过n-2步后，可以得到：步后，可以得到：其中其中18记记 ，则，则称分解式称分解式 为矩阵为矩阵 的上的上Hessenberg分解分解 上上Hessenberg分解分解算法算法（8.4.1）For k=1:n-2然后对上然后对上Hessenberg矩阵进行矩阵进行QR迭代迭代设设19上上Hessenberg矩阵的矩阵的QR迭代算法：迭代算法：For m=1,2,3,直到直到 的的次对角次对角元素趋于元素趋于零零注意注意：此时的此时的QR分解可采分解可采用用Givens变换来实现；变换来实现；用用Givens变换得到的变换得到的RQ仍仍然为上然为上Hessenberg矩阵；矩阵； 上上Hessenberg分解不唯一。分解不唯一。若上若上Hessenberg矩阵的次对角元素均不为矩阵的次对角元素均不为零零，则称则称之为之为不可约不可约的上的上Hessenberg矩阵。矩阵。定理定理8.4.3说明：在说明：在不可约不可约的条件下，的条件下，上上Hessenberg分解在相差一个分解在相差一个正负号正负号的意义下的意义下唯一唯一。见文献。见文献620 实用的实用的QR迭代算法（仅计算迭代算法（仅计算特征值特征值）Step1 由算法由算法8.4.1计算计算上上Hessenberg矩阵：矩阵：Step2（QR分解分解） For k=1:n-1Step3（计算（计算RQ）Step4 重复步骤重复步骤Step23，直到，直到下次对角下次对角元素趋于元素趋于零零21四、四、三对角三对角化（化（对称对称矩阵的矩阵的上上Hessenberg化）化）设设 为为对称对称矩阵，矩阵， 的的上上Hessenberg分解为分解为其中其中 为为对称三对角对称三对角矩阵。矩阵。Step1 选取选取Householder变换变换 ，使得，使得其中其中令令其中其中22主要主要工作量工作量在于计算在于计算令令减少减少运算量运算量23 三对角三对角分解分解算法算法（8.4.2）For k=1:n-224