硕士生课程 数值分析 第四章矩阵特征值与特征向量的计算

1第四章特征值与特征向量的计算幂法和反幂法2幂法用于计算矩阵按模最大的特征值及其相应的特征向量,特别适用于大型稀疏矩阵.§1幂法和反幂法反幂法用于计算矩阵按模最小的特征值及其特征向量,也可用来计算对应于一个给定近似特征值的特征向量.3设A为n阶实矩阵,其特征值为1,2,…,n,相应的特征向量为u1,u2,…,un.且满足条件n32u1,u2,…,un线性无关.幂法幂法:求1及其相应的特征向量.此时1一定是实数!1通常称为主特征值.14幂法基本思想给定初始非零向量x(0),由矩阵A构造一向量序列)0(1)()1()0(2)1()2()0()1(xAAxxxAAxxAxxkkk在一定条件下,当k充分大时:)()1(1kikixx相应的特征向量为:)1(kx5,1)0(niiiux设1不为零.1111112211211111111)0(1)()1()()(uuuuuuAxAAxxknnknkkniikiiniiikkkk)()1(1kikixxx(k+1)为1的特征向量的近似向量(除一个因子外).对任意向量x(0),有幂法的理论依据故6如果x(0)的选取恰恰使得1=0,幂法仍能进行.因为计算过程中会有舍入误差,迭代若干次后,必然会产生一个向量x(k),它在u1方向上的分量不为零,这样以后的计算就满足所设条件.因为计算过程中可能会出现上溢(|1|1)或下溢成为0(|1|1).为避免出现这一情形,实际计算时每次迭代所求的向量都要归一化.,111)(uxkk7归一化过程设有一向量x0,将其归一化得到向量)max(xxy其中max(x)表示向量x的绝对值最大的分量,即如果有||max||10iniixx.,)max(00小下标量中的最为所有绝对值最大的分且则ixxi例x=(1,－8,7)T,Txxy)875.0,1,125.0()max(则max(x)=－8,归一化向量为8幂法的计算公式kkkkkkkxyxAyx)()()()1()(max任取初始向量x(0)=y(0)0,对k=1,2,…,构造向量序列{x(k)},{y(k)}1k)max(11)(uuyk当k充分大时9),2,1(max)()()()1()(kxyxAyxkkkkkkk定理设n阶实矩阵A有n个线性无关的特征向量u1,u2,…,un,主特征值1满足|1||2||3|…|n|,则对任取非零初始向量x(0)=y(0)0(10),按下述方法构造向量序列{x(k)},{y(k)}则有.lim2,)max(lim1111kkkkuuy10幂法特别适用于求大型稀疏矩阵的主特征值和相应的特征向量.若A的主特征值1为实的m重根,即1=2=…=m,且|1||m+1||m+2|…|n|,又设A有n个线性无关的特征向量,此时幂法仍然适用.幂法的收敛速度取决于比值即比值越接近1,收敛速度越慢,比值越接近0,收敛越快.,1212111limkkk11例用幂法求矩阵210120012A的按模最大的特征值和相应的特征向量.取x(0)=(0,0,1)T,要求误差不超过103.解,1,0,000Txy,2)max(,2,1,0)1(101xAyxTTxy)1,5.0,0(1)1()1(,5.2)max(,5.2,2,5.0)2(2)1()2(xAyxT12389100006049.099909241.29996973.2Txy)1,8.0,2.0(2)2()2(,8.2)max(,8.2,6.2,2.1)3(3)2()3(xAyxT.9996973.2,9990924.2,9972799.2,9918619.2,9756097.2,9285714.2987654.9996973.29113应用幂法计算矩阵A的主特征值的收敛速度主要由比值r=|2/1|来决定,但当r接近于1时,收敛可能很慢.这时可以采用加速收敛的方法.幂法的加速—原点移位法引进矩阵B=A－0I其中0为代选择参数.设A的特征值为1,2,…,n,则B的特征值为1－0,2－0,…,n－0,而且A,B的特征向量相同.14仍设A有主特征值1,且,21取0使得)1(001ii且120101maxii用幂法求矩阵B=A0I的按模最大的特征值1*,则1=1*+0.1－0是B=A0I的主特征值对B应用幂法比对A应用幂法收敛速度快原点移位法15例8.20101350144A矩阵A的特征值为.8.2,3,6321直接应用幂法求矩阵A的主特征值其收敛速度为.2112r用原点移位法求主特征值,取0=2.9,此时收敛速度为.3111.31.00102r16原点移位法使用简便,不足之处在于0的选取十分困难,通常需要对特征值的分布有一大概的了解,才能粗略地估计0,并通过计算不断进行修改.17若{ak}线性收敛于a,即0lim1Caaaakkk当k充分大时，有aaaaaaaakkkk121kkkkkkaaaaaaa12212)(幂法的加速—Aitken加速法18可以证明.0ˆlim,ˆlimaaaaaakkkkk用逼近a,这就是Aitken加速法.kaˆkkkkkkkaaaaaaa12212)(ˆ把上式右端记为kaˆ即比快.aakaakˆ将Aitken方法用于幂法产生的序列{k},可加快幂法的收敛速度.19例用Aitken加速法求矩阵210120012A的按模最大的特征值和相应的特征向量,取x(0)=(0,0,1)T..9918619.2,9756097.2,9285714.2,8.2,5.2,2654321kkkkkkk12212)(ˆ.0004416.3ˆ,0027472.3ˆ,024999.3ˆ,25.3ˆ4321解20反幂法用于计算矩阵按模最小的特征值及其特征向量,也可用来计算对应于一个给定近似特征值的特征向量,是目前求特征向量最有效的方法.反幂法21设A为n阶实可逆矩阵，其特征值满足对应的特征向量分别u1,u2,…,un,则A1的特征值满足||||||121n,||1||1||1121n对应的特征向量分别un,un-1,…,u2,u1.反幂法：计算n以及相应的特征向量.||n||1n反幂法22对于A1应用幂法迭代，可求得矩阵A1的主特征值1/n,从而求得A的按模最小的特征值n.反幂法基本思想23反幂法迭代公式为任取初始向量x(0)=y(0)0,构造向量序列).,2,1,0()max()1()1()1()(1)1(kxxyyAxkkkkk迭代向量x(k+1)可以通过解方程组求得)()1(kkyAxnkx1)max()max()(nnkuuy当k充分大时24定理设A为非奇异矩阵且有n个线性无关的特征向量，其对应的特征值满足||||||121n则对任何初始非零向量x(0)(n0),由反幂法构造的向量序列{x(k)},{y(k)}满足)max(lim)1()(nnkkuuy.1)max(lim)2()(nkkx收敛速度比值为.1nn,0||n25在反幂法中也可用原点移位法来加速迭代过程或求其他特征值及特征向量.设已知A的一个特征值的近似值*,因为*接近,一般应有0|－*||i－*|(i)故－*是矩阵A－*I的按模最小的特征值，比值|(－*)/(i－*)|较小.因此对A－*I用反幂法求－*一般收敛很快，通常只要迭代二、三次就能达到较高的精度.带原点移位的反幂法26原点移位反幂法任取初始向量x(0)=y(0)0,).,2,1,0()max()*()1()1()1()(1)1(kxxyyIAxkkkkk迭代向量x(k+1)可以通过解方程组求得)()1()*(kkyxIA27LUIA*为了节省计算量，可以先对A－*I作三角分解.,)1()1()()1(kkkkzUxyLz已知y(k)求x(k+1)可通过下列方式进行)()1()*(kkyxIA)()1(kkyLUx28原点移位反幂法计算公式任取初始向量x(0)=y(0)0,先对A－*I作三角分解).,2,1,0()max()1()1()1()1()1()()1(kxxyzUxyLzkkkkkkkLUIA*已知y(k)求x(k+1).用下列计算公式构造向量序列{x(k)},{y(k)}29在一定条件下，有所对应的特征向量）为其中uuuykk()max(lim)1()())max(1*,*1)max(lim)2()()(kxxkkk（＋即带原点移位的反幂法是目前求特征向量最有效的方法.30例用反幂法求410131012A的对应于特征值＝1.2679的特征向量.31上机作业•第121页第2题.