4-1幂法和反幂法

第四章特征值与特征向量的计算§1幂法和反幂法1.1幂法用于求矩阵的按模最大的特征值与相应的特征向量的近似值。设A为n阶实矩阵,,(1,2,,)iiuin为其特征值与相应的特征向量,且满足：n32112,,,nuuu线性无关.对任意向量(0)x,有(0)1niiixui不全为零。()(1)(0)1121211211kkknnkkiiiiiiikkknnnxAxAxAuuuuu()111kkxu充分大时，有，当设k01()()1111kkkAxAux()kx1可近似地作为矩阵A的属于的特征向量。()(0)kkxAx上述迭代过程实质上即称为幂法。在实际计算时，为避免()kx()kx过大或过小，每迭代一次都对进行一次归一化，使()1kx实际迭代公式是(1)(1)(1)(1)(),1,2,kkkkkxyxxAyk()1kyu1在计算时，可采用不同的范数。比如，利用时，在此迭代格式下，(1)()kTkrkTrexey假定(1)kx的第r个分量的模最大。记010x如果选择的使得，由于计算过程111limTrkTkreAueu中舍入误差的影响必然会在迭代的某一步产容易证明：()1,0.kxu生这样的它在方向上的分量不为这样().kx相当于以为初始向量重新开始迭代算法4.11.输入A，初始向量,,xN2.置0,1k3.求整数r,使1max,ririnxxx4.计算,,xyxAy置rx5.若,输出,x,停机；否则，转66.若Nk,置,,1kk否则输出失败信息，停机。转3;可以证明，12112(1);mmmn3121,)2(当A有n个线性无关的特征向量时，在以下两种情况下，仍能利用幂法求矩阵的绝对值最大的特征值及相应的特征向量。个线性无关的特征向量。例1用幂法求矩阵210120012A的按模最大的特征值和相应的特征向量。取(0)(0,0,1)Tx要求误差不超过310解：000,0,1,3,1Tyxr1010,1,2,3,2,2TxAyr(1)(1)(0,0.5,1)Txy(2)(1)10.5,2,2.5,3,2.5,2.5TxAyr(2)(2)(0.2,0.8,1)Txy(3)(2)11.2,2.6,2.8,2.8TxAy(9)(8)1132.99969732.999092410.000604910幂法的收敛速度取决于比值21,比值越小,收敛越快。1.2幂法的加速（一）原点移位法设A有特征值i,且21,取0使得001i且120101maxii用幂法求矩阵IA0的按模最大的特征值1则,011这就是原点移位法。例如，1100,298,210.981此时，097100(2,3)ii收敛速度较慢。若取且则收敛速度加快。395012101max298==3100ii(二)幂法的埃特肯（Aitken）加速若ka收敛于a且0lim1Caaaakkk,即ka线性收敛，当k充分大时，有aaaaaaaakkkk121kkkkkkkaaaaaaaa12212)(可以证明aak比aak快，以ka逼近a这就是Aitken加速法。算法4.21.输入)(ijaA，初始向量x，误差限，最大迭代次数N.2置0.1,0,0,1010k.3求整数r，使1max,ririnxxx.4．计算Ayxxy,置2rx.5计算01220102)(.6若0，输出,,x停机；否则转7.7若Nk，置,1,,,01201kk转3；否则输出失败信息，停机.例3用Aitken加速法求解例1解2(1)(2.52)23.254.852(2)(2.82.5)2.53.02499995.42857145.62(4)(2.97560972.9285714)2.92857142.991861922.97560972.92857143.0004416(5)2.9999894(5)(4)30.0004522510（1）A与1A的特征值互为倒数，特征向量不变，求A的按模最小的特征值n求1A的按模最大的特征值n1。1.3反幂法基本思路：（2）计算)(1)1(kkyAx解方程组)()1(kkyAx计算步骤：给定初始向量)0(x（1）对A进行三角分解LUA（2）归一化，求整数r，使)(1)(maxkinikrxx()()(),kkkrxxy（3）解方程组ZUxyLZkk)1()(,nkrx)1(1事实上，反幂法是求特征向量的最有效方法。已知，则i，对IA用反幂法修正并求相应特征向量。1.输入)(ijaA，近似值，初始向量Tnxxx),,(1误差限，最大迭代次数N。算法4.3反幂法2置1,1k。3.作三角分解LUIA)(。4.求整数r，使得1max,ririnxxx。注：当0时，算法4.3计算出A的按模最小特征值。5.计算xyZUxyLZ,置rx6.若11，置1，输出x,，停机；否则转7。7.若Nk，置,1kk，转4；否则,输出失败信息，停机。例4用反幂法求矩阵210120012A接近2.93的特征值，并求相应的特征向量。取Tx)1,0,0()0(。解：对IA93.2作三角分解LUIA93.210009310010,009311101000930.930.93-.-LU-.--.(0)(0)(0)(1)(1)(0,0,1)3(0,0,1)(7.9590586,7.4019246,6.8837898)TTTyxrLZyZUxZxTyr)8649.0,93.0,1(,9590586.7,10752688.3193.2,8837898.6)1(迭代3次，得(3)3.0000954,(1,0.9992431,0.99914)Tuy，与特征向量的准确值1,1,1Tu的误差001.00007569.0r而在幂法求解中Ty)1,999899.0,9479795.0()9(特征向量的误差为1.00520205.0rJacobi方法：通过一系列旋转相似变换将实对称矩阵A变成近似对角矩阵)1(kA，从而求出A的全部特征值与相应的特征向量。QR方法是求解中小型矩阵全部特征值与相应特征向量的有效方法。先通过一系列相似变换（Householder变换）将矩阵化成拟上三角阵H，然后再通过一系列正交相似变换（QR分解）将H化成上三角阵（或分块上三角阵），由此得矩阵的全部特征值。另外两种求矩阵特征值和特征向量的方法：