特征值问题的计算方法文档资料

《特征值问题的计算方法文档资料》由会员分享，可在线阅读，更多相关《特征值问题的计算方法文档资料（57页珍藏版）》请在金锄头文库上搜索。

1、 第八章第八章 特征值问题的计算方法特征值问题的计算方法 /*Computational Method of Eigenvalue Problem*/本章主要介绍矩阵的本章主要介绍矩阵的特征值特征值和和特征向量特征向量的计算方法。的计算方法。 特征值特征值和和特征向量特征向量的的基本概念与性质基本概念与性质1 基本概念与性质基本概念与性质设设 ，若存在向量，若存在向量 和复数和复数 满足满足，则称，则称 是矩阵是矩阵 的的特征值特征值， 是特征值是特征值相应的相应的特征向量特征向量。特征特征多项式多项式 的根的集合：的根的集合：谱集谱集1其中其中称称 为为 的的代数重数代数重数（简称（简称重数

2、重数）；）；为为 的的几何重数几何重数。设设 ，对于矩阵对于矩阵 的的特征值特征值 ，如果，如果，则称该特征值，则称该特征值 为为 的一个的一个半单半单特征值。特征值。若若 的所有特征值都是的所有特征值都是半单半单的，则称的，则称 是是非亏损非亏损的。的。是是非亏损非亏损的等价条件是的等价条件是 有有n个个线性无关线性无关的特征向量的特征向量2设设 ， 若存在矩阵若存在矩阵 ，使得，使得则称则称 和和 是是相似相似的。的。相似相似矩阵有相同的特征值矩阵有相同的特征值设设寻求已知矩阵寻求已知矩阵 的的相似相似矩阵矩阵 ，要求：，要求：矩阵矩阵 的的特征值特征值和和特征向量特征向量容易计算容易计算

3、本章本章QR算法的算法的基本思想：基本思想：3设设 ，有，有 r个个互不相同互不相同的特征值的特征值 ，其其重数重数分别为分别为 ，则一定存在，则一定存在非奇异非奇异矩阵矩阵使得使得（Jordan分解）分解）其中其中且除了且除了 的的排列排列次序次序外，外， 是是唯一唯一的。的。称作称作 的的Jordan标准型标准型4设设 ，则存在，则存在酉酉矩阵矩阵 ，使得：，使得：（Schur分解）分解）其中其中 是是上三角上三角矩阵，且适当选择矩阵，且适当选择 ，可使，可使 的元素的元素按任意指定的顺序排列。按任意指定的顺序排列。设设 ，令，令（圆盘圆盘定理）定理）/*Disc Theorem*/则则5

4、设设 为为对称对称矩阵，则存在矩阵，则存在正交正交矩阵矩阵（谱谱分解定理）分解定理）/*Spectral Decomposition*/其中其中 是是 的的n个特征值。个特征值。使得使得设设 为为对称对称矩阵，且矩阵，且 的特征值为的特征值为（极大极小极大极小定理）定理）其中其中 表示表示 中所有中所有k维子空间的全体。维子空间的全体。则有则有6设设 为为对称对称矩阵，其特征值分别为矩阵，其特征值分别为（Weyl定理）定理）则有则有说明：说明：对称对称矩阵的特征值总是矩阵的特征值总是良态良态的。的。注意注意：实际问题中矩阵一般都是由：实际问题中矩阵一般都是由计算计算或或实验实验得到，得到，本身

5、必然存在本身必然存在误差误差，不妨假设，不妨假设 72 幂法与幂法与反幂法反幂法/*Power Method and Reversed Power Method*/幂法幂法是计算一个矩阵的是计算一个矩阵的模最大模最大的特征值和对应的特征的特征值和对应的特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为乘幂法乘幂法）。）。 一、一、幂法幂法的的基本思想与算法基本思想与算法假设假设 是可是可对角化对角化的，即的，即 存在如下分解：存在如下分解： 其中其中不妨假设不妨假设对于对于8说明：当说明：当k充分大时充分大时, 的一个的一个近似特征向量近似特征向量为为特征向量可以相差一个特征向量可以相

6、差一个倍数倍数9因为向量因为向量 中含有中含有未知量未知量 ，实际不能计算，实际不能计算但我们关心的仅是但我们关心的仅是 的的方向方向，故作如下处理：，故作如下处理：令令其中其中 为为 的的模最大分量模最大分量10 幂法迭代幂法迭代算法算法：For k=1,2,3,if输出输出 和和设设 和和 均均收敛收敛，由，由算法算法知知幂法幂法可以计算矩阵的可以计算矩阵的模最大模最大的特征值和对应的特征向量的特征值和对应的特征向量11解：解：Step1例例1 1：利用利用幂法幂法求下列矩阵求下列矩阵 的模的模最大的特征值及相应的最大的特征值及相应的特征向量特征向量.(取初始向量为取初始向量为 )Step

7、212Step3Step4特征值及相应的特征值及相应的特征向量特征向量精确值精确值为为:13 幂法幂法的收敛性的收敛性：设设 有有 p个个互不相同互不相同的特征值满足：的特征值满足：且且模最大模最大特征值特征值 是是半单半单的，如果初始向量的，如果初始向量 在在的特征子空间上的的特征子空间上的投影投影不为零，则由不为零，则由幂法幂法算法产生的算法产生的向量向量序列序列 收敛到收敛到 的一个特征向量的一个特征向量 ，且，且数值数值序列序列 收敛到收敛到 。特征特征子空间：子空间：14证明：证明：设设 有如下有如下Jordan分解：分解：是属于是属于 的的Jordan块构成的块上三角矩阵块构成的块

8、上三角矩阵是是半单半单的特征值的特征值令令将将 和和 如下分块：如下分块：1516记记 是属于是属于 的一个特征向量的一个特征向量17几点说明几点说明：定理定理8.2.1条件不满足时，条件不满足时，幂法幂法产生的产生的向量向量序列序列 可能有可能有若干若干个收敛于不同向量的个收敛于不同向量的子序列子序列；幂法幂法的收敛的收敛速度速度取决于取决于 的大小；的大小；加速加速方法：适当选取方法：适当选取 ，对，对 应用应用幂法幂法称之为称之为原点平移法原点平移法原点平移法原点平移法不改变不改变矩阵矩阵 的特征向量的特征向量18 幂法幂法可以计算第二个可以计算第二个模最大模最大特征值特征值 常用常用的

9、方法：的方法：降阶降阶方法（方法（收缩收缩技巧）技巧）设已经计算出设已经计算出模最大模最大特征值特征值 及其特征向量及其特征向量 对向量对向量 ，采用，采用复复的的Household变换计算变换计算酉酉矩阵矩阵其中其中 是是n-1阶方阵阶方阵为为 的的模最大模最大特征值特征值 19二、二、反幂法的反幂法的基本基本思想与算法思想与算法反幂法反幂法是求一个矩阵的是求一个矩阵的模最小模最小的特征值和对应的特征的特征值和对应的特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为反迭代法反迭代法）。）。 设设 ，则，则对对 应用应用幂法幂法就可以求得矩阵就可以求得矩阵 的的模最小模最小的特征值和相

10、应的特征向量。的特征值和相应的特征向量。不妨假设不妨假设 的特征值为的特征值为则则 的特征值为的特征值为20 反反幂法幂法算法算法：For k=1,2,3,if输出输出 和和若若 和和 均均收敛收敛，由，由幂法幂法知知收敛收敛速度速度取决于取决于 的大小的大小反反幂法幂法每次迭代都需要每次迭代都需要求解方程组求解方程组21 带位移的带位移的反反幂法幂法：实际应用中，实际应用中，反反幂法幂法主要用于求主要用于求特征向量特征向量。且用某种方法已经得到且用某种方法已经得到 的特征值的特征值 的的近似值近似值对矩阵对矩阵 采用采用反反幂法幂法迭代格式为：迭代格式为：记记假设假设 的特征值满足的特征值满

11、足For k=1,2,3,因为方程组的系数矩阵因为方程组的系数矩阵Doolittle分解化为两个分解化为两个三角三角方方是是固定固定的，通常采用的，通常采用( (选主元选主元) )程组求解，从而减少工作量。程组求解，从而减少工作量。22求解方程组求解方程组 化为：化为：带位移的带位移的反反幂法幂法迭代格式：迭代格式： For k=1,2,3,收敛收敛速度速度取决于取决于 的大小的大小当当 时，收敛速度会非常快时，收敛速度会非常快设矩阵设矩阵 存在存在Doolittle分解：分解：23解：解：例例2 2：用用带位移的带位移的反反幂法幂法求矩阵求矩阵）的近似特征向量。）的近似特征向量。对应特征值对

12、应特征值 （精确值精确值为为其中其中Step124反反幂法幂法具有一次具有一次“迭代性迭代性”Step2所求所求近似近似特征向量为：特征向量为：253 Jacobi方法方法Jacobi法：计算法：计算实对称实对称矩阵全部特征值和相应特征向量矩阵全部特征值和相应特征向量 基本基本思想思想对对存在存在正交正交矩阵矩阵 ，满足，满足记记则则寻找寻找正交相似正交相似变换变换 ，将矩阵，将矩阵 约化为约化为对角阵对角阵即可即可正交相似正交相似变换求法：通过变换求法：通过Givens变换来实现变换来实现26 经典经典Jacobi方法方法设设令令非对角非对角“范数范数”当当 时，时， 趋于一个趋于一个对角阵

13、对角阵先来研究一下矩阵先来研究一下矩阵的元素和矩阵的元素和矩阵 的的元素元素之间的之间的关系关系。Givens变换记为变换记为 ，下面通过，下面通过Givens变换变换对矩阵对矩阵 进行进行约化约化，使得，使得27例如例如取取记记28选取适当的选取适当的 ，由，由Givens变换将矩阵的变换将矩阵的下三角元素下三角元素尽可能多的化为尽可能多的化为零零：即：即非对角非对角“范数范数”尽可能的尽可能的小小。如果如果 ，则取，则取否则否则，令，令首先首先由由 确定确定29其次其次确定旋转平面确定旋转平面由由F-范数的范数的正交不变性正交不变性设设 经过一次经过一次正交相似正交相似变换后变为矩阵变换后

14、变为矩阵30注意注意到到旋转平面旋转平面 的选取方法：的选取方法：经典经典Jacobi方法的迭代格式：方法的迭代格式：对于经典对于经典Jacobi方法产生的矩阵序列方法产生的矩阵序列 ，存在存在 的特征值的一个排列的特征值的一个排列 满足满足证明见教材证明见教材31 经典经典Jacobi方法的迭代算法方法的迭代算法给定矩阵给定矩阵选取选取最佳旋转平面最佳旋转平面 ：For k=1,2,3,计算计算计算计算直到直到需比较需比较 个元素个元素32习惯上称习惯上称 次次Jacobi迭代为一次迭代为一次“扫描扫描” 循环循环Jacobi方法方法每一次每一次Jacobi迭代不是去选择迭代不是去选择最佳旋

15、转平面最佳旋转平面，而是而是直接按照某种直接按照某种预先指定预先指定的顺序来的顺序来“扫描扫描”自然自然顺序：顺序：按照按照自然自然顺序的循环顺序的循环Jacobi方法是方法是渐进平方渐进平方收敛的收敛的334 QR 方方 法法 基本基本思想思想利用利用正交相似正交相似变换将一个给定的矩阵逐步约化变换将一个给定的矩阵逐步约化为为上三角上三角矩阵或矩阵或拟上三角拟上三角矩阵的一种矩阵的一种迭代迭代方法方法 QR方法的方法的迭代迭代格式格式设设令令对矩阵对矩阵 进行进行QR分解分解再对矩阵再对矩阵 进行进行QR分解分解一、一、QR基本迭代基本迭代方法方法QR方法是目前计算矩阵方法是目前计算矩阵全部

16、全部特征值的特征值的最最有效有效的方的方法之一；具有法之一；具有收敛快收敛快、算法、算法稳定稳定等特点。等特点。34一般地有：一般地有：矩阵序列矩阵序列 中每一个矩阵都与原矩阵中每一个矩阵都与原矩阵 相似相似QR方法的迭代算法：方法的迭代算法：For m=1,2,3,直到直到 近似近似为为上三角上三角阵阵由由迭代格式迭代格式同时还得到：同时还得到：记记代入代入35等式两端同时右乘等式两端同时右乘记记即即其中其中 是是 的的第一列第一列， 是是 的相应元素的相应元素可以看作是对矩阵可以看作是对矩阵 用用 为为初始向量的初始向量的幂法幂法所得到的向量。所得到的向量。QR方法与方法与幂法幂法的关系：

17、的关系：36 QR方法的方法的收敛收敛性性设设 的特征值满足的特征值满足 ，且，且 的的则由则由QR迭代算法产生的矩阵迭代算法产生的矩阵 的对角线以的对角线以第第i行是行是 对应于对应于 的的左特征左特征向量；若向量；若 有有 分解，分解，下的元素趋于下的元素趋于0，同时对角元素，同时对角元素 趋于趋于（QR方法的方法的收敛收敛性质）性质）证明：证明：令令则有则有其中其中37且且当当m充分大时，充分大时， 存在唯一存在唯一QR分解：分解：且且当当m充分大时充分大时（QR分解）分解）记记 的的QR分解为：分解为：38为保证上述为保证上述QR分解中上三角矩阵的对角元为分解中上三角矩阵的对角元为正正

18、，令，令由由QR分解唯一性知：分解唯一性知：代入代入趋于趋于上三角上三角阵阵39实际应用中遇到的多数特征值问题都是关于实际应用中遇到的多数特征值问题都是关于实矩阵实矩阵的，所以自然希望设计只涉及实数运算的的，所以自然希望设计只涉及实数运算的QR迭代。迭代。 实实QR迭代迭代格式格式设设二、实二、实Schur标准形标准形For k=1,2,3,为为正交正交矩阵矩阵为为上三角上三角阵阵（实（实Schur分解）分解）设设，则存在，则存在正交正交矩阵矩阵，满足：，满足：其中其中 为为实数实数或具有或具有一对复共轭一对复共轭特征值的特征值的2阶方阵阶方阵40特征值为特征值为，其中，其中 为为虚单位虚单位

19、见文献见文献13矩阵矩阵称为称为 的的Schur标准形标准形定理定理8.4.2说明：只要求得矩阵的说明：只要求得矩阵的Schur标准形，标准形，就很容易求得矩阵的就很容易求得矩阵的全部全部特征值。特征值。缺陷缺陷： 很难得到很难得到41称下述形状的矩阵为称下述形状的矩阵为上上Hessenberg矩阵矩阵三、上三、上Hessenberg化化42设设 ， 寻求非奇异矩阵寻求非奇异矩阵 ，使得，使得 为上为上Hessenberg 矩阵矩阵，然后再对，然后再对 进行进行 迭代。迭代。 基本基本思想思想和和约化约化过程：过程：记矩阵记矩阵下面采用下面采用Householde变换寻找变换寻找Step1 选

20、取选取Householde变换变换 ，使得，使得其中其中令令43其中其中Step2 选取选取Householde变换变换 ，使得，使得下面对作下面对作 同样的处理，以此类推同样的处理，以此类推其中其中令令44令令其中其中记记为为正交正交阵阵45按照前述方法，经过按照前述方法，经过n-2步后，可以得到：步后，可以得到：其中其中46记记 ，则，则称分解式称分解式 为矩阵为矩阵 的上的上Hessenberg分解分解 上上Hessenberg分解分解算法算法（8.4.1）For k=1:n-2然后对上然后对上Hessenberg矩阵进行矩阵进行QR迭代迭代设设47上上Hessenberg矩阵的矩阵的Q

21、R迭代算法：迭代算法：For m=1,2,3,直到直到 的的次对角次对角元素趋于元素趋于零零注意注意：此时的此时的QR分解可采分解可采用用Givens变换来实现；变换来实现；用用Givens变换得到的变换得到的RQ仍仍然为上然为上Hessenberg矩阵；矩阵； 上上Hessenberg分解不唯一。分解不唯一。若上若上Hessenberg矩阵的次对角元素均不为矩阵的次对角元素均不为零零，则称则称之为之为不可约不可约的上的上Hessenberg矩阵。矩阵。定理定理8.4.3说明：在说明：在不可约不可约的条件下，的条件下，上上Hessenberg分解在相差一个分解在相差一个正负号正负号的意义下的意

22、义下唯一唯一。见文献。见文献648 实用的实用的QR迭代算法（仅计算迭代算法（仅计算特征值特征值）Step1 由算法由算法8.4.1计算计算上上Hessenberg矩阵：矩阵：Step2（QR分解分解） For k=1:n-1Step3（计算（计算RQ）Step4 重复步骤重复步骤Step23，直到，直到下次对角下次对角元素趋于元素趋于零零49四、四、三对角三对角化（化（对称对称矩阵的矩阵的上上Hessenberg化）化）设设 为为对称对称矩阵，矩阵， 的的上上Hessenberg分解为分解为其中其中 为为对称三对角对称三对角矩阵。矩阵。Step1 选取选取Householde变换变换 ，使得

23、，使得其中其中令令其中其中50主要主要工作量工作量在于计算在于计算令令减少减少运算量运算量51 三对角三对角分解分解算法算法（8.4.2）For k=1:n-252五、五、隐式隐式对称对称的的QR迭代方法（仅适用于迭代方法（仅适用于对称对称矩阵）矩阵）带原点带原点位移位移的的QR迭代格式：迭代格式：假设已经对矩阵假设已经对矩阵 完成完成三对角三对角分解，得到三对角矩阵分解，得到三对角矩阵为了为了加速加速收敛，下面选取适当的收敛，下面选取适当的位移位移进行进行QR迭代。迭代。迭代过程中产生的矩阵序列迭代过程中产生的矩阵序列 均为均为三对角三对角矩阵矩阵的选取方法：的选取方法：著名的著名的Wilk

24、inson位移位移一种简单的取法一种简单的取法- -53记矩阵记矩阵令令取取的的含义含义：是取上述矩阵两个：是取上述矩阵两个特征值中靠近特征值中靠近 的那个特征值的那个特征值收敛性见文献收敛性见文献454 隐式隐式对称对称QR迭代的实现方法迭代的实现方法设一次设一次对称对称QR迭代的格式为迭代的格式为左式左式说明：每一次说明：每一次对称对称QR迭代迭代相当于对矩阵相当于对矩阵 作作正交相似正交相似变换变换例如例如：n=4时时55 Wilkinson位移位移隐式隐式对称对称分解迭代算法（分解迭代算法（8.4.3）首先利用首先利用三对角三对角分解分解算法算法（8.4.2）计算）计算三对角三对角矩阵矩阵56For k=1:n-1其中其中IfEndEnd终止法则：终止法则： 的的下三角下三角元素均趋于元素均趋于零零注注：此算：此算法仅给出法仅给出了了1次的次的迭代过程迭代过程.57