数值分析第8章矩阵特征值问题计算1

Waitasecond,whatdoesthatdominanteigenvaluemean?Thatistheeigenvaluewiththelargestmagnitude.WhyintheearthdoIwanttoknowthat?Don’tyouhavetocomputethespectralradiusfromtimetotime?但高次多项式求根精度低,一般不作为求解方法.目前的方法是针对矩阵不同的特点给出不同的有效方法.工程实践中有多种振动问题，如桥梁或建筑物的振动，机械机件、飞机机翼的振动，及一些稳定性分析和相关分析可转化为求矩阵特征值与特征向量的问题。1.(),()det()0()2.()0ijnnAaIAAnAAIAxAxxxA已知求代数方程的根。称为的特征多项式，一般有个零点，称为的特征值。设为的特征值，求相应的齐次方程的非零解（即求的非零解），称为矩阵对应于的特征向量。§1.幂法和反幂法.一、幂法求矩阵的按模最大的特征值与相应的特征向量。它是通过迭代产生向量序列，由此计算特征值和特征向量。1212(0)(1)()()(1)()1(1)(1,2,,)(1,2,,),,,,(1,2,),/,1(1,2ininkkkkkiikinnAininuuuxxAxkxkxxxui＋设阶实矩阵的特征值满足且与相应的特征向量线性无关。给定初始向量由迭代公式产生向量序列可以证明，当充分大时，有相应的特征向量为。为简便，不妨设(0)1,,)(1,2,,),iniiiinuninxu。因为线性无关，故必存在个不全为零的数使得。(1)()1(0)1111(1)111211122111111121()[()()]0,(2,3,,)lim()lim()nnkkkkkiiiiiiikkkknnnkiiiiknkiiikixAxAxAuuxuuuinuuk由设由得故只要充分大，就有(1)11111111121(1)(1)(1)1()1111111()()()[()],(1,2,)nkkkkiiiikikkkkkikikkixuuuxxxuxuinxxxi因此，可把作为与相应的特征向量的近似。由为的第个分量。21(0)1()1()1110,,2kkkAxxux按上面式子计算矩阵按模最大的特征值与相应的特征向量的方法称为幂法。幂法的收敛速度依赖于比值，比值越小，收敛越快。两点说明：）如果的选取恰恰使得幂法计算仍能进行。因为计算过程中舍入误差的影响，迭代若干次后，必然会产生一个向量它在方向上的分量不为零，这样，以后的计算就满足所设条件。）因111,(1)0(1)u计算过程中可能会出现溢出或成为的情形。解决方法：每次迭代所求的向量都要归一化。因此，幂法实际使用的计算公式是()()()()()1(1)()(1)1max(0,1,2,)kkkkkrriinkkkryxxxxkxAyx／111.(),(,,),2.1,03.max4.5.,,,66.,1,,3ijnririnrAaxxxNkrxxxxyxAyxxkNkk算法：输入初始向量误差限，最大迭代次数。置求整数，使，计算置若输出停机；否则，转若置转；否则，输出失败信息，停机。(0)3(0)(0)(1)(0)(1)(1)(2)(1)210021012(0,0,1),10.(0,0,1),(0,1,2),2,(0,0.5,1),(0.5,2,2.5),TTTTTAxyxxAyxyxAy例：用幂法求矩阵的按模最大的特征值和相应的特征向量。取解：2.5,(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.xAyyxAy由故相应特123121(2.8436517,2.9993946,2.9996973)3,2,11-1,12.3TuA征向量为。事实上，的特征值，与对应的特征向量为（，）。此例中比值为两种特殊情况12121112(1)11111111111.1,[()()]mmnmkkmmkkmnmmnnmAnxuuuu前面假定如果按模最大的特征值有多个，即幂法是否有效？（）是重根，即矩阵仍有个线性无关的特征向量。此时有显然，只要1(1)1111111(1)12()(1),,()mkkmmmmkimkikkxuuuuAxxx不全为零，当充分大时，就有因也是矩阵相应于的特征向量，故有为相应的特征向量，即对这种情况幂法仍然有效。1213(1)11113111223311(1)(21)21(2)21112211122(2)2(11,2()2,,[(1)()()]()()kkkkknnnkkkkkkkiikiAnxuuuuxkxuuxuuxxx（）且矩阵有个线性无关的特征向量。由上式可知，是个摆动序列，当充分大时，有2)()(1)1111122()11122(1)()11111(1)()111122/[(1)][(1)]22(1)kikkkkkkkkkkkkkxxuuxuuxxuxxu又由故在这种情况下，仍可按幂法产生向量序列。12121(1)()1()12nmmnkkkAxAxxAn综上可知，当的特征值分布为或时，用幂法可以计算出及相应的特征向量。如果按迭代所得向量序列呈有规律的摆动，则可能为的情况。否则应考虑用别的方法求解。此外，当矩阵无个线性无关的特征量时，幂法收敛很慢，亦应考虑改用其他方法。幂法计算简便易行，它是求大型稀疏矩阵按模最大特征值的常用方法。幂法小结二、幂法的加速因为幂法的收敛速度是线性的，而且依赖于比值，当比值接近于1时，幂法收敛很慢。幂法加速有多种，介绍两种。12／000(1)()0(1)()0(1)1120010112210100()()[()()]iikkkkkkknnnAAIAAIAIxAxxAIxuuu（一）原点移位法矩阵与的特征值有以下关系：若是的特征值，则就是的特征值，而且相应的特征向量不变。如果对矩阵按计算，则有适当地选取，10002101(2,3,)iiin使得且Asfarasthelawsofmathematicsrefertoreality,theyarenotcertain,andasfarastheyarecertain,theydonotrefertoreality.--AlbertEinstein(1879-1955)Howarewesupposedtoknowwhereitis?010001231230202010100)(),2(2,3,nnniAIAAi这样，用幂法计算的最大模特征值及相应特征向量的收敛速度比对用幂法计算要快。这种加速收敛的方法称为原点移位法。原点移位法使用简便，但选取困难。在一些简单情形，可估。如当矩阵的特征值满足（或时，取则有2022221012112111,)2nnnnnnn且因此，用原点移位法求可使收敛速度加快。0(0)(1)()00(4)414051302.9,102.8(1,1,1),()6.9140510.10100.1(3.1000568,2.214326,0.968TkkAAxxAIxAIx-4例：,用原点移位法求矩阵的按模最大的特征值，要求误差不超过10。解：取按进行计算4(5)54547661)3.1000568(3.0999984,2.2142846,0.9687501)3.09999840.000058410x11232120103.09999842.95.9999984(3.0999984,2.2142846,0.9687501).6,3,2.8,1,20.113.131TAxAA所以，矩阵的按模最大的特征值为相应的特征向量为不难求出，的特征值为若对直接用幂法，则比值／而用原点移位法，则有因此收敛速度明显加快。1211222112121lim0()22kkkkkkkkkkkkkkkkkkkkkkkaaaacaaaaaakaaaaaaaaaaaaaaaaaaaaaAitk（二）、幂法的埃特肯(Aitken)加速如果序列线性收敛到，即则当充分大时，有序列比更快地收敛到，这就是kena加速法。将这一方法用于幂法所产生的序列，可加快幂法的收敛速度。1010122100210010211.(),(,,),2.1,0,0,13.max4.()5.26.,,,77.,,,ijnririnrAaxxxNkrxxxxyxAyxaaaaaaxkN算法：输入初始向量误差限，最大迭代次数。置求整数，使，计算置计算若输出停机；否则，转若置0,1,3kk转；否则，输出失败信息，停机。(也可采用幂法迭代两步或三步，加速一次的方法）三、反幂法反幂法是计算矩阵按模最小的特征值及特征向量的方法，也是修正特征值、求相应特征向量的最有效的方法。11111,1AnnuAAuuuAuAuuAAAAA设为阶非奇异矩阵，为的特征值与相应的特征向量，即此式表明，的特征值是的特征值的倒数，而相应的特征向量不变。因此，若对矩阵用幂法，即可计算出的按模最大的特征值，其倒数恰为的按模最小的特征值。这就是反幂法的基本思想。1(1)()(1)1()(1)kkkkkAAAxxxAxxA＋因为的计算比较麻烦，而且往往不能保持矩阵的一些好性质（如稀疏性），因此，反幂法在实际运算时以求解方程组代替幂法迭代求得，每迭代一次要解一个线性方程组。由于矩阵在迭代过程中不变，故可对先进行三角分解，每次迭代只要解两个三角形方程组。反幂法计算的主要步()()()()()1()(1)1.2.max,,3.kkkkkririnkkAALUxrxxxyLzyUxz骤：对进行三角分解求整数，使得计算解方程组**********0()()iiiiAAIAI用带原点移位的反幂法来修正特征值，并求相应的特征向量是非常有效的。设已知的一个特征值的近似值为，因接近，一般有故是矩阵的按模最小的特征值，且由上式可知，比值／较小。因此，对用反幂法求一般收敛很快，通常只要经过二、三次迭