Chapter9_1_特征值和乘幂法方法

第九章矩阵特征值问题的数值方法(Numericalmethodsforeigenvalueproblems)引言/*Introduction*/工程实践中有多种振动问题，如桥梁或建筑物的振动，机械机件、飞机机翼的振动，工程实践中有多种振动问题，如桥梁或建筑物的振动，机械机件、飞机机翼的振动，及一些稳定性分析和相关分析可转化为求矩阵特征值与特征向量的问题。xxGT1exTG:GoogleMatrix,“theworld’slargestmatrixcomputation”.4,300,000,000x:PageRank（网页级别）vector“The$25,000,000,000Eigenvector”搜索引擎设A是n阶矩阵,x是非零列向量.如果有数λ存在,满足Ax=λx,那么,称x是矩阵A关于特征值λ的特征向量.§1特征值与特征向量/*Eigenvalueandeigenvector*/如果把右端写为λIx，那么又可写为:(λI-A)x=0即|λI-A|=00111||)(aaaAIfnnn记它是关于参数λ的n次多项式，称为矩阵A的特征多项式，其中a0=(-1)n|A|.齐次线性方程组定义1A的特征值也称为A的特征根.显然,当λ是A的一个特征值时,它必然是f(λ)=0的根.反之,如果λ是f(λ)=0的根,那么齐次方程组(λI-A)x=0有非零解向量x,使Ax=λx成立.从而，λ是A的一个特征值.矩阵特征值和特征向量有如下主要性质：n阶矩阵A是降秩矩阵的充分必要条件是A有零特征值.设矩阵A与矩阵B相似，那么它们有相同的特征值.n阶矩阵A与AT有相同的特征值.设λi≠λj是n阶矩阵A的两个互异特征值，x、y分别是其相应的右特征向量和左特征向量，那么，xTy=0.定理1定理2定理3定理4§2Hermite矩阵特征值问题设A为n阶矩阵，其共轭转置矩阵记为AH.如果A=AH，那么，A称为Hermite矩阵一、Hermite矩阵的有关性质设是Hermite矩阵A的n个特征值.有以下性质:n,,,21全是实数.n,,,21有相应的n个线性无关的特征向量，它们可以化为一组标准酉交的特征向量组,即nuuu,,,21ijjHiuu是酉空间中的一组标准酉交基.nuuu,,,21记U=(),它是一个酉阵，即UHU=UUH=I，那么nuuu,,,21DAUUnH1即A与以为对角元的对角阵相似n,,,21A为正定矩阵的充分必要条件是全为正数.n,,,21设是Hermite矩阵A的n个特征值，那么n,,,212222))(()()(AAAAAH因此inimaxA12niiHFAtrAAtrA1222)()(又由inimaxA12niiFA12得niiFA12定理5证明如果A的n个特征值为其相应的标准酉交的特征向量为那么有12...n12,,...,nuuu设A是Hermite矩阵，那么设x是一个非零向量,A是Hermite矩阵,称为矩阵A关于向量x的Rayleigh商，记为R(x).xxAxxHHnxR)(1)(min0,~xRxkCxk)(min0,1~xRxknCxk或定理6定理7二、极值定理(极值定理)设Hermite矩阵的n个特征值为，其相应的标准酉交特征向量为n21nuuu,,,21用Ck表示酉空间Cn中任意的k维子空间，那么)(0,xRminmaxxkCxkCk)(0,11xRmaxminxknCxknCk或定理8矩阵特征值问题的性态是很复杂的，通常分别就单个特征值或整体特征值给出条件数进行分析.对于Hermite矩阵，由于其特征值问题的特殊性质，其特征值都是良态的.下面先证明Hermite矩阵特征值的扰动定理.三、Hermite矩阵特征值问题的性态矩阵特征值问题与求解线性方程组问题一样，都存在当矩阵A的原始数据有小变化(小扰动)时，引起特征值问题的变化有大有小的问题，如果引起的变化小，称该特征值问题是良态的.反之，称为病态的.(扰动定理)设矩阵A,E,A+E都是n阶Hermite矩阵，其特征值分别为,,,那么,1iniin21n21n21设矩阵A关于特征值λ1,λ2,…,λn的标准酉交特征向量为u1,u2,…,un，是由ui,ui+1,…,un生成的n-i+1维子空间.1~inC对中任意非零向量x,由极值定理,有1~inCxxxEAxmaxHHxinCxi)(0,1~xxExxmaxxxAxxmaxHHxinCxHHxinCx0,1~0,1~定理9证明10maxniHiHxCxxAxxx且由定理110maxniHnHxCxxExxx且又由定理，对任意x≠0，有1ii从而有另一方面,A=(A+E)-E.1ini那么，1ii重复上面的过程,可得iin从而有12n为矩阵-E的特征值记•，设矩阵A和A’=A+E都是n阶Hermite矩阵，其特征值分别为和，那么12n12n222iiEE这个定理表明，扰动矩阵E使A的特征值的变化不会超过‖E‖2.一般‖E‖2小，因此，Hermite矩阵特征值是良态的.定理10乘幂法是适用于求一般矩阵按模最大特征值及相应特征向量的算法.§3乘幂法设A是n阶矩阵,其n个特征值按模从大到小排序为||||||21n又假设关于λ1,λ2,…,λn的特征向量v1,v2,…,vn线性无关一、乘幂法任意取定初始向量x0建立迭代公式：)0(122110avavavaxnn1kkAxxnnAvaAvaAvaAxx221101nnnvavava222111nnnvavavaxAAxx2222212110212nknnkkkkkvavavaxAAxx22211101nknnkkvavava)()([12122111故当k→∞时，xk→λ1ka1v1.因此，xk可看成是关于特征值λ1的近似特征向量有一严重缺点，当|1|1（或|1|1时）{vk}中不为零的分量将随k的增大而无限增大，计算机就可能出现上溢（或随k的增大而很快出现下溢）因此，在实际计算时，须按规范法计算，每步先对向量xk进行“规范化”。迭代格式改为:kkkxxzkkAzx1,2,1,0k11ini,,2因为对任意给定的初始向量x0类似地nnvbvbvbxxz221100001Azx||||||||00111AzAzxxz||||00zAzAzkkk||)()(||)()(||1212211121221111nknnknknnkkkvbvbvbvbvbvb当10时1||11kk||||1111vbvbzk按模最大特征值λ1及其相应的特征向量v1的乘幂法的计算公式：当10时1||11kk||||1111vbvbzkkkkxxzkkAzx1,2,1,0kkTkkTkkTkkTkkzzAzzzzxz111若λ1为A的实重根,幂法仍然有效.试用幂法求按模最大的特征值和相应的特征向量31-2-1-432-37A表7.1.1例7.1.1计算结果ku(k)v(k)mk01.000000,1.000000,1.0000001.000000，1.000000，1.0000001.00000018.000000,6.000000,0.0000001.000000，0.750000，0.0000008.00000029.250000,6.000000,-2.7500001.000000，0.648649，-0.2972979.25000039.540541,5.891892,-3.5405411.000000，0.617564，-0.3711059.54054149.594901,5.841360,-3.7308781.000000，0.608798，-0.3888409.59490159.604074,5.824033,-3.7753171.000000，0.606413，-0.3930959.60407469.605429,5.818746,-3.7856991.000000，0.605777，-0.3941219.60542979.605572,5.817228,-3.7781391.000000，0.605777，-0.3943699.60557289.605567,5.816808,-3.7887171.000000，0.605566，-0.3944299.605567例1通过B求λ1-p的速度快于通过A求λ1的速度二、加速方法幂法计算A的特征值λ1的收敛速度主要由决定有特征值λ1-p,λ2-p,…,λn-p21pIAB选择p使λ1-p仍为B的主特征值,且满足2121pp求按模最小特征值及相应特征向量的反幂法,又称为反迭代法.§4反幂法反幂法可以求一个非奇异矩阵A的逆矩阵A-1的按模最小的特征值及相应的特征向量，又可以求A的某个近似特征值相应的特征向量.kkkxxzkkzLUx1kTkkTkkzzxz1)1(,2,1,0kkkzAx11若A非奇异,且Ax=λx,则A-1x=λ-1x因此,求A按模最小特征值就是求A-1按模最大特征值一、λi的近似求法kkkxxzkkzLykkyUx1,2,1,0k若A有特征值λi,λi有近似值:i~kTkkTkkzzxz1)1(先对矩阵进行LU分解IAi~记LUIAi~“半迭代法”的命名也由此而得.二、半迭代法一种选取特殊的初始向量x0的反幂法选取初始向量x0满足‖x0‖∞=1，这时z0=x0对照上页中的第二个式子.可把z0看成满足Le=z0这里，e=(1,1,…,1)T,而z0的各个分量的取值多少是无关重要的这样,在第一个迭代步的计算中,只需求解上页中的上三角方程组Ux1=e.假设IAi~1526315728.0392156862.001588235294.000122280702.000176470588.0335294118.00231.51.11211.23231.59.1IAB例2试用反幂法求矩阵A最接近于的特征值和相应的特征向量9.1~s取Ty)1,1,1(0作半迭代，计算结果如表kz(k)ξk10.3545525270.13819637514.48818892720.934390121-0.56607323115.27844165530.964988873-0.90581441818.76833071240.987366528-0.97954102819.91188109150.997464996-0.99581901219.91188109160.999486949-0.99915282319.98213921900178927.219.16sTzx)1,999152823.0,999486949.0()6(1由于A是对称矩阵，做一次Rayleigh商加速000000047.2),(),()6()6()6()6(vvvAvs与精确值λs=2相比，这次加速有较好效果理论上，实对称矩阵A正交相似于以A的特征值为对角元的对角阵.问题是如何构造这样的正交矩阵呢?Jacobi方法就是通过构造特殊的