工程计算7矩阵特征值与特征向量课件.ppt

1、7 求矩阵特征值与特征向量求矩阵特征值与特征向量7.1 幂幂 法与反幂法法与反幂法 7.2 Jacobi方法方法 7.3 QR方法方法 2022-11-1727.1 幂法幂法与反幂法与反幂法在实际问题中，矩阵的按模最大特征根起着重要的作用。例在实际问题中，矩阵的按模最大特征根起着重要的作用。例如矩阵的谱半径即矩阵的按模最大特征根的值，它决定了如矩阵的谱半径即矩阵的按模最大特征根的值，它决定了迭代矩阵是否收敛。迭代矩阵是否收敛。矩阵的最小特征值在工程中有重要意义。矩阵的最小特征值在工程中有重要意义。det()0AIAxxn阶方阵阶方阵A的的n个特征值就是其特征方程个特征值就是其特征方程的非零解。

2、的非零解。的的n个根，个根，A属于特征值属于特征值 的特征向量的特征向量x是线性方程组是线性方程组2022-11-1737.1 幂法幂法与反幂法与反幂法例例1 设矩阵设矩阵 幂法的基本思想是：先任取非零初始向量幂法的基本思想是：先任取非零初始向量x0，然后作迭，然后作迭代序列代序列 xk+1=Axk k=1，2，1221A两个特征值为两个特征值为 1132取初始向量取初始向量 x0=(1，0)T，计算向量序列计算向量序列 xk+1=Axk k=1，2，2022-11-1747.1 幂法幂法与反幂法与反幂法kx1(k)x2(k)012311513024145)1(1)2(1xx6.2)2(1)3

3、(1xx(4)1(3)13.154xx(5)1(4)12.951xx(6)1(5)13.016xx(7)1(6)12.994xxkx1(k)x2(k)45674112136510934012236410942)1(2)2(2xx5.3)2(2)3(2xx(4)2(3)22.857xx(5)2(4)23.05xx(6)2(5)22.983xx(7)2(6)23.005xx2022-11-1757.1 幂法幂法与反幂法与反幂法设矩阵设矩阵A的几个特征值按模的大小排列如下的几个特征值按模的大小排列如下 n21其相应特征向量为其相应特征向量为 12,nu uu任取初始向量任取初始向量(0)(0)(0)

4、012,0Tnxxxx01122nnaaaxuuu10111222nnnaaa xAxuuu1111222kkkkknnnaaa xAxuuu21112211kkknknnaaa xuuu2022-11-1767.1 幂法幂法与反幂法与反幂法分三种情况讨论分三种情况讨论 1.1为实根，且为实根，且|1|2|当当a10，k充分大时，有充分大时，有 111kkaxu111111kkkaxux(1)1()kikixx11kux2.1=2为实根，且为实根，且|2|3|，当当a1，a2 0，k充分大时，有充分大时，有 2022-11-1777.1 幂法幂法与反幂法与反幂法1 11212(1)kkkkaa

5、 xuu11111 11212(1)kkkkaa xuu222221112121(1)kkkkkaa xuux2221kkkxA xx221()0kAI x1(2)21111()1(2)22212(),kikkkikikkkixxxx uxxuxx2022-11-1787.1 幂法幂法与反幂法与反幂法3k充分大时，有充分大时，有1223,uivuiv111222kkkaaxuu111111222kkkaaxuu222111222kkkaaxuu2121122111121121121121221222()()()0kkkkkkkkkaa xxxuu2022-11-1797.1 幂法幂法与反幂法与

6、反幂法令令1212,pq210kkkpqxxx用最小二乘法解用最小二乘法解,求出求出p、q，然后再解一元二次方程，然后再解一元二次方程 20 xpxq得到的两个根便是得到的两个根便是 1,2的近似值。的近似值。再由再由 21212()0k AAx12112()()()()0kkkAIAI xAIxx212110kkkAA xAxx2022-11-17107.1 幂法幂法与反幂法与反幂法综上所述，可得综上所述，可得qPp421221112kkuxxqpp421222211kkuxx 2022-11-17117.1 幂法幂法与反幂法与反幂法可根据迭代向量各分量的变化情况来判定属于哪种情况可根据迭代

7、向量各分量的变化情况来判定属于哪种情况 若迭代向各分量单调变化，且有关系式若迭代向各分量单调变化，且有关系式 xk+1=cxk属于第属于第1种情况种情况 若迭代向量分量变化不单调，但有关系式若迭代向量分量变化不单调，但有关系式xk+2=cxk则属于第则属于第2种情况种情况若迭代向量各分量变化不规则，但有关系式若迭代向量各分量变化不规则，但有关系式 210kkkpqxxx则属于第则属于第3种情况种情况 2022-11-17127.1 幂法幂法与反幂法与反幂法 时，按模最大特征值为正，故计算时，按模最大特征值为正，故计算时时s取取 ()(1)1inkki jjjxa y1,2,in()()kkii

8、kyxm()()()|maxkkkkiipimxxx1,2,k()()1()nkkkiiism yx0(1,1,1)Ty()0pkx()kix()kix()0pkx 时，时，s取取 ()kix2022-11-17137.1 幂法幂法与反幂法与反幂法两端同乘以两端同乘以A，得，得 22233122323kkkkkkkkkxA yA xxAyAxxxx10230kkkAxxxx01230kkkkA xAxxxx2022-11-17147.1 幂法幂法与反幂法与反幂法因为因为 11111kkkkkkAxxxAyAxx前两式两端分别取范数后，代入上式得前两式两端分别取范数后，代入上式得 2111221

9、1121112211kkknnnkkkknnnaaaaaauuuxuuuk1kkmx当当时，时，当当k充分大时，充分大时，mk就是按模最大的特征值就是按模最大的特征值|1|的近似值的近似值 2022-11-17157.1 幂法幂法与反幂法与反幂法另一方面，有另一方面，有 111kkkkkkkkxAyAxyxxxx010kkk A xxxx00000kkkA xA yxA yx110010kkAAyxAxx1110k Ayxx10kkxxx2022-11-17167.1 幂法幂法与反幂法与反幂法 21112211002111211kkknnnkkkkkknnnnaaaaaauuuA xyA xu

10、uu11kk uyu当时，说明归一化向量序列说明归一化向量序列 yk 收敛于按模最大的特征值所对应的收敛于按模最大的特征值所对应的特征向量。因此，当特征向量。因此，当k充分大时，充分大时，yk就是特征向量就是特征向量u1的近的近似值似值2022-11-17177.1 幂法幂法与反幂法与反幂法 能否按此方法求出次大特征值和特征向量能否按此方法求出次大特征值和特征向量限制：设限制：设|1|2|3|,在求出在求出 1，u1条件下条件下2022-11-17187.2 Jacobi方法方法 其中，其中，D 是对角矩阵，其主对角线元素是对角矩阵，其主对角线元素 j(j=1，2，n)是矩阵是矩阵 A 的特征

11、值，而正交矩阵的特征值，而正交矩阵U的第的第j列就是列就是A的属于的属于j的特的特征向量征向量(j=1，2，n)。Jacobi方法是用于计算实对称矩阵的全部特征值及对应方法是用于计算实对称矩阵的全部特征值及对应特征向量的一种变换方法。特征向量的一种变换方法。Jacobi方法的基本思想是，通过方法的基本思想是，通过一组平面旋转变换（正交相似变换）将对称矩阵一组平面旋转变换（正交相似变换）将对称矩阵 A化为对角化为对角矩阵，进而求出其全部特征值。矩阵，进而求出其全部特征值。由代数学知识，对于一个实对称矩阵由代数学知识，对于一个实对称矩阵 A=(aij)n n，一定，一定存在正交矩阵存在正交矩阵 U

12、 UTAU=D 求实对称矩阵求实对称矩阵A的特征值问题等于寻找正交矩阵的特征值问题等于寻找正交矩阵U，使，使 UTAU=D为对角阵为对角阵 2022-11-17197.2 Jacobi方法方法 有实对称矩阵有实对称矩阵A=(aij)nn，它的一对非主对角线元素，它的一对非主对角线元素 apq=aqp(pq)不为零。取不为零。取n n的正交矩阵的正交矩阵 11cos1sin1sincos11pqpUqpq2022-11-17207.2 Jacobi方法方法 Upq是是n维空间中的二维坐标旋转变换矩阵。设维空间中的二维坐标旋转变换矩阵。设xRn，则，则 Upqx相当于将坐标轴相当于将坐标轴 oxp

13、和和 oxq在在 xp、xq所在平面旋转了一个所在平面旋转了一个角度角度，其他坐标轴保持不变，故称，其他坐标轴保持不变，故称Upq为平面旋转矩阵。为平面旋转矩阵。用用 Upq对对A 作正交相似变换，得到作正交相似变换，得到 A1=UTpqAUpq=(a(1)ij)n na(1)pp=appcos2 +aqqsin2 +2apqcos sin a(1)qq=appsin2 +aqqcos2 +2apqcos sin a(1)pi=a(1)ip=apicos +aqisin a(1)qi=a(1)iq=apisin +aqicos a(1)ij=a(1)ji=aija(1)pq=a(1)qp=0.

14、5(aqq app)sin2 +2apqcos2(i，jp，q)2022-11-17217.2 Jacobi方法方法 可见，与矩阵可见，与矩阵A相比，矩阵相比，矩阵A1的第的第p行、第行、第p列和第列和第q行、第行、第q列列的元素发生了变化，其余元素不变。的元素发生了变化，其余元素不变。当取当取 满足关系式满足关系式 cot22ppqqpqaaa可以得到可以得到 a(1)pq=a(1)qp=0，也就是说，用平面旋转变换矩阵，也就是说，用平面旋转变换矩阵Upq对对A进行正交相似变换，可以将进行正交相似变换，可以将A 的两个非主对角线元素的两个非主对角线元素apq和和aqp化为零化为零 2022-

15、11-17227.2 Jacobi方法方法 求实对称矩阵求实对称矩阵A的特征值和特征向量是一个迭代过程，其迭代的特征值和特征向量是一个迭代过程，其迭代步骤如下步骤如下(1)在在A的非主对角线元素中，找出按模最大的元素的非主对角线元素中，找出按模最大的元素apq cot22ppqqpqaaa(2)计算计算并由此求出并由此求出 sin、cos 以及相应的平面旋转矩阵以及相应的平面旋转矩阵Upq(3)计算矩阵计算矩阵 A1的元素的元素a(1)ij(4)若若(1)max|ijija则停止计算，所求特征值为则停止计算，所求特征值为 ia(1)ii，i=1，2，n 否则，令否则，令 A=A1，重复执行上述

16、各步骤，重复执行上述各步骤.2022-11-17237.2 Jacobi方法方法 当条件当条件 满足时，满足时，A1几乎是一个对角矩阵。因此，可取几乎是一个对角矩阵。因此，可取A1的主对角线的主对角线元素作为元素作为A的特征值的近似值，即的特征值的近似值，即 ia(1)ii，i=1，2，n 记第记第 k次迭代所得的平面旋转矩阵为次迭代所得的平面旋转矩阵为Upkqk，设经过，设经过N次迭代，次迭代，上述条件得到满足，那么，经过上述条件得到满足，那么，经过N 次迭代所得的矩阵次迭代所得的矩阵AN为为 记记(1)max|ijija2 21 11 12 2TTTNNNNNp qp qp qp qp q

17、p qAUUUAUUU1 12 2NNp qp qp qUUUU则则U是正交矩阵，并且有是正交矩阵，并且有AN=UTAU U 的第的第j列就是列就是A的属于特征值的属于特征值 ia(1)ii的近似特征向量，并且的近似特征向量，并且所有的特征向量都是单位正交的。所有的特征向量都是单位正交的。2022-11-17247.2 Jacobi方法方法 在旋转变换中可以逐步形成在旋转变换中可以逐步形成U，而不必保存每一次的变换矩，而不必保存每一次的变换矩阵阵Upkqk。记。记 R0=I 令令 Rk=Rk 1Upkqk，k=1，2，N 则则 U=RN.计算矩阵计算矩阵 Rk的元素的元素r(k)ij的公式为的

18、公式为()(1)(1)()(1)(1)()(1)cossinsincos(1,2,)kkkkkkkkkipipiqkkkiqipiqkkkkijijrrrrrrjnjp qrr 且2022-11-17257.2 Jacobi方法方法 用用 Jacobi方法计算方法计算n n矩阵矩阵A的特征值和特征向量的特征值和特征向量,计算量主要计算量主要是乘法的次数，约为是乘法的次数，约为8n次次.关于关于 Jacobi方法的收敛性，有以下的定理方法的收敛性，有以下的定理.定理定理 8.1 设设A=(aij)n n是实对称矩阵，由是实对称矩阵，由 Jacobi方法的第方法的第k次次迭代得到的矩阵记为迭代得到

19、的矩阵记为 Ak=(a(k)ij)n n，又记，又记()2,1()nkkiji jija则有则有 lim0kk2022-11-17267.2 Jacobi方法方法 证证 令令注意到注意到()21()nkkijia()()()1()sin2cos202kkkqqpppqaaa可得可得(1)(1)2()2()2()2()()()2()kkkkkppqqppqqpqaaaaa(1)()(,)kkiiiiaaip q()212()kkkpqa2022-11-17277.2 Jacobi方法方法 实对称矩阵经过正交相似变换后，其元素的平方和不变，即实对称矩阵经过正交相似变换后，其元素的平方和不变，即 故

20、有故有 又因又因 k+1+k+1=k+k()211()2()kkkkkkpqa()()|max|kkpqijijaa故得故得()2(1)()kkpqn na2022-11-17287.2 Jacobi方法方法 从而有从而有 其中，其中，0是矩阵是矩阵A的非主对角线元素平方之和。由于的非主对角线元素平方之和。由于 所以有所以有()21222()1(1)(1)kkkpqkkkan nn n11021(1)kkn n2011(1)n nlim0kk2022-11-17297.2 Jacobi方法方法 为了减少搜索非对角线绝对值最大元素时间为了减少搜索非对角线绝对值最大元素时间,对经典的对经典的Jac

21、obi方法可作进一步改进方法可作进一步改进.1.循环循环Jacobi方法：按方法：按(1,2)，(1,3)，(1,n)，(2,3)，(2,4)，(2,n)，(n-1,n)的顺序的顺序,对每个对每个(i,j)的非零元素的非零元素aij作作Jacobi变换变换,使其零化使其零化,逐次重逐次重复扫描下去复扫描下去,直至直至S(A)|2|n|0，则由基本，则由基本QR方法产生的矩阵序列方法产生的矩阵序列Ak收敛于一个上三角矩阵收敛于一个上三角矩阵(其主对角线以上的元素可以不收其主对角线以上的元素可以不收敛敛)。若。若A是对称矩阵，则序列是对称矩阵，则序列Ak收敛于一个对角矩阵收敛于一个对角矩阵.定理定

22、理 8.3 对于任何对于任何n n 实矩阵实矩阵A，由基本，由基本QR方法产生的矩阵方法产生的矩阵序列序列Ak收敛于分块上三角矩阵（其主对角线子块以上的元收敛于分块上三角矩阵（其主对角线子块以上的元素可以不收敛），并且每个主对角线子块有等模的特征值素可以不收敛），并且每个主对角线子块有等模的特征值.2022-11-17387.3 QR方法方法 要实现一步要实现一步QR 方法的迭代，就需要做一次方法的迭代，就需要做一次QR 分解，再做一分解，再做一次矩阵相乘，当次矩阵相乘，当A是一般矩阵时，计算量是很大的。是一般矩阵时，计算量是很大的。为了减少计算量，在实际计算时，总是先将原矩阵为了减少计算量，

23、在实际计算时，总是先将原矩阵A经过相似经过相似变换，化为上变换，化为上Hessenberg矩阵矩阵A1=(a(1)ij)n n，其中，当其中，当i j+1 时，时，a(1)ij=0。然后对。然后对A1使用使用 QR 方法。容易方法。容易看出，从上看出，从上Hessenberg矩阵矩阵A1出发，经过迭代所得的出发，经过迭代所得的Ak(k=2，3，)全都是上全都是上Hessenberg矩阵。事实上，设矩阵。事实上，设Ak是上是上Hessenberg矩阵，则由于矩阵，则由于Rk 1是上是上Hessenberg矩阵，故矩阵，故Qk=Ak Rk 1 是上是上Hessenberg矩阵，因而矩阵，因而Ak+

24、1=RkQk也是上也是上Hessenberg矩阵。矩阵。2022-11-17397.3 QR方法方法 6.3.3 带原点平移的带原点平移的QR已经证明，基本已经证明，基本QR方法的收敛速度一般是线性收敛的方法的收敛速度一般是线性收敛的.为了加为了加速收敛，引进带原点平移的速收敛，引进带原点平移的QR 方法方法.设设A是是n n非奇异实矩阵，令非奇异实矩阵，令A1=A，并取一适当的数，并取一适当的数u1，对矩，对矩阵阵(A1 u1I)作作QR分解分解 A1 u1I=Q1R1然后令然后令 A2=R1Q1+u1I又取一适当的数又取一适当的数u2，对矩阵，对矩阵(A2 u2I)作作QR分解分解 A2

25、u2I=Q2R2反复进行这种运算，得到迭代公式反复进行这种运算，得到迭代公式 2022-11-17407.3 QR方法方法 称为带原点平移的称为带原点平移的QR方法，称方法，称uk为第为第k次迭代中的原点平移量次迭代中的原点平移量 产生的序列有下述性质产生的序列有下述性质(1)Ak+1与与Ak相似相似 111,2,kkkkkkkkAAAu IQ RkAR Qu I(2)当当Ak 为上为上 Hessenberg 阵时，阵时，Ak+1也是上也是上 Hessenberg 阵，阵，迭代若干次后，若迭代若干次后，若 足够小，就可以认为足够小，就可以认为 是特征是特征值的近似值，然后将值的近似值，然后将A

26、k+1的第的第n行第行第n列去掉列去掉(1),1|kn na(1),1kn na2022-11-17417.3 QR方法方法 如果对如果对(Ak ukI)作作QR分解时利用分解时利用 Householder矩阵，则有矩阵，则有 恰当的选用平移量恰当的选用平移量uk可加速分解过程收敛，可加速分解过程收敛，uk的选取一般有的选取一般有两种两种(1)令令 uk=()()()121()kkkknnkkRHHHAu I()()()121kkkknQHHH()()()()()()11211211,2,kkkkkkknnknAHHHA HHHk(),kn na2022-11-17427.3 QR方法方法 (

27、2)设设A1已经是上已经是上 Hessenberg矩阵，则矩阵，则Ak的形式为的形式为 先求出先求出Ak最右下角的二阶子矩阵最右下角的二阶子矩阵()()()11121()()()21222()32()1,()(),100000000kkknkkknkkknnkkn nnnaaaaaaaAaaa ()()1,11,()(),1kknnnnkkkn nnnaaDaa2022-11-17437.3 QR方法方法 的两个特征值，然后取其中按模最小的一个作为平移量的两个特征值，然后取其中按模最小的一个作为平移量uk 在迭代过程中，如果在迭代过程中，如果 已接近于零，就取已接近于零，就取 作为矩作为矩阵阵

28、A的特征值的特征值 n的近似值的近似值,并对并对 Ak+1左上角的左上角的(n 1)阶主子矩阵阶主子矩阵进行的迭代；进行的迭代；按照这种平移量的选取方法进行迭代。可以断言，下列极限按照这种平移量的选取方法进行迭代。可以断言，下列极限成立成立()()1,2,1lim0kknnn nkaa(1),1kn na(1),kn na如果在迭代过程中如果在迭代过程中 接近于零，则取矩阵接近于零，则取矩阵 Dk+1的两个特的两个特征值作为矩阵征值作为矩阵A的特征值的特征值 n 1和和 n的近似值，然后对的近似值，然后对Ak+1左上左上角的角的(n 2)阶主子矩阵进行迭代。可见，每求得阶主子矩阵进行迭代。可见，每求得A的一个或两的一个或两个特征值之后就降阶迭代，直至余下一个个特征值之后就降阶迭代，直至余下一个2 2的矩阵为止的矩阵为止.(1)1,2knna2021