数值分析第8章——矩阵特征值问题计算.ppt

《数值分析第8章——矩阵特征值问题计算.ppt》由会员分享，可在线阅读，更多相关《数值分析第8章——矩阵特征值问题计算.ppt（121页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 矩阵特征值问题计算矩阵特征值问题计算 对对n 阶方阵阶方阵A求数求数 和非零向量和非零向量x,使其满足使其满足Ax=x 这样的这样的 值称为矩阵值称为矩阵A的特征值，非零向量的特征值，非零向量 x 称为矩阵称为矩阵A的与特征值的与特征值 相对应的一个特征向量。相对应的一个特征向量。1定义定义1 设矩阵设矩阵A,B R n n，若有可逆阵若有可逆阵P，使使 则称则称A与与B相似相似。定理定理1 若矩阵若矩阵A,B R n n且相似且相似，则则（1）A与与B的特征值完全相同的特征值完全相同；（2）若若x是是B的特征向量的特征向量，则则Px便为便为A的特征向量的特征向量。8.1 预备知

2、识预备知识2定理定理2：设设A R n n具有完全的特征向量系，即存在具有完全的特征向量系，即存在n个个线性无关线性无关其中其中 i为为A的特征值的特征值，P的各列为相应于的各列为相应于 i的特征向量的特征向量。的特征向量构成的特征向量构成Rn的一组基底的一组基底，则经相似变换可化则经相似变换可化A为为对角阵，即有可逆阵对角阵，即有可逆阵P，使使3定理定理3 ：A R n n，1,n为为A的特征值的特征值，则则（2）A的行列式值等于全体特征值之积，即的行列式值等于全体特征值之积，即（1）A的迹数等于特征值之和，即的迹数等于特征值之和，即4定理定理45定理定理5 设设A R n n为对称矩阵为对

3、称矩阵，其特征值其特征值 1 2 n，则则（1）对任意对任意A R n，x0，（2）（3）6定理定理6（Gerschgorin圆盘定理圆盘定理）设设A R n n，则则表示以表示以aii为中心为中心，以以 半径为的复平面上的半径为的复平面上的n个圆盘个圆盘。（2）如果矩阵如果矩阵A的的m个圆盘组成的并集个圆盘组成的并集S（连通的连通的）与其余与其余（1）A的每一个特征值必属于下述某个圆盘之中的每一个特征值必属于下述某个圆盘之中，n m个圆盘不连接个圆盘不连接，则则S内恰包含内恰包含m个个A的特征值的特征值。789101112定理定理71314一一 幂法幂法1 基本思想基本思想任取非零向量任取非

4、零向量 v0 ,则可则可唯一表示为唯一表示为 设设n 阶矩阵阶矩阵A 的特征值的特征值 ,满足满足 ,且其对应有且其对应有n个线性无关的特个线性无关的特 征向量征向量 x1,x2,xn，即，即 8.2 幂法和反幂法幂法和反幂法15则则16其中其中由假设条件由假设条件 所以当所以当k充分大时，有充分大时，有从而从而 所以所以17即为矩阵即为矩阵 A 的对应特征值的对应特征值 1 的近似特征向量。的近似特征向量。用用(vk)i 表示表示 vk 的第的第 i 个分量个分量,则当则当k充分大时充分大时,有有即为主特征值的近似值。即为主特征值的近似值。且且18设设有有主特征主特征值值满满足足个线性无关的

5、特征向量，个线性无关的特征向量，则对则对任意非零初始向量任意非零初始向量，下面的式子成立，下面的式子成立定理定理19 迭代公式迭代公式(1)实质上是由矩阵实质上是由矩阵A的乘幂的乘幂 Ak与非零向与非零向量量 v0 相乘来构造向量序列相乘来构造向量序列 xk ,从而计算主特征值从而计算主特征值及其对应的主特征向量及其对应的主特征向量,故称这种方法为幂法。故称这种方法为幂法。20设设有有主特征主特征值值满满足足个线性无关的特征向量，个线性无关的特征向量，则对则对任意非零初始向量任意非零初始向量定理定理按照下述方法构造的向量序列按照下述方法构造的向量序列则有则有21 2.幂法实用计算公式幂法实用计

6、算公式22例例1 求矩阵求矩阵的主特征值与其对应的特征向量。的主特征值与其对应的特征向量。解取解取 v0=(0,0,1)T ,则则23直到直到k=8 时的计算结果见下表时的计算结果见下表0.5,1,0.750011.00005.5000,11.0000,8.250080.5,1,0.750011.00055.5002,11.0005,8.250170.5,1,0.750110.99745.4987,10.9974,8.249460.5,1,0.749411.01425.5075,11.0142,8.257650.5,1,0.753610.92235.4621,10.9223,8.230640.

7、5,1,0.736011.44445.7222,11.4444,8.36130.5,1,0.861194.5,9,7.7520.5,1,0.25 4 2,4,1,1k从而从而24二、幂法的加速二、幂法的加速1、原点平移法、原点平移法 如果如果 是矩阵是矩阵 A 的特征值的特征值,则对任意的实数则对任意的实数p,矩阵矩阵 A-pE 的特征值为的特征值为 -p,且且 A 与与 A-pE 的特征向量相同的特征向量相同.据此据此,如果要计算如果要计算 A 的主特征值的主特征值 1,只要选择合适的只要选择合适的数数 p,使使 1-p 为矩阵为矩阵 A-pE 的主特征值的主特征值,且且 那么那么,对矩阵对

8、矩阵 A-pE 应用幂法求其主特征值应用幂法求其主特征值 1-p,收敛收敛速度将会加快速度将会加快.这种通过求这种通过求 A-pE 的主特征值和特征向的主特征值和特征向量量,进而得到进而得到A的主特征值和特征向量的方法叫的主特征值和特征向量的方法叫原点平原点平移法。移法。25且使且使显然显然,当当 2-p=-(n-p),即即 P=(2+n)2 时时,上式取上式取最小值最小值;如果希望计算如果希望计算 n,类似的讨论可知应选取类似的讨论可知应选取 p=(1+n-1)2 。则对任意实数则对任意实数p,矩阵矩阵 A-pE 的主特征值为的主特征值为 1-p或或 n-p,要求要求 1,则选则选 p 使使

9、26例例2 用原点平移加速法求例用原点平移加速法求例1中矩阵中矩阵A的主特征值与其的主特征值与其对应的特征向量。对应的特征向量。解解 取取p=-2.5,做平移变换做平移变换B=A-pE，则则对对B应用幂法，仍应用幂法，仍取取 x0=(0,0,1)T ,则则27迭代迭代5步的计算结果见下表步的计算结果见下表0.5,1,0.750013.50006.7500,13.5000,10.125050.5,1,0.750013.50076.7503,13.5007,10.125640.5,1,0.750713.51796.76,13.5179,10.140630.5,1,0.7545147,14,10.5

10、62520.5,1,0.8754 2,4,3.51k可得到可得到B的主特征值的主特征值 1 13.5000 特征向量特征向量 v1 (0.5,1.0,0.7500)T 因此因此,A的主特征值为的主特征值为 1=1+p 11.0000,特征向量仍为特征向量仍为v1=(0.5,1,0.7500)T。282930设设A为为n阶实对称矩阵，称阶实对称矩阵，称为为向量向量 x 的瑞利商的瑞利商，其中，其中(x,x)=xT x 为内积。不难为内积。不难证明，对实对称矩阵证明，对实对称矩阵A，如果其特征值满足，如果其特征值满足2、瑞利商加速、瑞利商加速由幂法公式生成的由幂法公式生成的 xk 的瑞利商满足的瑞

11、利商满足由此可见，由此可见，R(xk)比比 mk 更快的收敛于更快的收敛于 1。31幂法的瑞利商加速迭代公式为幂法的瑞利商加速迭代公式为其中其中A为为n阶实对称矩阵。阶实对称矩阵。对给定的误差限对给定的误差限 ，当，当|mk mk-1|时，取时，取32三、反幂法三、反幂法 反幂法是用于求非奇异矩阵反幂法是用于求非奇异矩阵A的按模最小的特征值的按模最小的特征值和对应特征向量的方法和对应特征向量的方法.而结合原点平移法的反幂法而结合原点平移法的反幂法则可以求矩阵则可以求矩阵A的任何一个具有先验了解的特征值和对的任何一个具有先验了解的特征值和对应的特征向量。应的特征向量。设矩阵设矩阵A非奇异非奇异,

12、其特征值其特征值 i (i=1,2,n),满足满足其相应的特征向量其相应的特征向量 x1,x2,xn 线性无关线性无关,则则 A-1 的特的特征值为征值为1/i，对应的特征向量仍为，对应的特征向量仍为 xi (i=1,2,n).33此时此时,A-1 的特征值满足的特征值满足因此因此,对对 A-1 应用幂法应用幂法,可求出其主特征值可求出其主特征值 1/n 和特征向量和特征向量 xn uk,从而求得从而求得A的按模最小特征值的按模最小特征值 n 1/和对应的特征向量和对应的特征向量 xn uk，这种方法称为这种方法称为反幂法反幂法。34为了避免求为了避免求 A-1,可通过解线性方程组可通过解线性

13、方程组A vk=uk-1 得到得到yk，采用，采用LU分解分解,即先对即先对 A 进行进行LU分解分解 A=LU,此时反幂此时反幂法的迭代公式为法的迭代公式为35对给定的误差对给定的误差 ，当，当|j 时时,故故 设方阵设方阵X 的的QR 的分解式为的分解式为由由 48由由 知知,对充分大的对充分大的 k,非奇异非奇异,它应有唯一的它应有唯一的 QR 分解式分解式 ,并且并且 于是于是但上三角阵但上三角阵 的对角线元素不一定大于零的对角线元素不一定大于零.为此为此,引入对角阵引入对角阵以便保证以便保证 的对交线元素都是正数的对交线元素都是正数49从而得到从而得到 的的QR 分解式分解式由由 的

14、的 QR 分解式的唯一性得到分解式的唯一性得到 从而从而 由于由于 所以所以50从而从而 其中其中 于是于是因为因为 为上三角阵为上三角阵,为对角阵为对角阵,且元素为且元素为1 或或-1,所以所以51 的极限不一定存在的极限不一定存在52例例 1 用用 QR 算法求矩阵算法求矩阵 特征值特征值.A的特征值为的特征值为-1,4,1+2i.53解解 令令 用施密特正交化过程将用施密特正交化过程将 分解为分解为54将将 与与 逆序相乘逆序相乘,求出求出用用 代替代替A 重复上面过程重复上面过程,计算计算11次得次得55由由 不难看出不难看出,矩阵矩阵A 的一个特征值是的一个特征值是4,另一个特另一个

15、特 征值是征值是-1,其它两个特征值是方程其它两个特征值是方程 的根的根.求得为求得为 56上上Hessenberg化化57585960616263用正交变换化对称矩阵为对称三对角阵用正交变换化对称矩阵为对称三对角阵64带原点位移的带原点位移的QR算法算法6566用单步用单步QR方法计算上方法计算上Hessenberg特征值特征值6768697071727374757677787980818283848586隐式隐式QR算法算法878889909192定理定理6 设设A为为n阶实对称矩阵，则必存在正交矩阵阶实对称矩阵，则必存在正交矩阵P使得使得其中其中为为A的的n个特征值。个特征值。证证设设A

16、的互不相同的特征值为的互不相同的特征值为它们它们的重数依次为的重数依次为根据性质根据性质1和性质和性质3知，知，恰有恰有个线性无关的实特征向量，个线性无关的实特征向量，对应于特征值对应于特征值93把它们标准正交化，把它们标准正交化，特征向量组，特征向量组，特征向量共有特征向量共有n个，个，并有并有其中其中为为A的的n个特征值。个特征值。个单位正交的个单位正交的就可得到就可得到知，知，由由这样的这样的特征值的特征向量是正交的，特征值的特征向量是正交的，向量两两正交，以它们为列向量构成正交矩阵向量两两正交，以它们为列向量构成正交矩阵P，又由性质又由性质2知，知，A的属于不同的属于不同故这故这n个单

17、位特征个单位特征94由定理由定理6可知，实对称矩阵的对角化问题，实质上可知，实对称矩阵的对角化问题，实质上是求正交矩阵是求正交矩阵P的问题，计算的问题，计算P的步骤如下：的步骤如下：（1）（2）求出齐次线性方求出齐次线性方程组程组的基础解系，的基础解系，进行正交化和单位化，得到进行正交化和单位化，得到A对于对于的一组的一组标准正交的特征向量，标准正交的特征向量，的个数恰好是的个数恰好是作为作为A的特征值的重数；的特征值的重数；求出实对称矩阵求出实对称矩阵A的全部特征值的全部特征值对于各个不同的特征值对于各个不同的特征值对基础解系对基础解系这个向量组所含向量这个向量组所含向量95（3）量构成一组

18、量构成一组的标准正交基的标准正交基（4）则则P为正交矩阵且使得为正交矩阵且使得为对角阵，对角线上的元素为为对角阵，对角线上的元素为相应特征向量的特征值。相应特征向量的特征值。的所有标准正交的特征向的所有标准正交的特征向将将取取96例例13 设实对称矩阵设实对称矩阵求正交阵求正交阵解解得特征值得特征值97987.2 对称对称QR方法方法对称矩阵的三对角化对称矩阵的三对角化99带原点位移的带原点位移的QR迭代迭代100101隐式隐式QR迭代迭代102103定义定义JacobiJacobi方法是用来计算实对称矩阵方法是用来计算实对称矩阵A 的全部的全部特征值及其相应特征向量的一种变换方法特征值及其相

19、应特征向量的一种变换方法.Jacobi方法的基本思想是通过一系列的平面旋转矩方法的基本思想是通过一系列的平面旋转矩阵构成的正交变换将对称矩阵逐步化为对角阵阵构成的正交变换将对称矩阵逐步化为对角阵,从从而得到而得到A的全部特征值及其相应的特征向量的全部特征值及其相应的特征向量.定理定理 (1)(1)如果如果n 阶方阵阶方阵A满足满足 则称则称A为正交阵为正交阵.7.3 Jacobi7.3 Jacobi方法方法104(2)设设A 是是n 阶实对称矩阵阶实对称矩阵,则则A 的特征值都是的特征值都是 实数实数,并且有互相正交的并且有互相正交的n 个特征向量个特征向量.(3)相似矩阵具有相同的特征值相似

20、矩阵具有相同的特征值.(4)设设A 是是n 阶实对称矩阵阶实对称矩阵,P 为为n 阶正交阵阶正交阵,则则 B=PAP 也是对称矩阵也是对称矩阵.(5)n 阶正交矩阵的乘积是正交矩阵。阶正交矩阵的乘积是正交矩阵。(6)(6)设设A 是是n n 阶实对称矩阵阶实对称矩阵,则必有正交矩阵则必有正交矩阵P，使使 105由由(6)可知可知,对于任意的对于任意的 阶实对称矩阵阶实对称矩阵A,只只要能求得一个要能求得一个 正交阵正交阵P,使使 则可得到则可得到A 的全部特征值及其相应的特征向量的全部特征值及其相应的特征向量,这就是雅克这就是雅克比方法的理论基础比方法的理论基础.其中其中 的对角线元素是的对角

21、线元素是A 的的n 个个特征值，正交特征值，正交矩阵矩阵P 的第的第i 列是列是A 的对应于特征值的对应于特征值 的特征的特征向量。向量。下面我们详细介绍雅可比方法。首先引进下面我们详细介绍雅可比方法。首先引进 中中 的平面旋转变换的平面旋转变换.变换变换 106 i j i j记为记为 ,其中其中107X=,Y=,称为称为 平面内的平面旋转矩阵平面内的平面旋转矩阵.容易得到如容易得到如 下下性质性质:则称则称 x=为为 中中 平面内的一个旋转变换平面内的一个旋转变换,(2)的主对角线元素中除第的主对角线元素中除第i 个与第个与第j 个元素个元素为为 外外,其它元素均为其它元素均为1;非对角元

22、素中除第非对角元素中除第i 行第行第 j 列元素为列元素为 ,第第j 行第行第i 列元素为列元素为 外外,其它元素均为零其它元素均为零.(1)为正交矩阵为正交矩阵108(3)只改变只改变A的第的第i行第行第j 行元素行元素,AP只改变只改变A 的的 第第i 列第列第j 列元素列元素,所以所以 只改变只改变A 的第的第i 行行,第第j 行行,第第i 列列,第第j 列元素列元素.设设A=为为n 阶实对称矩阵阶实对称矩阵,为一非对角线元素为一非对角线元素.令令 则则 为实对为实对 称矩阵称矩阵,且且 与与A 有同的特征值有同的特征值.通过直接计算知通过直接计算知 109110当取当取 满足关系式满足

23、关系式 时时,且且由于在正交相似变换下由于在正交相似变换下,矩阵元素的平方和不变矩阵元素的平方和不变,所以若所以若用用D(A)表示矩阵表示矩阵A的对角线元素的平方和的对角线元素的平方和,用用S(A)表示表示A 的非对角元素平方和的非对角元素平方和,则由则由(11)式得式得111 ,的非对角元素平方和的非对角元素平方和A的非对角元素平方的非对角元素平方 且将事先选定的非对角元素消去了且将事先选定的非对角元素消去了 这说明用这说明用 对对A 作正交相似变换化为作正交相似变换化为 后后,的的 对角线元素平方和比对角线元素平方和比A 的对角元素平方和增加了的对角元素平方和增加了 和减少了和减少了112

24、 因此因此,只要我们逐次地用这种变换只要我们逐次地用这种变换,就可以使得就可以使得 矩阵矩阵A 的非对角线元素平方和趋于零的非对角线元素平方和趋于零,也即使得矩也即使得矩阵阵A 逐步化为对角阵逐步化为对角阵.这里需要说明一点这里需要说明一点:并不是对矩阵并不是对矩阵A的每一对非的每一对非对角线非零元素进行一次这样的变换就能得到对对角线非零元素进行一次这样的变换就能得到对角阵角阵.因为在用变换消去因为在用变换消去 的时候的时候,只有第只有第 i 行行,第第 j 行行,第第 i 列列,第第 j 列元素在变化列元素在变化,如果如果 或或 为零为零,经经变换后又往往不是零了变换后又往往不是零了.113

25、 雅克比方法就是逐步对矩阵雅克比方法就是逐步对矩阵A 进行正交相似变进行正交相似变换换,消去非对角线上的非零元素消去非对角线上的非零元素,直到将直到将A的非对角的非对角线元素化为接近与零为止线元素化为接近与零为止,从而求得从而求得A的去全特的去全特征征值值,把逐次的正交相似变换矩阵乘起来把逐次的正交相似变换矩阵乘起来,便是所要便是所要求的特征向量求的特征向量.Jacobi的计算步骤归纳如下的计算步骤归纳如下:第一步第一步 在矩阵在矩阵A 的非对角元素中选取一个非零的非对角元素中选取一个非零 元素元素 .一般来说一般来说,取绝对值最大的非对取绝对值最大的非对 角线元素角线元素.114第二步第二步

26、 由公式由公式 求出求出 ,从而得从而得 平面旋转矩阵平面旋转矩阵第三步第三步 ,的元素由公式的元素由公式(9)计算计算第四步第四步 以以 代替代替A,重复第一重复第一,二二,三步求出三步求出 及及 继续重复这一过程继续重复这一过程,直到直到 的非对交的非对交 线元素全化为充分小线元素全化为充分小(即小于允许误差即小于允许误差)时为止时为止.第五步第五步 的对角化元素为的对角化元素为A的全部特征值的近的全部特征值的近 似值似值,的第的第j 列为对应于特列为对应于特 征值征值 (为为 的对角线上第的对角线上第j 个元素个元素)的特征向量的特征向量.115例例 1 1 用雅克比方法求矩阵用雅克比方

27、法求矩阵 的特征值与特征向量的特征值与特征向量解解 首先首先 i=1,j=2,由于由于 故故 取取 所以所以 116再取再取i=1,=1,j=3,=3,由由 得得所以所以 117继续做下去继续做下去,直到非对角线元素趋于零直到非对角线元素趋于零,进行九次变进行九次变换后换后,得得 的对角线元素就是的对角线元素就是A 的特征值的特征值,即即 118继续做下去继续做下去,直到非对角线元素趋于零直到非对角线元素趋于零,进行九次变进行九次变换后换后,得得 的对角线元素就是的对角线元素就是A 的特征值的特征值,即即 119 用雅可比方法求得的结果都比较高用雅可比方法求得的结果都比较高,特别是求特别是求得

28、的特征向量正交性很好得的特征向量正交性很好,所以雅可比方法是求实所以雅可比方法是求实对称矩阵的全部特征值及其对应特征向量的一个对称矩阵的全部特征值及其对应特征向量的一个较好的方法较好的方法.但由于上面介绍的雅可比方法每次迭代都选取但由于上面介绍的雅可比方法每次迭代都选取绝对值最大的非对角元素作为消去对象绝对值最大的非对角元素作为消去对象,花费很多机花费很多机器时间器时间.另外当矩阵是稀疏矩阵时另外当矩阵是稀疏矩阵时,进行正交相似变进行正交相似变换后并不能保证其稀疏的性质换后并不能保证其稀疏的性质,所以对阶数较高的矩所以对阶数较高的矩阵不一采用这种方法阵不一采用这种方法.120 目前常采用一种过

29、关雅克比方法目前常采用一种过关雅克比方法.这种方法是选这种方法是选取一个单调减小而趋于零的数列取一个单调减小而趋于零的数列 作为极值作为极值,这些极这些极称为称为“关关”,对矩阵的非对角线元素规定一个顺序对矩阵的非对角线元素规定一个顺序(例例如先行后列如先行后列,自左至右的顺序自左至右的顺序).首先对限值首先对限值 按规定的顺序逐个检查矩阵的非按规定的顺序逐个检查矩阵的非对角线元素对角线元素,碰到绝对值小于碰到绝对值小于 的元素就跳过去的元素就跳过去,否否则就作变换将其化为零则就作变换将其化为零.重复上述过程重复上述过程,直到所有的非对角元素的绝对值都直到所有的非对角元素的绝对值都小于小于 为止为止.121