特征值问题的计算方法.pptx

《特征值问题的计算方法.pptx》由会员分享，可在线阅读，更多相关《特征值问题的计算方法.pptx（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、其中称 为 的代数重数（简称重数）；为 的几何重数。设 ，对于矩阵 的特征值 ，如果，则称该特征值 为 的一个半单特征值。若 的所有特征值都是半单的，则称 是非亏损的。是非亏损的等价条件是 有n个线性无关的特征向量第1页/共57页设 ，若存在矩阵 ，使得则称 和 是相似的。相似矩阵有相同的特征值设寻求已知矩阵 的相似矩阵 ，要求：矩阵 的特征值和特征向量容易计算本章QR算法的基本思想：第2页/共57页设 ，有 r个互不相同的特征值 ，其重数分别为 ，则一定存在非奇异矩阵使得（Jordan分解）其中且除了 的排列次序外，是唯一的。称作 的Jordan标准型第3页/共57页设 ，则存在酉矩阵 ，使

2、得：（Schur分解）其中 是上三角矩阵，且适当选择 ，可使 的元素按任意指定的顺序排列。设 ，令（圆盘定理）/*Disc Theorem*/则第4页/共57页设 为对称矩阵，则存在正交矩阵（谱分解定理）/*Spectral Decomposition*/其中 是 的n个特征值。使得设 为对称矩阵，且 的特征值为（极大极小定理）其中 表示 中所有k维子空间的全体。则有第5页/共57页设 为对称矩阵，其特征值分别为（Weyl定理）则有说明：对称矩阵的特征值总是良态的。注意：实际问题中矩阵一般都是由计算或实验得到，本身必然存在误差，不妨假设 第6页/共57页2 幂法与反幂法/*Power Meth

3、od and Reversed Power Method*/幂法是计算一个矩阵的模最大的特征值和对应的特征 向量的一种迭代方法（又称为乘幂法）。一、幂法的基本思想与算法假设 是可对角化的，即 存在如下分解：其中不妨假设对于第7页/共57页说明：当k充分大时,的一个近似特征向量为特征向量可以相差一个倍数第8页/共57页因为向量 中含有未知量 ，实际不能计算但我们关心的仅是 的方向，故作如下处理：令其中 为 的模最大分量第9页/共57页 幂法迭代算法：For k=1,2,3,if输出 和设 和 均收敛，由算法知幂法可以计算矩阵的模最大的特征值和对应的特征向量第10页/共57页解：Step1例1 1

4、：利用幂法求下列矩阵 的模最大的特征值及相应的特征向量.(取初始向量为 )Step2第11页/共57页Step3Step4特征值及相应的特征向量精确值为:第12页/共57页 幂法的收敛性：设 有 p个互不相同的特征值满足：且模最大特征值 是半单的，如果初始向量 在的特征子空间上的投影不为零，则由幂法算法产生的向量序列 收敛到 的一个特征向量 ，且数值序列 收敛到 。特征子空间：第13页/共57页证明：设 有如下Jordan分解：是属于 的Jordan块构成的块上三角矩阵是半单的特征值令将 和 如下分块：第14页/共57页第15页/共57页记 是属于 的一个特征向量第16页/共57页几点说明：定

5、理8.2.1条件不满足时，幂法产生的向量序列 可能有若干个收敛于不同向量的子序列；幂法的收敛速度取决于 的大小；加速方法：适当选取 ，对 应用幂法称之为原点平移法原点平移法不改变矩阵 的特征向量第17页/共57页幂法可以计算第二个模最大特征值 常用的方法：降阶方法（收缩技巧）设已经计算出模最大特征值 及其特征向量 对向量 ，采用复的Household变换计算酉矩阵其中 是n-1阶方阵为 的模最大特征值 第18页/共57页二、反幂法的基本思想与算法反幂法是求一个矩阵的模最小的特征值和对应的特征 向量的一种迭代方法（又称为反迭代法）。设 ，则对 应用幂法就可以求得矩阵 的模最小的特征值和相应的特征

6、向量。不妨假设 的特征值为则 的特征值为第19页/共57页 反幂法算法：For k=1,2,3,if输出 和若 和 均收敛，由幂法知收敛速度取决于 的大小反幂法每次迭代都需要求解方程组第20页/共57页 带位移的反幂法：实际应用中，反幂法主要用于求特征向量。且用某种方法已经得到 的特征值 的近似值对矩阵 采用反幂法迭代格式为：记假设 的特征值满足For k=1,2,3,因为方程组的系数矩阵Doolittle分解化为两个三角方是固定的，通常采用(选主元)程组求解，从而减少工作量。第21页/共57页求解方程组 化为：带位移的反幂法迭代格式：For k=1,2,3,收敛速度取决于 的大小当 时，收敛

7、速度会非常快设矩阵 存在Doolittle分解：第22页/共57页解：例2 2：用带位移的反幂法求矩阵）的近似特征向量。对应特征值 （精确值为其中Step1第23页/共57页反幂法具有一次“迭代性”Step2所求近似特征向量为：第24页/共57页3 Jacobi方法Jacobi法：计算实对称矩阵全部特征值和相应特征向量 基本思想对存在正交矩阵 ，满足记则寻找正交相似变换 ，将矩阵 约化为对角阵即可正交相似变换求法：通过Givens变换来实现第25页/共57页 经典Jacobi方法设令非对角“范数”当 时，趋于一个对角阵先来研究一下矩阵的元素和矩阵 的元素之间的关系。Givens变换记为 ，下面

8、通过Givens变换对矩阵 进行约化，使得第26页/共57页例如取记第27页/共57页选取适当的 ，由Givens变换将矩阵的下三角元素尽可能多的化为零：即非对角“范数”尽可能的小。如果 ，则取否则，令首先由 确定第28页/共57页其次确定旋转平面由F-范数的正交不变性设 经过一次正交相似变换后变为矩阵第29页/共57页注意到旋转平面 的选取方法：经典Jacobi方法的迭代格式：对于经典Jacobi方法产生的矩阵序列 ，存在 的特征值的一个排列 满足证明见教材第30页/共57页 经典Jacobi方法的迭代算法给定矩阵选取最佳旋转平面 ：For k=1,2,3,计算计算直到需比较 个元素第31页

9、/共57页习惯上称 次Jacobi迭代为一次“扫描”循环Jacobi方法每一次Jacobi迭代不是去选择最佳旋转平面，而是直接按照某种预先指定的顺序来“扫描”自然顺序：按照自然顺序的循环Jacobi方法是渐进平方收敛的第32页/共57页4 QR 方 法 基本思想利用正交相似变换将一个给定的矩阵逐步约化为上三角矩阵或拟上三角矩阵的一种迭代方法 QR方法的迭代格式设令对矩阵 进行QR分解再对矩阵 进行QR分解一、QR基本迭代方法QR方法是目前计算矩阵全部特征值的最有效的方法之一；具有收敛快、算法稳定等特点。第33页/共57页一般地有：矩阵序列 中每一个矩阵都与原矩阵 相似QR方法的迭代算法：For

10、 m=1,2,3,直到 近似为上三角阵由迭代格式同时还得到：记代入第34页/共57页等式两端同时右乘记即其中 是 的第一列，是 的相应元素可以看作是对矩阵 用 为初始向量的幂法所得到的向量。QR方法与幂法的关系：第35页/共57页 QR方法的收敛性设 的特征值满足 ，且 的则由QR迭代算法产生的矩阵 的对角线以第i行是 对应于 的左特征向量；若 有 分解，下的元素趋于0，同时对角元素 趋于（QR方法的收敛性质）证明：令则有其中第36页/共57页且当m充分大时，存在唯一QR分解：且当m充分大时（QR分解）记 的QR分解为：第37页/共57页为保证上述QR分解中上三角矩阵的对角元为正，令由QR分解

11、唯一性知：代入趋于上三角阵第38页/共57页实际应用中遇到的多数特征值问题都是关于实矩阵的，所以自然希望设计只涉及实数运算的QR迭代。实QR迭代格式设二、实Schur标准形For k=1,2,3,为正交矩阵为上三角阵（实Schur分解）设，则存在正交矩阵，满足：其中 为实数或具有一对复共轭特征值的2阶方阵第39页/共57页特征值为，其中 为虚单位见文献13矩阵称为 的Schur标准形定理8.4.2说明：只要求得矩阵的Schur标准形，就很容易求得矩阵的全部特征值。缺陷：很难得到第40页/共57页称下述形状的矩阵为上Hessenberg矩阵三、上Hessenberg化第41页/共57页设 ，寻求

12、非奇异矩阵 ，使得 为上Hessenberg 矩阵，然后再对 进行 迭代。基本思想和约化过程：记矩阵下面采用Householde变换寻找Step1 选取Householde变换 ，使得其中令第42页/共57页其中Step2 选取Householde变换 ，使得下面对作 同样的处理，以此类推其中令第43页/共57页令其中记为正交阵第44页/共57页按照前述方法，经过n-2步后，可以得到：其中第45页/共57页记 ，则称分解式 为矩阵 的上Hessenberg分解 上Hessenberg分解算法（8.4.1）For k=1:n-2然后对上Hessenberg矩阵进行QR迭代设第46页/共57页上H

13、essenberg矩阵的QR迭代算法：For m=1,2,3,直到 的次对角元素趋于零注意：此时的QR分解可采用Givens变换来实现；用Givens变换得到的RQ仍然为上Hessenberg矩阵；上Hessenberg分解不唯一。若上Hessenberg矩阵的次对角元素均不为零，则称之为不可约的上Hessenberg矩阵。定理8.4.3说明：在不可约的条件下，上Hessenberg分解在相差一个正负号的意义下唯一。见文献6第47页/共57页 实用的QR迭代算法（仅计算特征值）Step1 由算法8.4.1计算上Hessenberg矩阵：Step2（QR分解）For k=1:n-1Step3（计

14、算RQ）Step4 重复步骤Step23，直到下次对角元素趋于零第48页/共57页四、三对角化（对称矩阵的上Hessenberg化）设 为对称矩阵，的上Hessenberg分解为其中 为对称三对角矩阵。Step1 选取Householde变换 ，使得其中令其中第49页/共57页主要工作量在于计算令减少运算量第50页/共57页 三对角分解算法（8.4.2）For k=1:n-2第51页/共57页五、隐式对称的QR迭代方法（仅适用于对称矩阵）带原点位移的QR迭代格式：假设已经对矩阵 完成三对角分解，得到三对角矩阵为了加速收敛，下面选取适当的位移进行QR迭代。迭代过程中产生的矩阵序列 均为三对角矩阵的选取方法：著名的Wilkinson位移一种简单的取法-第52页/共57页记矩阵令取的含义：是取上述矩阵两个特征值中靠近 的那个特征值收敛性见文献4第53页/共57页 隐式对称QR迭代的实现方法设一次对称QR迭代的格式为左式说明：每一次对称QR迭代相当于对矩阵 作正交相似变换例如：n=4时第54页/共57页 Wilkinson位移隐式对称分解迭代算法（8.4.3）首先利用三对角分解算法（8.4.2）计算三对角矩阵第55页/共57页For k=1:n-1其中IfEndEnd终止法则：的下三角元素均趋于零注：此算法仅给出了1次的迭代过程.第56页/共57页感谢您的观看！第57页/共57页