东北农业大学《数值分析》课件-第八章（隋老师）.pptx

东北农业大学东北农业大学 数值分析数值分析 第八章第八章 第八章第八章.矩阵特征值和特征向量计算矩阵特征值和特征向量计算 应用背景应用背景 工程实践中有多种振动问题，如桥梁或建筑物的振动，机械机件、飞机机翼的振动，及一些稳定性分析和相关分析可转化为求矩阵特征值与特征向量的问题。但高次多项式求根精度低但高次多项式求根精度低,一般不作一般不作为求解方法为求解方法.目前的方法是针对矩阵不同目前的方法是针对矩阵不同的特点给出不同的有效方法的特点给出不同的有效方法.1.(),()det()0()2.()0ijn nAaIAAnAAIA xAxxxA 已知求代数方程的根。称为 的特征多项式，一般有 个零点，称为 的特征值。设 为 的特征值，求相应的齐次方程的非零解（即求的非零解），称为矩阵 对应于 的特征向量。主要方法 乘幂法与反幂法（迭代法）QR算法 Jacobi 方法（变换法）1.1.乘幂法和反幂法乘幂法和反幂法.一、乘幂法一、乘幂法 乘幂法乘幂法：求矩阵的按模最大的特征值与相应的特征向量。基本思想基本思想：通过迭代产生向量序列，由此计算特征值和特征向量。1212(0)(1)()()(1)()(1)1 (1,2,)(1,2,),(1,2,),/,inikkkkkkiiiinnAininkxkxxnu uux0 xAxxu设阶实矩阵 的特征值满足且与相应的特征向量线性无关。给定初始向量由迭代公式产生向量序列可以证明，当 充分大时，有相应的特征向量为。因为(对应的特征向量）线性无关(0)1(1,2,),niiiininxu，故必存在个不全为零的数使得。(1)()1(0)1111(1)111211 1221111(1)1 111 ()()()0,(2,3,)limnnkkkkkiiiiiiikkkknnnikkkxAxAxAuuxuuuinxu 由 设由得(1)11111 111 121(1)(1)1()11 111 1(1)()1(1)1()()1 (),()(1,2,)nkkkkiiiikikkkkkkkikikikxuuuxxuxuxxxinAxx 故只要 充分大，就有因此，可把作为与 相应的特征向量的近似。由其为 按模值中最大的特征()kxi为的第 个分量。21(0)1()1()11 111 10,2,(1)0(1)kkkxxuxu 乘幂法的收敛速度依赖于比值，比值越小，收敛越快。两点说明：）如果的选取恰恰使得幂法计算仍能进行。因为计算过程中舍入误差的影响，迭代若干次后，必然会产生一个向量它在 方向上的分量不为零，这样，以后的计算就满足所设条件。）因计算过程中可能会出现溢出或成为的情形。解决方法：每次迭代所求的向量都要归一化。001111 ,111max(0,1,2,)=/Tkkkkiki nkkkAmkmm xRxyxyxy因此，乘幂法实际使用的计算公式:任取初始向量通常取，迭代过程为(0)3 210021012(0,0,1),10.TAx例：用乘幂法求矩阵 的按模最大的特征值和相应的特征向量。取(0)(1)(0)1(1)(1)1(2)(1)1(2)(2)2 (0,0,1),step1.(0,1,),2,(0,0.5,1),step2.(0.5,2,),2.5,(0.2,0.8,1),22.5TTTTTxyAxmyxmyAxmyxm解：(8)(7)8(8)(8)99819)3(2.7650948,2.9981848,)2.9990924(0.9219772,0.9996973,1)(2.8436517,2.9993946,).2.9996973-2.99969732.99909240.00062.049 10.2.92.999092499969739yAxmxyAxmmm由故 196973.(2.8436517,2.9993946,2.9996973)u 相应特征向量为。123121 3,2,11-1,1 2 .3TA事实上，的特征值，与 对应的特征向量为（，）。此例中比值为两种特殊情况两种特殊情况 12121 .mmn前面假定如果按模最大的特征值有多个，即乘幂法是否有效？112(1)111 111111111(1)111 11,()(),(mkkmmkkmnmmnnmkkmAnxuuuukxu（）是 重根，即矩阵 仍有 个线性无关的特征向量。此时有 显然，只要不全为零，当 充分大时，就有)mmu1 11(1)12()(1)mmkimkikuuAxxx因也是矩阵 相应于 的特征向量，故有为相应的特征向量，即对这种情况乘幂法仍然有效。1213(1)111311 12233111(1)(21)21(2)211 12211 122(212,(1)()()(),()kkkkknnnkkkkkiAnxuuuuxkxuuxuux （）且矩阵 有 个线性无关的特征向量。由上式可知，是个摆动序列，当 充分大时，有2)(2)()1,2()/kkkiikixxx(1)1111 122()11 122(1)()1111 1(1)()111122 (1)(1)2 2(1)kkkkkkkkkkkkkxuuxuuxxuxxu 又由故在这种情况下，仍可按乘幂法产生向量序列。121211(1)()()12 nmmnkkkAxAxx 1.当 的特征值分布为 或时，用乘幂法可以计算出 及相应的特征向量。2.如果按 迭代所得向量序列呈有规律的摆动，则可能为的情况。否则应考虑用别的方法求解。乘幂法小结乘幂法小结 An3.当矩阵 无 个线性无关的特征量时，乘幂法收敛很慢，亦应考虑改用其他方法。乘幂法计算简便易行，它是求大型稀疏矩阵按模最大特征值的常用方法。二、乘幂法的加速 因为乘幂法的收敛速度是线性的，而且依赖于比值 ，当比值接近于1时，幂法收敛很慢。幂法加速有多种，介绍两种:原点移位法；外推法 12000(1)()0(1)()(1)0101 111200221010 ()()()()iikkkkkkknnnAAIAAIAIxAxxAI xuuu（一）原点移位法矩阵 与的特征值有以下关系：若 是的特征值，则就是的特征值，而且相应的特征向量不变。如果对矩阵按计算，则有010002101010 (2,3,)iiinAIA适当地选取，使得且这样，用幂法计算的最大模特征值及相应特征向量的收敛速度比对 用乘幂法计算要快。这种加速收敛的方法称为原点移位法。001231230202010202222101211211 00)1(),2 (2,3,)2nnninnnnnnAin原点移位法使用简便，但选取困难。在一些简单情形，可估。如当矩阵 的特征值满足（或时，取则有且 因此1，用原点移位法求可使收敛速度加快。04 140 5 1302.9,102.8AA-4例：,用原点移位法求矩阵 的按模最大的特征值，要求误差不超过10。(0)(1)()00(1,1,1),()6.9140 510.10100.1TkkxxAI xAI解：取按进行计算 (4)4(5)54541(3.1000568,2.214326,0.9687661)3.1000568(3.0999984,2.2142846,0.9687501)3.09999840.000058410 3.09999842.95.9999984(3.0999984xmxmmmAx 所以，矩阵 的按模最大的特征值为相应的特征向量为 ,2.2142846,0.9687501).T123212010 6,3,2.8,1,20.11 3.131AA不难求出，的特征值为若对 直接用幂法，则比值而用原点移位法，则有因此收敛速度明显加快。1211222112121 lim0 ()22kkkkkkkkkkkkkkkkkkkkkaaaacaaaaaakaaaaaaaaaaaaaaaaaa（二）、乘幂法的Aitken加速如果序列线性收敛到，即则当 充分大时，有 kkkaaaAitkena序列比更快地收敛到，这就是加速法。将这一方法用于乘幂法所产生的序列，可加快乘幂法的收敛速度。1010122100210 1.(),(,),2.1,0,0,13.max4.()5.2ijnriri nrAaxxxNkrxxxxyxAyx 算法：输入初始向量误差限，最大 迭代次数。置求整数，使，计算置计算0102106.,77.,1,3xkNkk 若输出停机；否则，转；若置转；否则，输出失败信息，停机。(也可采用幂法迭代两步或三步，加速一次的方法）三、反幂法三、反幂法 反幂法是计算矩阵按模最小的特征值反幂法是计算矩阵按模最小的特征值及特征向量的方法，也是修正特征值、求及特征向量的方法，也是修正特征值、求相应特征向量的最有效的方法。相应特征向量的最有效的方法。11111 ,1 AnnuAAuuuA uA uuAAAAA设 为阶非奇异矩阵，为 的特征值与相应的特征向量，即此式表明，的特征值是 的特征值的倒数，而相应的。因的按模最大的特此，若对矩阵用幂法，即可计算出，倒数恰为 的按模最小的特征特征向量不值值。征其变反幂法的基本思想反幂法的基本思想 1(1)()(1)1()(1)kkkkkAAAxxxA xxA因为的计算比较麻烦，而且往往不能保持矩阵 的一些好性质（如稀疏性），因此，反幂法在实际运算时以求解方程组 代替幂法迭代求得，每迭代一次要解一个线性方程组。由于矩阵在迭代过程中不变，故可对，每次迭代只要解两个三先角进行三角分解形方程组。00111,1111max(0,1,2,)=/Tkkkkii nkkkkAAmkmm xRxyxyxy任取初始向量通常取，迭代过程为（避免求）()()()1(1)()-1-1 1.2.max,3.,1,limkkkkii nkkknnkknnnAALUymyxmUyzLzxm 反幂法计算的主要步骤：对 进行三角分解求计算解方程组若 则 反幂法的收敛比值为*0 ()()iiiiAAIAI用带原点移位的反幂法来修正特征值，并求相应的特征向量是非常有效的。设已知 的一个特征值 的近似值为，因接近，一般有故是矩阵的按模最小的特征值，且由上式可知，比值较小。因此，对用反幂法求一般收敛很快，通常只要经过二、三次迭代就能达到较高的精度。原点平移法原点平移法(0)210021012(0,0,1).TAAx例：，用反幂法求矩阵 接近2.93的特征值，并求相应的特征向量，取2.930.93102.9300.931010.93AIAI解：对作三角分解得41000.931001000.9310 1/0.931000.93 1/0.9333.0000954,310(1,0.9992431,0.9991478)(1,-1,1)0.001.TTur按算法迭代 次，与准确值 的误差小于，与准确值比较，残差乘幂法主要用来求矩阵按模最大的特征值；反幂法主要用来求特征向量。2.2.QRQR方法方法 6060年代出现的年代出现的QRQR算法是目前计算中小算法是目前计算中小型矩阵的型矩阵的全部特征值与特征向量全部特征值与特征向量的最有效的最有效方法。实矩阵、非奇异。方法。实矩阵、非奇异。理论依据理论依据：任一非奇异实矩阵都可分：任一非奇异实矩阵都可分解成一个正交矩阵解成一个正交矩阵Q Q和一个上三角矩阵和一个上三角矩阵R R的的乘积，而且当乘积，而且当R R的对角元符号取定时，分的对角元符号取定时，分解是唯一的。解是唯一的。()(1)(1)(1)11111(2)1111(2)()QR (1,2,).,(2kkkkkkkAQ RkAR QAAAAAQ RQ ARARQQ AQAAAAk基本思想:利用矩阵的分解通过迭代格式将化成相似的上三角阵（或分块上三角阵），从而求出矩阵 的全部特征值与特征向量。由即。于是 即与 相似。同理可得，,3,)。故它们有相同的特征值。一、化一般矩阵为准上三角阵一、化一般矩阵为准上三角阵 111211121222123233311 (2,3,),HouseholdernnnnnnnnniihhhhhhhhHhhhhhhinA称形如 的矩阵为拟上三角阵，也称为海森堡（