资源描述
3.1. 幂法和反幂法幂法和反幂法3.1.1 幂法幂法用于求矩阵A的按模最大的特征值及相应的特征向量。一、算法构造及收敛性分析 1 设设阶阶实实方方阵阵 满满足足：条条件件nnA o121 ,;有有 个个线线性性无无关关的的特特征征向向量量nAnxxxo122 ,的的 个个线线性性无无关关的的特特征征向向量量对对应应的的特特征征值值满满nAnxxx12足足。n下下面面通通过过分分析析由由迭迭代代格格式式( )(1)0,1,2,;初初始始值值任任意意选选取取。(3.1)(3.1)kkuAuku ( )1产产生生的的序序列列的的收收敛敛情情况况来来构构造造计计算算和和它它对对应应的的特特征征ku 1向向量量 的的计计算算方方法法。x第1页/共31页(0)1122,nnuxxx设设则则21112211kkknnnxxx 110,(2,3, ) iin不不妨妨设设由由得得( )(1)2(2)(0)kkkkuAuA uA u1122= kkknnA xA xA x111222kkknnnxxx 1 lim kiiikx 第2页/共31页( )(0)(3.1),kkuA u 1 1由由于于迭迭代代公公式式本本质质上上是是计计算算于于, ,因因此此称称( +1)( )kkuu与与对对应应分分量量近近似似成成比比例例，比比例例因因子子正正好好近近似似等等这这种种迭迭代代法法为为幂幂法法。( )11111121knkkkiiiiuxxx (+1)+1()1111kkkuxu 同同样样，我我们们还还有有。( )1ku 可可把把作作为为与与相相应应的的特特征征向向因因此此，量量的的近近似似。k当当 充充分分大大时时，有有第3页/共31页归一化处理与实际计算方法(1)(1)(1)(0)( )(1) 1,2,;kkkkkuyukuuAy 任任意意选选取取。2112211112112211kknknnkknnnxxxxxx (1)2(2)(0)( )(1)(2)1(0);kkkkkkkAuA uA uuuAuAu分分析析：( )(0)( )( )(0) ykkkkkuA uuA u第4页/共31页( )( )111111yykkkxkx当当 充充分分大大时时，有有，即即可可近近似似地地作作( )1y=1k 为为对对应应的的特特征征向向量量，且且特征值的计算 ( )(1)(1)1TT(1)( )(1)(1)11 ,kkkkkkkuAyyyuyy 方方法法 由由于于从从而而有有， T(1)( )1T(1)(1)kkkkyuyy 第5页/共31页(1)kky 1 1最最后后作作为为 的的近近似似值值，以以作作为为其其对对应应的的特特征征向向量量。3.1迭迭代代算算法法 (1)(1)(1)kkkuyu ( )(1)kkuAy T(1)( )T(1)(1)=kkkkkyuyy 1,2,;k 1kkk 终终止止条条件件：。(0)u任任意意选选取取。第6页/共31页 2(1)(1)T(1)(1)(0)( )(1)T(1)( )1(1)3.2 () 1,2,;=kkkkkkkkkkkkkkuyuukuuAyyuy 1 1迭迭代代算算法法使使用用范范数数任任意意选选取取。终终止止条条件件：。最最后后作作为为 的的近近似似值值，以以作作为为其其对对应应的的特特征征向向量量。第7页/共31页 (1)(1)1(1)(1)(1)(0)T( )(1)( )( )( )12(1)( )1(1)3.3 max 1,2,;,=signkkrjj nkkkrkkkkknkkkrrkkkkkhhuyhkuuAyhhhhhy 1 1迭迭代代算算法法使使用用范范数数任任意意选选取取。终终止止条条件件：。最最后后作作为为 的的近近似似值值，以以作作为为其其对对应应的的特特征征向向量量。第8页/共31页1(0)7612621324121251(1,0,0) ,10 .kkTkAx 例例1 1：用用幂幂法法求求矩矩阵阵的的按按模模最最大大的的特特征征值值和和相相应应的的特特征征向向量量。取取0 1 2 18 191 0.2407717 0.3617725 0.0000002 0.00000010 -0.8427010 -0.5878803 -0.4472137 -0.44721360 -0.4815434 -0.7235450 -0.8944271 -0.8944272 6.0000000 22.3043478 44.9999954 44.9999981123kkxxx 3.2解解：应应用用算算法法的的结结果果第9页/共31页0 1 2 12 131 0.2857143 0.5000000 0.0000420 0.00001680 -1.0000000 -0.8125000 -0.5000419 -0.50001680 -0.5714286 -1.0000000 -1.0000000 -1.0000000 6.0000000 16.7142857 44.9999989 45.0000002123kkxxx 3.3 应应用用算算法法的的结结果果第10页/共31页( +1)( )( )=kkkuAuu 1 1也也有有. .这这表表明明对对这这种种情情况况幂幂法法仍仍然然有有效效。121 mmn 时时幂幂法法是是否否有有效效？12 前前面面假假定定。若若按按模模最最大大的的特特征征值值有有多多个个，即即有有112,2mmAn是是重重根根，即即矩矩阵阵 仍仍条条有有件件个个线线性性无无关关的的特特征征向向量量。此此时时有有 ( )11111111kkkkmnmmmmnnuxxxx 1,mk显显然然，只只要要不不全全为为零零，当当 充充分分大大时时，就就有有( )111()kkmmuxx111mmxxA因因也也是是矩矩阵阵 相相应应于于 的的特特征征向向量量，所所以以，( )1kku 当当 充充分分大大时时，仍仍可可近近似似地地作作为为对对应应的的特特征征向向量量，同同样样第11页/共31页 (1)( )( )kkkxAxx 如如果果按按迭迭代代所所得得向向量量序序列列呈呈有有规规律律的的摆摆A综综上上可可知知，当当 的的特特征征值值分分布布为为12n或或12112mmnm ()()1 时时，用用幂幂法法可可以以计计算算出出及及相相应应的的特特征征向向量量。 幂幂法法计计算算简简便便易易行行，它它是是求求大大型型稀稀疏疏矩矩阵阵按按模模最最大大特特An动动，则则应应考考虑虑用用别别的的方方法法求求解解。此此外外，当当矩矩阵阵 无无 个个线线性性无无关关的的特特征征量量时时，幂幂法法收收敛敛很很慢慢，亦亦应应考考虑虑改改用用其其他他方方法法。征征值值的的常常用用方方法法。第12页/共31页3.1.2 反反幂法幂法 ,AnnxA 设设 为为阶阶非非奇奇异异矩矩阵阵，为为 的的特特征征值值与与相相应应反幂法是计算矩阵按模最小的特征值及特征向量的方法，也是修正特征值、求相应特征向量的最有效的方法。的的特特征征向向量量，即即111AxxxA xA xx 1AA 此此式式表表明明，的的特特征征值值是是 的的特特征征值值的的倒倒数数，而而相相应应的的1A 特特征征向向量量不不变变。因因此此， 若若对对矩矩阵阵用用幂幂法法，即即可可计计算算1AA 出出的的按按模模最最大大的的特特征征值值，其其倒倒数数恰恰为为 的的按按模模最最小小的的 特特征征值值。这这就就是是反反幂幂法法的的基基本本思思想想。第13页/共31页o12o121211 ,;2 ,nnnnnnAAnxxxAnxxx 设设阶阶实实方方阵阵 满满足足：有有 个个线线性性无无关关的的特特征征向向量量的的 个个线线性性无无关关的的特特征征向向量量对对应应的的特特征征值值满满足足 。n 则则用用反反幂幂法法计计算算及及相相应应的的一一个个特特征征向向量量的的步步骤骤如如下下: :1( )(1)( )1(1)( ) kkkkkAAAuuuA uuAA 因因为为的的计计算算比比较较麻麻烦烦，而而且且往往往往不不能能保保持持矩矩阵阵的的一一些些好好性性质质（如如稀稀疏疏性性），因因此此，反反幂幂法法在在实实际际运运算算时时以以求求解解方方程程组组 代代替替幂幂法法迭迭代代求求得得，每每迭迭代代一一次次要要解解一一个个线线性性方方程程组组。由由于于矩矩阵阵在在迭迭代代过过程程中中不不变变，故故当当 的的阶阶数数不不是是很很大大时时，可可考考虑虑对对 先先进进行行三三角角分分解解，则则每每次次迭迭代代只只要要解解两两个个三三角角形形方方程程组组。第14页/共31页 ( -1)( -1)( -1)( -1)( )T(1)( )T(1)(1)1( )1 2 3 5 =16 kkkkkkkkkkkkknnkAALUuRuyuLzyUuzyuyyy (0)(0)k k对对 进进行行三三角角分分解解任任取取非非零零向向量量做做初初始始特特征征向向量量；; ;4 4 解解方方程程组组，；当当时时，以以作作为为的的近近似似值值，作作相相应应的的近近似似特特征征向向量量。 ()3.4算算法法反反幂幂法法第15页/共31页* 0 () ()iiiiiAAIAI用带原点移位的反幂法来修正特征值，并求相应的特征向量是非常有效的。设已知 的一个特征值 的近似值为，因接近 ，一般有故是矩阵的按模最小的特征值，且由上式可知，比值较小。因此，对用反幂法求一般收敛很快，通常只要经过二、三次迭代就能达到较高的精度。反幂法的一个应用第16页/共31页 *(0)*( -1)( -1)( -1)( -1)( )T(1)( )T(1)(1)1*( ) 1. (),2. ()3 5 =16 3. 5ijkkkkkkkkkkkkkiikAauNAILUuyuLzyUuzyuyyy k k输输入入近近似似值值，初初始始向向量量, ,误误差差限限 ，最最大大迭迭 代代次次数数 。作作三三角角分分解解 ; ;4 4 解解方方程程组组，；当当时时，以以+ +作作为为 的的近近似似算算值值法法：， 作作相相应应的的近近似似特特征征向向量量。第17页/共31页(0)210 021012(0,0,1) . 2.930.9310 2.9300.931010.93100 0100 1/0.931TAAxAIAI例：，用反幂法求矩阵 接近2.93的特征值，并求相应的特征向量，取解：对作三角分解得40.931000.931000.93 1/0.9333.0000954,310(1, 0.9992431,0.9991478)(1,-1,1)0.001.TTur按算法迭代 次，与准确值 的误差小于，与准确值比较，残差第18页/共31页3.2 Jacobi方法方法1222,1(1) , diag(,) (1,2, ),2(),(), Tniijn nnTijn nijiji jAUU AUDinAUAaUBU AUbab 任任意意实实对对称称矩矩阵阵 可可通通过过正正交交相相似似变变换换化化成成对对角角阵阵 即即存存在在 正正交交矩矩阵阵使使得得其其中中是是 的的特特征征值值中中各各列列即即为为相相应应的的特特征征向向量量。（ ）在在正正交交相相似似变变换换下下，矩矩阵阵元元素素的的平平方方和和不不变变。设设为为正正交交矩矩征征向向量量。理理论论基基础础阵阵：，记记则则,1ni j Jacobi方方法法用用来来求求实实对对称称矩矩阵阵的的全全部部特特征征值值及及相相应应特特Jacob ,iA通通过过一一次次正正交交变变换换 将将 中中一一对对非非零零的的非非对对角角元元素素化化成成零零 并并且且使使得得非非对对角角元元素素的的平平方方和和减减少少。反反复复进进行行上上述述过过程程，使使变变换换后后的的矩矩阵阵的的非非对对角角元元素素的的平平方方和和趋趋于于零零，从从而而使使该该矩矩阵阵近近似似为为对对角角矩矩阵阵，得得到到全全部部特特征征方方法法的的基基本本思思值值和和特特路路：征征向向量量。第19页/共31页一、矩阵的旋转变换cos ,1sin ,pqppqqpqqppqUuuunuU 其其中中，的的主主对对角角线线元元素素中中其其余余为为 ；而而其其非非主主对对角角线线元元素素中中维维空空间间中中的的二二维维坐坐其其余余为为标标旋旋0 0。称称为为转转矩矩阵阵。( )pqU 坐坐标标旋旋转转矩矩阵阵是是正正交交矩矩阵阵. .11cossin1( )1sincos11pqU 第20页/共31页(1)(1)(1)22(1)22(1)(1)0, ()cossinsin2 sincossin2 cossin (, ) TpqqppqpqijppppqqpqqqppqqpqpiippiqiAaaAU AUaaaaaaaaaaaaaip qa 设设 为为实实对对称称矩矩阵阵，且且若若记记则则有有(1)(1)(1)(1)(1)(1)sincos ( , )1()sin2cos2 2()cot2 2qiiqpiqiijjiijpqqpqqpppqppqqpqaaaaaai jp qaaaaaaaa 如如果果取取 使使得得(1)(1)(/4)0,.pqqppqqpaaAaa 则则有有得得到到一一个个使使 中中非非零零的的非非对对角角元元素素变变成成零零的的正正交交相相似似变变换换第21页/共31页 (1)(2)( )(1)2(1)(1)2(1)(1)(1)(1)(1)(1), ( ),()()( , ),cossin ,kijijijijijjiijpiippiqiqiiqAAAAAE AaE Aaaaai jp q aaaaaa 对对重重复复上上述述过过程程得得到到一一个个矩矩阵阵序序列列。可可证证，虽虽然然这这种种变变换换不不一一定定能能使使矩矩阵阵中中非非对对角角元元中中零零元元素素的的个个数数单单调调增增加加，但但可可保保证证非非对对角角元元的的平平方方和和递递减减。以以 与与为为例例：设设，则则由由(1)(1)(1)(1)2(1)2(1)2(1)2(1)2,2222,sincos ,(, )=0()()()2()() +2() 2()( )2( ) piqipqqpijijpiqipqijijip qi jp qijpiqipqijip qi jp qaaip qaaE AaaaaaaaaE AaE A ，上上式式表表明明，在在上上述述旋旋转转变变换换下下，非非对对角角元元的的平平方方和和严严格格单单调调递递减减，因因而而对对角角元元的的平平方方和和单单调调递递增增。第22页/共31页( )o( )( )1j( )( )o( )( )(1)(1) 0,2 ,max3 cot2,cos24 sin ,( )4 3.6 Jacobik kkkk kk kk kkkkkkp qijinkkp pq qkp qkp qkkijkAAp qaaaaaUUAaa o oo o1 1 令令；求求整整数数使使得得计计算算旋旋转转矩矩阵阵： 由由计计算算相相应应的的和和并并得得到到旋旋转转矩矩阵阵；计计算算法法求求实实对对称称矩矩阵阵全全部部特特征征值值和和对对应应的的特特征征向向量量：方方算算法法(1)( )(1)(1)(1)(1)( )( )(1)(1)( )( )o(1)(1) 2(1) ( , ), =0, cossin , (, ) sincos , (, )5()()(),kkkkjiijpqqpkkkkpiippiqikkkkqiiqpiqikkkijijai jp qaaaaaaip qaaaaip qE AaE A ，； , ,若若(1)(1)(1)1122(0)(1)( )o, 12kkknnnaaaQU UUkk 则则为为特特征征值值，的的各各列列为为相相应应特特征征向向量量；否否则则，返返回回 ，重重复复上上述述过过程程。第23页/共31页 ( )2(0)( )( )2( )( )( )( )1j(1)(1)( )( )2Jacobi, lim ()=lim0,Jacobi1 max()(1)()() 2() , k kk kk kkkkijkki jkkkkp qijp qinkkkkp qA nAAAAE AaaaaE An nAE AE Aa ：设设 为为 阶阶实实对对称称阵阵，对对 用用法法得得到到序序列列其其中中则则即即法法收收敛敛。：由由，得得；又又由由计计算算的的公公式式可可得得从从收收证证而而有有敛敛定定理理明明1(1)( )1( )22 ()1()1( )(1)(1)22 11,lim ()lim 1( )0(1)(1)JacobikkkkkkkE AE AE An nn nE AE An nn n 因因即即法法收收敛敛。第24页/共31页说明：o1 Jacobi;定定理理表表明明，法法是是收收敛敛的的Jacobi法法是是求求中中小小型型稠稠密密实实对对称称矩矩阵阵的的全全部部特特征征值值与与特特征征向向量量的的较较好好方方法法。o2 JacobiAnAn当当 的的阶阶数数 不不太太高高时时，算算法法的的收收敛敛速速度度很很快快；但但当当 的的 阶阶数数 变变得得较较大大时时，其其收收敛敛速速度度将将会会变变慢慢，即即法法 为为适适合合计计算算中中等等规规模模的的实实对对称称矩矩阵阵的的特特征征值值问问题题；o3 对对中中等等规规模模问问题题，具具有有较较好好的的数数值值稳稳定定性性；求求得得的的结结果果 的的精精度度也也很很高高，得得到到的的特特征征向向量量正正交交性性很很好好；o4 不不足足之之处处：运运算算量量大大，不不能能保保持持矩矩阵阵的的特特殊殊形形状状 （如如稀稀疏疏性性）。第25页/共31页 00(0)12T(1)(0)(0)(0)0:1,2,cot20,4cos0.7071068,sin0.70710680.70710680.70710680 ( )0.70710680.70710680 ,001100.7071068030.70710680.70710680.70710682kpqUUAUA U 210121012AA 例例：用用JacobiJacobi方方法法求求 的的特特征征值值。解： 第26页/共31页11(1)230.707106780.47765830.88807380.45970081 0 00 0.888071:2,3,cot2,cos,sin 38 -0.45970080 0.4597008 ( ) 0.88807kpqUU T(2)(1)(1)(1)38 3.0000000 0.3250576 0.6279630 0.3250576 0.6339746 -0.0000000 0.6279630 0 2.3,U660254UAA第27页/共31页22(2)230.50478660.55166340.85165390.52410460.8516539 0 -0.5241046 0 1 2:1,3,cot2,cos,sin 00.5241046 0 0.8516( )53 9kpqUU T(3)(2)(2)(2) 3.3864461 0.2768366 -0.0000000 0.2768366 0.6339746 -0.1703642-0.0000000 -0.1703642 1.9795,UU793AA 第28页/共31页66(6)236:1,2,cot2-693.88568,-0.00072057929,cos0.9999997,sin0.0007205792 0.9999997 0.0007205792 0 ( ) -0.0007205792 0.9999997 0 0 kpqUU T(7)(6)(6)(6), 0 1 3.4142136 0 0.0000000UU -0.0000000 0.5857864 -0.0000242 0.0000000 -0.0000242 1.9999999(AAE (7)1.1668492e-009A 第29页/共31页123123(0)(1)(6)3.4142136,0.5857864,1.9999999;223.4142136,220.5857864,20.0000001 0.5000000 0.5000121 -0.7070982-0.7071068 0.7071068 0.0000121 0.5000000 QUUU所所以以，准准确确特特征征值值最最大大误误差差不不超超过过；又又 0.4999879 0.7071153 0.50000000.5000121 -0.7070982-0.70710680.7071068 0.0000121 0.50000000.4999879 0.7071153 所所以以，对对应应的的特特征征向向量量分分别别为为，第30页/共31页感谢您的观看。第31页/共31页
展开阅读全文