第八章特征值问题的计算方法

第八章特征值问题的计算方法/*ComputationalMethodofEigenvalueProblem*/本章主要介绍矩阵的特征值和特征向量的计算方法。特征值和特征向量的基本概念与性质§1基本概念与性质1Def设，若存在向量和复数满足nnACnxCAxx，则称是矩阵的特征值，是特征值xA相应的特征向量。0det()IA()det()ApIA特征多项式的根的集合：谱集()A1212det()()()()pnnnpIA其中12;()pijnnnnij称为的代数重数（简称重数）；ini()iimnrankIA为的几何重数。iiimn2Def设，nnACiimn对于矩阵的特征值，如果Ai，则称该特征值为的一个半单特征值。Ai若的所有特征值都是半单的，则称是非亏损的。AA是非亏损的等价条件是有n个线性无关的特征向量AA3Def设，,nnABC若存在矩阵，使得P1BPAP则称和是相似的。AB相似矩阵有相同的特征值1AxxPAPPxPxBPxPxAxx设寻求已知矩阵的相似矩阵，要求：矩阵的特征值和特征向量容易计算ABB本章QR算法的基本思想：811..Th1(,,)iir设，有r个互不相同的特征值，nnAC其重数分别为，则一定存在非奇异矩阵11()((),,,());iiinniikiJdiagJJCir使得（Jordan分解）1(,,)inirnnPC其中112((),(),,())rPAPdiagJJJJ11()iijiiJ()jiJ且除了的排列次序外，是唯一的。J称作的Jordan标准型AJ812..Th设，则存在酉矩阵，使得：nnAC（Schur分解）其中是上三角矩阵，且适当选择，可使的元素HUAUTnnUCTUT按任意指定的顺序排列。813..Th设，令()nnijAaC（圆盘定理）/*DiscTheorem*/则1(){:};,,iiiijjiGAzCzaain12()()()()nAGAGAGA814..Th设为对称矩阵，则存在正交矩阵nnAR（谱分解定理）/*SpectralDecomposition*/其中是的n个特征值。nnQR使得1(,,)TnQAQdiag1,,nA815..Th设为对称矩阵，且的特征值为nnAR（极大极小定理）其中表示中所有k维子空间的全体。则有12nA0maxminniTiTuuAuuu10minmaxnniTTuuAuuunknR设为对称矩阵，其特征值分别为816..Th,nnABR（Weyl定理）则有1212;nn212;,,,iiABin说明：对称矩阵的特征值总是良态的。注意：实际问题中矩阵一般都是由计算或实验得到，本身必然存在误差，不妨假设BAA212;,,,iiAin§2幂法与反幂法/*PowerMethodandReversedPowerMethod*/幂法是计算一个矩阵的模最大的特征值和对应的特征向量的一种迭代方法（又称为乘幂法）。一、幂法的基本思想与算法假设是可对角化的，即存在如下分解：nnACA1AXX其中1(,,)ndiag1;[,,]nnnXxxC不妨假设12n对于0nuC01122;nniuxxxC011nnkkkjjjjjjjAuAxx11121(()))njkkjjjxx011211(()))knjkjjkjAuxx11()xk01kkkAuu说明：当k充分大时,的一个近似特征向量为1特征向量可以相差一个倍数01kkkAuu因为向量中含有未知量，实际不能计算1ku但我们关心的仅是的方向，故作如下处理：0kkkAuu令其中为的模最大分量k0kAu11121011121(()))(()))njkkjjkjnkjkkjjjxxAuxx11()xkx幂法迭代算法：1kkkAuu1limlimlimkkkkkkAuu1Axx1kFork=1,2,3,…1kkyAukkyif1kkuu输出和kukkkkyu001,uu设和均收敛，由算法知kuk幂法可以计算矩阵的模最大的特征值和对应的特征向量1ku解：Step1210131014A例1：利用幂法求下列矩阵的模最大的特征值及相应的特征向量.A0111()Tu(取初始向量为)10355()TyAu151113115()TyuStep2212311555()TyAu25222231112525()TyuStep3321842492(...)TyAu3492.33303659085371(..)TyuStep443158543926848537(...)TyAu448537.44403266080901(..)Tyu特征值及相应的特征向量精确值为:47321.02679073201(..)Tu幂法的收敛性：821..Th12p设有p个互不相同的特征值满足：nnAC且模最大特征值是半单的，如果初始向量在的特征子空间上的投影不为零，则由幂法算法产生的1ku向量序列收敛到的一个特征向量，且数值10u11x序列收敛到。k1特征子空间：0VxAxx证明：设有如下Jordan分解：A11(,,)pAXdiagJJXiinniJC是属于的Jordan块构成的块上三角矩阵i111nJI是半单的特征值110yXu令将和如下分块：yX12(,,,)TTTTpyyyy12pnnn12(,,)pXXXX12pnnn1010(,,)kkkpAuXdiagJJXu111222kkkPppXJyXJyXJy111222kkkpppXyXJyXJy21112211(()())pkkkppJJXyXyXy0111222kkkkPppAuXJyXJyXJy021122111()()kpkkppkJAuJXyXyXy1111110()/()kiiiJJ01110lim()kkkAuXy记11111XyxXyAXXJ11111AXXJX11111AXyXy111Axx1kkkAuu011kkkAu0110kkkkAuAu1111()kXyukXy1limkkux是属于的一个特征向量11x1kkkAuu1()kk几点说明：定理8.2.1条件不满足时，幂法产生的向量序列ku可能有若干个收敛于不同向量的子序列；幂法的收敛速度取决于的大小；21:021122111()()kpkkppkJAuJXyXyXy加速方法：适当选取，对应用幂法AI称之为原点平移法1Axx1Axxxx1()()AIxx原点平移法不改变矩阵的特征向量A幂法可以计算第二个模最大特征值2常用的方法：降阶方法（收缩技巧）设已经计算出模最大特征值及其特征向量11x111Axx对向量，采用复的Household变换计算酉矩阵1xP111Pxe1111HPAPePAx1111Px11e10HPAPB其中是n-1阶方阵B2为的模最大特征值B二、反幂法的基本思想与算法反幂法是求一个矩阵的模最小的特征值和对应的特征向量的一种迭代方法（又称为反迭代法）。设，则Axx11Axx1A对应用幂法就可以求得矩阵的模最小的特征值和相应的特征向量。A不妨假设的特征值为11nnA则的特征值为11nn1A1ii反幂法算法：Fork=1,2,3,…1kkAyzkkyif1kkzz输出和kzkkkkyz001,zzlimknkzxnnnAxx若和均收敛，由幂法知kzk1kzlimknk收敛速度取决于的大小1:nn反幂法每次迭代都需要求解方程组1kkAyz带位移的反幂法：实际应用中，反幂法主要用于求特征向量。且用某种方法已经得到的特征值的近似值A11对矩阵采用反幂法迭代格式为：AI1记假设的特征值满足120nA1()kkAIvzkkkvzvFork=1,2,3,…因为方程组的系数矩阵Doolittle分解化为两个三角方是固定的，通常采用(选主元)AI程组求解，从而减少工作量。AILU求解方程组化为：1()kkAIvz1kkkkLyzUvy带位移的反幂法迭代格式：Fork=1,2,3,…1kkLyzkkUvykkkvzv收敛速度取决于的大小12当时，收敛速度会非常快1设矩阵存在Doolittle分解：AI解：210131014A例2：用带位移的反幂法求矩阵12679.）的近似特征向量。33对应特征值（精确值为A12679.AILU其中11365910273101..L073211000366210000011...U0111()Tz10Lyz1100000636619999...yStep1反幂法具有一次“迭代性”11Uvy167763938496000018158199...vStep221Lyv2100001107960073...y22Uvy220327411488072544673...v222100000732002679...vzv所求近似特征向量为：§3Jacobi方法Jacobi法：计算实对称矩阵全部特征值和相应特征向量基本思想对,nnTARAAQ存在正交矩阵，满足12(,,,)TnQAQdiag记12(,,,)nQqqq则12;,,,iiiAqqin寻找正交相似变换，将矩阵约化为对角阵即可QA正交相似变换求法：通过Givens变换来实现经典Jacobi方法设[],nnijijjiAaRaa令1122222111()()()nnniiijFiijjiEAAaa非对角“范数”当时，趋于一个对角阵0()EAA(,,)(,,)TGpqAGpq先来研究一下矩阵的元素和矩阵的元素之间的关系。AGivens变换记为，下面通过Givens变换(,,)Gpq对矩阵进行约化，使得0()EAA例如取424;,npqcos;sincs记11a12a24a13a14a13a22a12a23a23a33a34a14a24a34a44a10s000c000100s0c10s000c000100s0c11a12a13a14a13a23a33a34a10s000c000100s0c11a13a13a33a()ipipiqbcasa;;iqipiqbsaca(,)ipq11a13a13a33a222()pppppqqqbcascasa222qqpppqqqbsascaca