演示文稿第八章特征值问题的计算方法

演示文稿第八章特征值问题的计算方法现在是1页\一共有56页\编辑于星期三第八章特征值问题的计算方法ppt课件现在是2页\一共有56页\编辑于星期三其中称为的代数重数（简称重数）；为的几何重数。设，对于矩阵的特征值，如果，则称该特征值为的一个半单特征值。若的所有特征值都是半单的，则称是非亏损的。是非亏损的等价条件是有n个线性无关的特征向量现在是3页\一共有56页\编辑于星期三设，若存在矩阵，使得则称和是相似的。相似矩阵有相同的特征值设寻求已知矩阵的相似矩阵，要求：矩阵的特征值和特征向量容易计算本章QR算法的基本思想：现在是4页\一共有56页\编辑于星期三设，有r个互不相同的特征值，其重数分别为，则一定存在非奇异矩阵使得（Jordan分解）其中且除了的排列次序外，是唯一的。称作的Jordan标准型现在是5页\一共有56页\编辑于星期三设，则存在酉矩阵，使得：（Schur分解）其中是上三角矩阵，且适当选择，可使的元素按任意指定的顺序排列。设，令（圆盘定理）/*DiscTheorem*/则现在是6页\一共有56页\编辑于星期三设为对称矩阵，则存在正交矩阵（谱分解定理）/*SpectralDecomposition*/其中是的n个特征值。使得设为对称矩阵，且的特征值为（极大极小定理）其中表示中所有k维子空间的全体。则有现在是7页\一共有56页\编辑于星期三设为对称矩阵，其特征值分别为（Weyl定理）则有说明：对称矩阵的特征值总是良态的。注意：实际问题中矩阵一般都是由计算或实验得到，本身必然存在误差，不妨假设现在是8页\一共有56页\编辑于星期三§2幂法与反幂法/*PowerMethod

andReversed

PowerMethod*/幂法是计算一个矩阵的模最大的特征值和对应的特征向量的一种迭代方法（又称为乘幂法）。一、幂法的基本思想与算法假设是可对角化的，即存在如下分解：其中不妨假设对于现在是9页\一共有56页\编辑于星期三说明：当k充分大时,的一个近似特征向量为特征向量可以相差一个倍数现在是10页\一共有56页\编辑于星期三因为向量中含有未知量，实际不能计算但我们关心的仅是的方向，故作如下处理：令其中为的模最大分量现在是11页\一共有56页\编辑于星期三幂法迭代算法：Fork=1,2,3,…if输出和设和均收敛，由算法知幂法可以计算矩阵的模最大的特征值和对应的特征向量现在是12页\一共有56页\编辑于星期三解：Step1例1：利用幂法求下列矩阵的模最大的特征值及相应的特征向量.(取初始向量为)Step2现在是13页\一共有56页\编辑于星期三Step3Step4特征值及相应的特征向量精确值为:现在是14页\一共有56页\编辑于星期三幂法的收敛性：设有p个互不相同的特征值满足：且模最大特征值是半单的，如果初始向量在的特征子空间上的投影不为零，则由幂法算法产生的向量序列收敛到的一个特征向量，且数值序列收敛到。特征子空间：现在是15页\一共有56页\编辑于星期三证明：设有如下Jordan分解：是属于的Jordan块构成的块上三角矩阵是半单的特征值令将和如下分块：现在是16页\一共有56页\编辑于星期三现在是17页\一共有56页\编辑于星期三记

是属于的一个特征向量现在是18页\一共有56页\编辑于星期三几点说明：定理8.2.1条件不满足时，幂法产生的向量序列可能有若干个收敛于不同向量的子序列；幂法的收敛速度取决于的大小；加速方法：适当选取，对应用幂法称之为原点平移法原点平移法不改变矩阵的特征向量现在是19页\一共有56页\编辑于星期三幂法可以计算第二个模最大特征值常用的方法：降阶方法（收缩技巧）设已经计算出模最大特征值及其特征向量对向量，采用复的Household变换计算酉矩阵其中是n-1阶方阵为的模最大特征值现在是20页\一共有56页\编辑于星期三二、反幂法的基本思想与算法反幂法是求一个矩阵的模最小的特征值和对应的特征向量的一种迭代方法（又称为反迭代法）。设，则对应用幂法就可以求得矩阵的模最小的特征值和相应的特征向量。不妨假设的特征值为则的特征值为现在是21页\一共有56页\编辑于星期三反幂法算法：Fork=1,2,3,…if输出和若和均收敛，由幂法知收敛速度取决于的大小反幂法每次迭代都需要求解方程组现在是22页\一共有56页\编辑于星期三带位移的反幂法：实际应用中，反幂法主要用于求特征向量。且用某种方法已经得到的特征值的近似值对矩阵采用反幂法迭代格式为：记假设的特征值满足Fork=1,2,3,…因为方程组的系数矩阵Doolittle分解化为两个三角方是固定的，通常采用(选主元)程组求解，从而减少工作量。现在是23页\一共有56页\编辑于星期三求解方程组化为：带位移的反幂法迭代格式：

Fork=1,2,3,…收敛速度取决于的大小当时，收敛速度会非常快设矩阵存在Doolittle分解：现在是24页\一共有56页\编辑于星期三解：例2：用带位移的反幂法求矩阵）的近似特征向量。对应特征值（精确值为其中Step1现在是25页\一共有56页\编辑于星期三反幂法具有一次“迭代性”Step2所求近似特征向量为：现在是26页\一共有56页\编辑于星期三§3Jacobi方法Jacobi法：计算实对称矩阵全部特征值和相应特征向量基本思想对存在正交矩阵，满足记则寻找正交相似变换，将矩阵约化为对角阵即可正交相似变换求法：通过Givens变换来实现现在是27页\一共有56页\编辑于星期三经典Jacobi方法设令非对角“范数”当时，趋于一个对角阵先来研究一下矩阵的元素和矩阵的元素之间的关系。Givens变换记为，下面通过Givens变换对矩阵进行约化，使得现在是28页\一共有56页\编辑于星期三例如取记现在是29页\一共有56页\编辑于星期三选取适当的，由Givens变换将矩阵的下三角元素尽可能多的化为零：即非对角“范数”尽可能的小。如果，则取否则，令首先由确定现在是30页\一共有56页\编辑于星期三其次确定旋转平面由F-范数的正交不变性设经过一次正交相似变换后变为矩阵现在是31页\一共有56页\编辑于星期三注意到旋转平面的选取方法：经典Jacobi方法的迭代格式：对于经典Jacobi方法产生的矩阵序列，存在的特征值的一个排列满足证明见教材现在是32页\一共有56页\编辑于星期三经典Jacobi方法的迭代算法给定矩阵选取最佳旋转平面：Fork=1,2,3,…计算计算直到需比较个元素现在是33页\一共有56页\编辑于星期三习惯上称次Jacobi迭代为一次“扫描”循环Jacobi方法每一次Jacobi迭代不是去选择最佳旋转平面，而是直接按照某种预先指定的顺序来“扫描”自然顺序：按照自然顺序的循环Jacobi方法是渐进平方收敛的现在是34页\一共有56页\编辑于星期三§4QR

方法基本思想利用正交相似变换将一个给定的矩阵逐步约化为上三角矩阵或拟上三角矩阵的一种迭代方法QR方法的迭代格式设令对矩阵进行QR分解再对矩阵进行QR分解一、QR基本迭代方法QR方法是目前计算矩阵全部特征值的最有效的方法之一；具有收敛快、算法稳定等特点。现在是35页\一共有56页\编辑于星期三一般地有：矩阵序列中每一个矩阵都与原矩阵相似QR方法的迭代算法：Form=1,2,3,…直到近似为上三角阵由迭代格式同时还得到：记代入现在是36页\一共有56页\编辑于星期三等式两端同时右乘记即其中是的第一列，是的相应元素可以看作是对矩阵用为初始向量的幂法所得到的向量。QR方法与幂法的关系：现在是37页\一共有56页\编辑于星期三QR方法的收敛性设的特征值满足，且的则由QR迭代算法产生的矩阵的对角线以第i行是对应于的左特征向量；若有分解，下的元素趋于0，同时对角元素趋于（QR方法的收敛性质）证明：令则有其中现在是38页\一共有56页\编辑于星期三且当m充分大时，存在唯一QR分解：且当m充分大时（QR分解）记的QR分解为：现在是39页\一共有56页\编辑于星期三为保证上述QR分解中上三角矩阵的对角元为正，令由QR分解唯一性知：代入趋于上三角阵现在是40页\一共有56页\编辑于星期三实际应用中遇到的多数特征值问题都是关于实矩阵的，所以自然希望设计只涉及实数运算的QR迭代。实QR迭代格式设二、实Schur标准形Fork=1,2,3,…为正交矩阵为上三角阵（实Schur分解）设，则存在正交矩阵，满足：其中为实数或具有一对复共轭特征值的2阶方阵现在是41页\一共有56页\编辑于星期三特征值为，其中为虚单位见文献[13]矩阵称为的Schur标准形定理8.4.2说明：只要求得矩阵的Schur标准形，就很容易求得矩阵的全部特征值。缺陷：很难得到现在是42页\一共有56页\编辑于星期三称下述形状的矩阵为上Hessenberg矩阵三、上Hessenberg化现在是43页\一共有56页\编辑于星期三设，寻求非奇异矩阵，使得为上Hessenberg

矩阵，然后再对进行迭代。基本思想和约化过程：记矩阵下面采用Householde变换寻找Step1

选取Householde变换，使得其中令现在是44页\一共有56页\编辑于星期三其中Step2

选取Householde变换，使得下面对作同样的处理，以此类推其中令现在是45页\一共有56页\编辑于星期三令其中记为正交阵现在是46页\一共有56页\编辑于星期三按照前述方法，经过n-2步后，可以得到：其中现在是47页\一共有56页\编辑于星期三记，则称分解式为矩阵的上Hessenberg分解上Hessenberg分解算法（）Fork=1:n-2然后对上Hessenberg矩阵进行QR迭代设现在是48页\一共有56页\编辑于星期三上Hessenberg矩阵的QR迭代算法：Form=1,2,3,…直到的次对角元素趋于零注意：此时的QR分解可采用Givens变换来实现；用Givens变换得到的RQ仍然为上Hessenberg矩阵；上Hessenberg分解不唯一。若上Hessenberg矩阵的次对角元素均不为零，则称之为不可约的上Hessenberg矩阵。定理8.4.3说明：在不可约的条件下，上Hessenberg分解在相差一个正负号的意义下唯一。见文献[6]现在是49页\一共有56页\编辑于星期三实用的QR迭代算法（仅计算特征值）Step1由算法8.4.1计算上Hessenberg矩阵：Step2（QR分解）