九章代数特征值问题备课讲稿.docVIP

九章代数特征值问题备课讲稿 数值分析数值分析第九章代数特征值问题工程实践中有多种振动问题，如桥梁或建筑物的振动，机械机件、飞机机翼的振动，及一些稳定性分析和相关分析可转化为求矩阵特征值与特征向量的问题。 但高次多项式求根精度低,一般不作为求解方法法.目前的方法是针对矩阵不同的特点给出不同的有效方法.?()ijAa AfIAn?nn矩矩阵的的特特征征值值是是的的特特征征多多项项式的的个个零零点点.数值分析数值分析第九章代数特征值问题第一节特征值的估计和数值稳定性第二节幂法和反幂法第三节求矩阵全部特征值的QR方法数值分析数值分析第一节特征值的估计和数值稳定性?为格希格林圆盘。 则称，令阶矩阵对定义i iiini jjiji n n ijra Z C ZZn ia ra A n?),2,1(,)(1? 一、格希格林圆盘(Gerschgorin)?nn nn nnin iinixxxxa a aa a aa a axA x Ax?11111212111211?，则有最大元为的特征向量规范化使其，将设有数值分析数值分析内。 为中心的格希格林圆盘必须在以此式说明，得到因为个方程是其第iiini jjijii jnijjj ijiiar a a nj xxa ai?11),2,1(,1,? 二、特征值问题的稳定性数值分析数值分析数值分析数值分析() (0)()11(1,2,)(1,2,),iiiniiix in uni ny x?为为简简便便，不不妨妨设。 因因为线线性无无关关，故故必必存存在在个个不不全全为为零零的的数使使得。 () (1) (0)()()11() (1) (2)()211211()()()n nk k k k i k iii iiik k k k n nny Ay Ay A x xy x x x?由11()()211() (1)() (1)1111210,(2,3,)lim()lim()()ink ik ii iiik kink k kikiiii nx xky x xx?设由得故只要要充分大，就有数值分析数值分析() (1)1 (1)() (1)1111 (1)1()()(),(1,2,)kik k k kkikik kiyy xy xyinyy yi?因因此此，可可把把作作为为与与相相应应的的特特征征向向量量的的近近似似。 由为的的第个个分分量量。 21A?按按上上面面式式子子计计算算矩矩阵按按模模最最大大的的特特征征值与与相相应应的的特特征征向向量量的的方方法法称称为为幂幂法法。 幂幂法法的的收敛敛速速度度依依赖赖于于比比值值，比比值值越越小小，收收敛敛越越快快。 数值分析数值分析 (0)1() (1)() (1)111110,2, (1)0 (1)kk kyy xy x?两点说明）如果的选取恰恰使得幂法计算仍能进行。 因为计算过程中舍入误差的影响，迭代若干次后，必然会产生一个向量它在方向上的分量不为零，这样，以后的计算就满足所设条件。 ）因计算过程中可能会出现溢出或成为的情形。 解决方法每次迭代所求的向量都要归范化。 因此，幂法实际使用的计算公式是00121()()()()()()()max()(,.)k kkkk kkZ yy AZC yZy Ck?数值分析数值分析1()()11.(),(,),2.1,03.max4.5.,66.,1,3ij nk k kr i rinA ay y yNkr y y CyZ yAZCCyk Nk k?()算算法法输输入初初始始向向量误误差差限限，最最大大迭迭代代次次数。 置求求整整数数，使，y y计计算置若输输出停停机机；否否则则，转若置转；否否则则，输输出出失失败信信息息，停停机机。 数值分析数值分析030010112121002101xx10001012xx105225()()()()()()()()()(,),.(,),(,),(,.,),(.,.),TTTTTAyZ yyA ZCyZCy A ZC用用幂幂法法求求矩矩阵的的按按模最最大大的的特特征征值值和和相相应应的的特特征征向向量量。 取例例解解?25.,数值分析数值分析 (8) (7) (8) (9) (8)31(2.7650948,2.9981848,2.9990924)2.9990924(0.9219772,0.9996973,1)(2.8436517,2.9993946,2.9996973).2.99969732.99909240.000604910.2.9996973.yAZCZy AZ?由故相相应应特 (1)123121(2.8436517,2.9993946,2.9996973)3,2,11-1,12.3TxA?征征向向量量为。 事事实实上上，的的特特征征值，与对对应应的的特特征征向向量量为为（，）。 此此例例中中比比值值为数值分析数值分析两种特殊情况12121112() (1)()11 (1)()1111.1,()m m nmk kmmk mk nmnmnm Anyxxx x?前前面面假假定如如果果按按模模最最大大的的特特征征值值有有多多个个，即幂幂法法是是否否有有效效？（）是重重根根，即矩矩阵仍仍有个个线线性性无关关的的特特征征向向量量。 此此时时有有显显然然，只只要1() (1)()11 (1)()11 (1)12()(),y()mk kmmmmkim kikkx xx x Ayyy?不不全全为为零零，当充充分分大大时时，就就有因也也是是矩矩阵相相应应于的的特特征征向向量量，故故有为为相相应应的的特特征征向向量量，即即对对这这种种情情况况幂幂法法仍仍然然有有效效。 数值分析数值分析?1213() (1) (2) (3)()3112311() (21)21 (1) (2) (2)2 (1) (2)112112 (2)211,2()2, (1)()()()()k k kkk nnnkk kk kkikiA nyxxx xykxxxxx xyy?（）且且矩矩阵有个个线线性性无无关关的的特特征征向向量量。 由由上上式式可可知知，是是个个摆摆动动序序列列，当充充分分大大时时，有 (2)() (1)1 (1)1 (2)112() (1) (2)112 (1)()1 (1)111 (1)()11 (2)112/ (1) (1)22 (1)kkiik k kk kkk kkk kk ky yyxxy xxy yxy yx?又又由故故在在这这种种情情况况下下，仍仍可可按按幂幂法法产产生生向向量量序序列列。 数值分析数值分析?12121 (1)()1()12nm mnk kkAyAyyA n?综上可知，当当的特征值分布为或时，用幂法可以计算出及相应的特征向量。 如果按迭代所得向量序列呈有规律的摆动，则可能为的情况。 否则应考虑用别的方法求解。 此外，当矩阵无无个线性无关的特征量时，幂法收敛很慢，亦应考虑改用其他方法。 幂法计算简便易行，它是求大型稀疏矩阵按模最大特征值的常用方法。 幂法小结数值分析数值分析 二、幂法的加速因为幂法的收敛速度是线性的，而且依赖于比值,当比值接近于1时，幂法收敛很慢。 幂法加速有多种，介绍两种。 12?() (1)() (1) (1) (2)()211211()()()()iik kkkkkknnnA A pI ApA pIApI yAyy ApI yp pp xx xpp?1.原点移位法矩阵阵与的特征值有以下关系若若是是的特征值，则就是的特征值，而且相应的特征向量不变。 如果对矩阵按计算，则有数值分析数值分析() (1)211122111211()()()()(2,3,)kkkkknn niiyApIypppu uup ppp ppinp?适当地选取，使得且1ApI pA?这这样样，用用幂幂法法计计算算的的最最大大模模特特征征值及及相相应应特特征征向向量量的的收收敛敛速速度度比比对对用用幂幂法法计计算算要要快快。 这这种种加加速速收收敛敛的的方方法法称称为为原原点平平移移法法。 数值分析数值分析12312322122222112112100)1(),2(2,3,2)n nninnnnn nppApp pp inpp?原点平移法使用简便，但但的选取困难。 在一些简单情形，可估计。 如当矩阵的特征值满足（或时，取则有且11?因此，用原点平移法求可使收敛速度加快。 数值分析数值分析 (0)() (1) (4)414051302.9,102.8(1,1,1),()6.9140510.10100.1(3.1000568,2.214326,0.968766T k kA pAy yApI yApIy?-4用,用原原点点平平移移法法求求矩阵的的按按模模最最大大的的特特征征值值，要要求求误误差差不不超超过过10。 取取一按进进行行计解算例例4 (5)54541)3.1000568(3.0999984,2.2142846,0.9687501)3.09999840.000058410y?数值分析数值分析112321213.09999842.95.9999984(3.0999984,2.2142846,0.9687501).6,3,2.8,1,20.113.131TAxAApp?所所以以，矩矩阵的的按按模模最最大大的的特特征征值值为相相应应的的特特征征向向量量为不不难难求求出出，的的特特征征值值为若若对直直接接用用幂幂法法，则则比比值而而用用原原点点平移移法法，则则有因因此此收收敛敛速速度度明明显显加加快快。 数值分析数值分析?1211222112121lim0()22kkkkk kkkkkkkkkkk kkkk kkka aa acaaa aa akaaaaa aaaaa aaa aaaaaaaaA itken?加2.A itken加速如如果果序序列线线性性收收敛敛到，即则则当充充分分大大时时，有序序列比更更快快地地收收敛敛到，这这就就是加速速法法。 将将这这一一方?kC法法用用于于幂幂法法所所产产生生的的序序列，可可加加快快幂幂法法的的收收敛敛速速度度。 数值分析数值分析101012210021010211.(),(,),2.1,0,0,13.m ax4.()5.26.,77.,ij nri rinrA ayyyNkr yyy CyZyAZyCa aaaa apyk N?算算法法输输入初初始始向向量误误差差限，最最大大迭迭代代次次数。 置求求整整数，使，计计算置计计算若输输出停停机机；否否则则，转若置,1,3p kk?转；否否则则，输输出出失失败败信信息息，停停机机。 也(也可可采采用用幂幂法法迭迭代代两两步步或或三三步步，加加速速一一次次的的方方法法）数值分析数值分析 三、反幂法反幂法是计算矩阵按模最小的特征值及特征向量的方法，也是修正特征值、求相应特征向量的最有效的方法。 11111,1Ann uAAx xxAxAx xAAAA A?设设为阶非奇异矩阵，为为的特征值与相应的特征向量，即此式表明，的特征值是是的特征值的倒数，而相应的特征向量不变。 因此，若对矩阵用幂法，即可计算出的按模最大的特征值，其倒数恰为的按模最小的特征值。 这就是反幂法的基本思想。 数值分析数值分析1() (1)()1 (1)()kkkkkAAAy yyA yyA?因为的计算比较麻烦，而且往往不能保持矩阵阵的一些好性质（如稀疏性），因此，反幂法在实际运算时以求解方程组代替幂法迭代求得，每迭代一次要解一个线性方程组。 由于矩阵在迭代过程中不变，故可对对先进行三角分解，每次迭代只要解两个三角形方程组。 数值分析数值分析()()()1()()() (1)()1.2.max,3.kkkri ri nkkkkkAPA LUryyC yyZCLWPZ Uy W?反幂法计算的主要步骤对对进行三角分解求整数数，使得计算解方程组数值分析数值分析0()()iii j j iiijjiiAA IA I?用用带带原原点点平平移移的的反反幂幂法法来来修修正正特特征征值值，并并求相相应应的的特特征征向向量量是是非非常常有有效效的的。 设设已已知的的一一个个特特征征值的的近近似似值值为，因接接近，一一般般有故是是矩矩阵的的按按模模最最小小的的特特征征值值，且且由上上式式可可知知，比比值较较小小。 因因此此，对用用反反幂幂法法求一一般般收收敛敛很很快快，通通常常只只要要经经过过 二二、三三次次迭迭代代就就能能达达到到较较高高的的精精度度。 反幂法的一个应用数值分析数值分析111.(),(,),2.1,13.()m ax5.1116.,77.,1,ij nririnrA axxxNk uPAIL UryyyCyZL WZ UyWyCyuk Nkk?算算法法输输入近近似似值，初初始始向向量误误差差限，最最大大迭迭代代次次数。 置作作三三角角分分解解求4.求整整数，使，计计算置若则则置输,输出停停机机；否否则则，转若置,4u转；否否则则，输输出出失失败败信信息息，停停机