41第一节 幂法和反幂法.ppt

《41第一节 幂法和反幂法.ppt》由会员分享，可在线阅读，更多相关《41第一节 幂法和反幂法.ppt（32页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学学院 信息与计算科学系第四章第四章矩阵特征值及特征向量的计算矩阵特征值及特征向量的计算 工程技术中有多种振动问题工程技术中有多种振动问题,如桥梁或建筑如桥梁或建筑物的振动物的振动,机械零件、飞机机翼的振动机械零件、飞机机翼的振动,及一些及一些稳定性分析和相关分析在数学上都可转化为求矩阵稳定性分析和相关分析在数学上都可转化为求矩阵特征值与特征向量的问题特征值与特征向量的问题.问题的来源问题的来源数学学院 信息与计算科学系二、反幂法二、反幂法一、幂法一、幂法第一节第一节 幂法与反幂法幂法与反幂法三、原点平移法三、原点平移法数学学院 信息与计算科学系幂法幂法计算矩阵的计算矩阵的按模最大的特征值和

2、相应按模最大的特征值和相应 特征向量特征向量的一种向量迭代法。的一种向量迭代法。适用矩阵适用矩阵大型稀疏矩阵大型稀疏矩阵.一、幂法一、幂法数学学院 信息与计算科学系特征值问题及性质特征值问题及性质设矩阵设矩阵A Rnn，特征值问题是求，特征值问题是求 C和和非零向量非零向量x Rn，使，使Ax=x其中其中 是矩阵是矩阵A的的特征值特征值，x是矩阵是矩阵A属于特征属于特征值值 的的特征向量特征向量.数学学院 信息与计算科学系求求A的特征值问题等价于求的特征值问题等价于求A的特征方程的特征方程的根；求的根；求A的属于特征值的属于特征值 的特征向量等价于求的特征向量等价于求非零解非零解.数学学院 信

3、息与计算科学系 设设 为为ARnn的特征值的特征值,x 称为称为A的与特征的与特征值值 相对应的一个特征向量相对应的一个特征向量,即即Ax=x,(x0)则有则有 (1)cx(c0为常数为常数)也是也是 A的与特征值的与特征值 相对相对应的一个特征向量，即应的一个特征向量，即A(cx)=(cx)；(2)k为为Ak的特征值的特征值,且且Akx=kx;数学学院 信息与计算科学系 设设n 阶矩阵阶矩阵A的特征值和相应特征向量为的特征值和相应特征向量为1.幂法的基本思想幂法的基本思想v1,v2,vn其中要求其中要求v1,v2,vn 线性无关，且有线性无关，且有即满足即满足称称 1为为A的的按摸最大特征值

4、按摸最大特征值(也称也称主特征值主特征值).数学学院 信息与计算科学系任取非零向量任取非零向量 ,则则 设设 a1 0,由由A构造向量序列构造向量序列xk其中其中数学学院 信息与计算科学系就得到了就得到了向量序列向量序列即对即对用公式用公式由于由于 xk=Axk-1=Akx0，所以这种生成向量序，所以这种生成向量序列的方法就称为列的方法就称为幂法幂法.数学学院 信息与计算科学系 将向量将向量 xk 整理改写一下为整理改写一下为数学学院 信息与计算科学系由于由于 所以得所以得2.收敛性及幂法迭代公式收敛性及幂法迭代公式前面已知前面已知 故有故有即有即有数学学院 信息与计算科学系就是就是 1 的特

5、征向量的特征向量.而用向量而用向量 xk+1 的第的第i个分量与向量个分量与向量 xk 的第的第i个分个分量之比的极限量之比的极限就是按摸最大特征值就是按摸最大特征值 1.数学学院 信息与计算科学系因此当因此当k充分大时，就可以充分大时，就可以近似得到近似得到按摸最大按摸最大的特征值和对应的特征向量为的特征值和对应的特征向量为这样就得到两个极限这样就得到两个极限从而我们就得到幂法的迭代公式从而我们就得到幂法的迭代公式数学学院 信息与计算科学系幂法的迭代公式幂法的迭代公式为为当当k充分大时，有充分大时，有收敛速度收敛速度取决于比值取决于比值 ,比值越小比值越小,收敛越快收敛越快.数学学院 信息与

6、计算科学系问题是问题是：当：当|1|1时时,xk 所有不为零的分量将随所有不为零的分量将随 k 而趋于而趋于 ,在计算机计算时会造成在计算机计算时会造成“溢出溢出”;而而当当|1|1时时,xk 的分量将随的分量将随 k 而趋于而趋于0,成为成为0向量向量.幂法的迭代公式为幂法的迭代公式为当当k充分大时充分大时,有有3.误差分析误差分析为了避免这个问题，对每一步的为了避免这个问题，对每一步的xk进行规范化，进行规范化，这样就得到了修改计算公式为这样就得到了修改计算公式为数学学院 信息与计算科学系 4.实用计算公式实用计算公式当当k充分大时充分大时,有有其中其中 mk 是向量是向量 yk中中绝对值

7、最大的第一个分量绝对值最大的第一个分量.这这时时xk分量的模最大为分量的模最大为1.数学学院 信息与计算科学系例例1 求矩阵求矩阵的主特征值与其对应的特征向量。的主特征值与其对应的特征向量。解解迭代公式为迭代公式为取取 x0=(0,0,1)T ,则有则有数学学院 信息与计算科学系直到直到k=8 时的计算结果见下表时的计算结果见下表kmk1 2,4,1,4 0.5,1,0.252 4.5,9,7.75 90.5,1,0.86113 5.7222,11.4444,8.36111.44440.5,1,0.73604 5.4621,10.9223,8.230610.92230.5,1,0.75365

8、5.5075,11.0142,8.257611.01420.5,1,0.74946 5.4987,10.9974,8.249410.99740.5,1,0.75017 5.5002,11.0005,8.250111.00050.5,1,0.75008 5.5000,11.0000,8.250011.00000.5,1,0.7500从而得从而得数学学院 信息与计算科学系二、反幂法二、反幂法 反幂法是求反幂法是求非奇异矩阵非奇异矩阵A按模最小的特征值和对按模最小的特征值和对应特征向量应特征向量的方法的方法.设矩阵设矩阵A非奇异非奇异,其特征值为其特征值为 1,2,n,满足满足设相应的特征向量设相应

9、的特征向量v1,v2,vn线性无关，则线性无关，则即即A-1的特征值为的特征值为1/i,对应的特征向量仍为对应的特征向量仍为v1,v2,vn.数学学院 信息与计算科学系 A-1的特征值满足的特征值满足因此因此,对对A-1应用幂法应用幂法,可求出其可求出其主特征值主特征值1/n m k 和和特征向量特征向量 vn xk.从而求得从而求得A的的按模最小按模最小特征值特征值 n 1/mk 和对应的和对应的特征向量特征向量 vn xk，这种方法称为这种方法称为反幂法反幂法.数学学院 信息与计算科学系因为因为A-1的计算比较困难，所以解方程组先对的计算比较困难，所以解方程组先对A进行进行LU分解分解A=

10、LU,此时此时反幂法的迭代公式反幂法的迭代公式为为 对对A-1用幂法的迭代公式用幂法的迭代公式为为数学学院 信息与计算科学系例例2 求矩阵求矩阵按模最小的特征值与其对应的特征向量。按模最小的特征值与其对应的特征向量。解解 A 进行进行LU分解得分解得 数学学院 信息与计算科学系反幂法迭代公式反幂法迭代公式为为数学学院 信息与计算科学系取取 x0=(1,1,1)T,迭代迭代5步的计算结果见下表步的计算结果见下表kmk10.2446,0.5625,-0.27030.5652 0.4348,1,-0.478320.1879,0.9877,-0.87250.98770.1902,1,-0.883430

11、.1520,0.8245,-0.75230.82450.1843,1,-0.912440.1489,0.8134,-0.74260.81340.1831,1,-0.912950.1490,0.8134,-0.74260.81340.1832,1,-0.9130可得可得特征向量特征向量 v3 (0.1832,1,-0.9130)T 3 1/0.8134=1.2294数学学院 信息与计算科学系三、原点平移法三、原点平移法 由前面讨论知道，应用幂法计算由前面讨论知道，应用幂法计算A的按模最大特的按模最大特征值的收敛速度主要由比值征值的收敛速度主要由比值 r=|2/1|来决定，但当来决定，但当r 接近

12、于接近于1时，收敛可能很慢时，收敛可能很慢.这时，一个补救办法是采这时，一个补救办法是采用一种加速收敛的方法用一种加速收敛的方法.其中其中p为参数，设为参数，设A的特征值为的特征值为 i，则，则对矩阵对矩阵B的特征的特征值为值为 i-p，而且而且A,B的特征向量相同的特征向量相同.引进矩阵引进矩阵 B=A-pI.数学学院 信息与计算科学系 如果要计算如果要计算A的按模最大特征值的按模最大特征值 1,只要只要选择合适选择合适的数的数p，使使 1-p为矩阵为矩阵B=A-pI 的按模最大特征值，且的按模最大特征值，且 那么，对矩阵那么，对矩阵B=A-pI应用幂法求其按模最大特征值应用幂法求其按模最大

13、特征值 1-p,收敛速度将会加快收敛速度将会加快.这种通过求这种通过求B=A-pI的按模最的按模最大特征值和特征向量，而得到大特征值和特征向量，而得到A的按模最大特征值和的按模最大特征值和特征向量的方法叫特征向量的方法叫原点平移法原点平移法.对于对于A的特征值的某的特征值的某种分布，它是十分有效的种分布，它是十分有效的.也也可以求其它特征值可以求其它特征值.数学学院 信息与计算科学系 例例1 用用p=5的原点平移法求矩阵的原点平移法求矩阵A的特征值的特征值 及其对应的特征向量，及其对应的特征向量，列表计算三次，取列表计算三次，取x0=(1,0,0)T，保，保留两位小数留两位小数.其中其中对对B

14、应用幂法有应用幂法有 解解 平移有平移有数学学院 信息与计算科学系取取 x0=(1,0,0)T,迭代迭代3步的计算结果见下表步的计算结果见下表kmk1-4.00,-2.00,0.00-4 1,0.50,0.002-4.50,-2.50,-0.50-4.51,056,0.113-4.56,-2.78,-0.89-4.561,0.61,0.20可得可得B的一个特征值为的一个特征值为 m3-4.56=+5-4.56+5=0.44对应的特征向量为对应的特征向量为 v(1,0.61,0.20)T故得故得A的一个特征值为的一个特征值为对应的特征向量为对应的特征向量为 v(1,0.61,0.20)T数学学院

15、 信息与计算科学系 在反幂法中也可以用在反幂法中也可以用原点平移法原点平移法求其它特征值与求其它特征值与其对应的特征向量其对应的特征向量.如果矩阵如果矩阵(A-pI)-1存在，显然其特征值为存在，显然其特征值为 如果如果p是是A的特征值的特征值 j的一个近似值，且设的一个近似值，且设 j与其它与其它特征值是分离的，即有特征值是分离的，即有就是说就是说1/(j-p)是矩阵是矩阵(A-pI)-1的按模最大特征值，即的按模最大特征值，即 j-p是是B=A-pI的按模最小特征值，故可用反幂法计算的按模最小特征值，故可用反幂法计算B的特征值的特征值=j-p 1/mk 及特征向量及特征向量xj，从而求得，

16、从而求得A的一的一个特征值个特征值 j及特征向量及特征向量xj.数学学院 信息与计算科学系 例例2 已知矩阵已知矩阵A的一个近似特的一个近似特征值征值 5，用原点平移法求特征值，用原点平移法求特征值 及其对应的特征向量，列表计算三及其对应的特征向量，列表计算三次，取次，取x0=(1,0,0)T，保留两位小数，保留两位小数.其中其中对对B应用反幂法有应用反幂法有 解解 取取p=5平移有平移有数学学院 信息与计算科学系对对B 进行进行LU分解得分解得 其中其中数学学院 信息与计算科学系取取 x0=(1,0,0)T,迭代迭代3步的计算结果见下表步的计算结果见下表kmk10.50,-3.00,1.00-3 -0.17,1,-0.332-1.92,7.83,-2.507.83-0.25,1,-0.323-1.94,8.10,-2.568.10-0.24,1,-0.32可得可得B的按模最大特征值为的按模最大特征值为 1/m3 1/8.10 0.12=+5-0.12+5=5.12对应的特征向量为对应的特征向量为 v(-0.24,1,-0.32)T故得故得A的一个特征值为的一个特征值为得对应的特征向量为得对应的特征向量为 v(-0.24,1,-0.32)T