数值分析第四章矩阵特征值与特征向量的计算.ppt

1,第四章 特征值与特征向量的计算, 幂法和反幂法,2,幂法 用于计算矩阵按模最大的特征值及其相应的特征向量, 特别适用于大型稀疏矩阵.,1 幂法和反幂法,反幂法 用于计算矩阵按模最小的特征值及其特征向量, 也可用来计算对应于一个给定近似特征值的特征向量.,3,设A为n阶实矩阵, 其特征值为1, 2, , n, 相应的特征向量为u1, u2, , un. 且满足条件,u1, u2, , un线性无关., 幂法, 幂法: 求1及其相应的特征向量.,此时1一定是实数!, 1通常称为主特征值.,4, 幂法基本思想, 给定初始非零向量x(0), 由矩阵A构造一向量序列, 在一定条件下, 当k充分大时:, 相应的特征向量为:,5,设1不为零., x(k+1)为1的特征向量的近似向量(除一个因子外).,对任意向量x(0), 有, 幂法的理论依据,故,6, 如果x(0)的选取恰恰使得1=0, 幂法仍能进行. 因为计算过程中会有舍入误差, 迭代若干次后, 必然会产生一个向量x(k), 它在u1方向上的分量不为零, 这样以后的计算就满足所设条件., 因为 计算过程中可能会出现上溢(|1|1)或下溢成为0 (|1|1). 为避免出现这一情形, 实际计算时每次迭代所求的向量都要归一化.,7, 归一化过程,设有一向量x0, 将其归一化得到向量,其中max(x)表示向量x的绝对值最大的分量, 即如果有,例 x=(1, 8, 7)T,则 max(x)=8 ,归一化向量为,8, 幂法的计算公式, 任取初始向量x(0)=y(0)0, 对k=1, 2, , 构造向量序列 x(k), y(k), 当k充分大时,9,定理 设n阶实矩阵A有n个线性无关的特征向量u1, u2, , un, 主特征值1满足| 1 | |2 | |3 | | n |, 则对任取非零初始向量x(0)=y(0)0 (10), 按下述方法构造向量序列 x(k), y(k),则有,10, 幂法特别适用于求大型稀疏矩阵的主特征值和相应的特征向量., 若A的主特征值1为实的m重根, 即1= 2= m, 且 | 1 | |m+1 | |m+2 | | n |, 又设A有n个线性无关的特征向量, 此时幂法仍然适用., 幂法的收敛速度取决于比值 即 比值越接近1, 收敛速度越慢, 比值越接近0, 收敛越快.,11,例 用幂法求矩阵,的按模最大的特征值和相应的特征向量.,取 x(0)=(0, 0, 1)T, 要求误差不超过103.,解,12,13, 应用幂法计算矩阵A的主特征值的收敛速度主要由比值 r=|2/1|来决定, 但当r接近于1时, 收敛可能很慢. 这时可以采用加速收敛的方法., 幂法的加速原点移位法,引进矩阵 B=A0I 其中0为代选择参数. 设A的特征值为1, 2, , n, 则B的特征值为10, 20, , n0, 而且A, B的特征向量相同.,14, 仍设A有主特征值1, 且,取0使得,且, 用幂法求矩阵B=A0I的按模最大的特征值1*, 则1= 1*+0.,10是B=A0I的主特征值,对B应用幂法比对A应用幂法收敛速度快,原点移位法,15,例,矩阵A的特征值为,直接应用幂法求矩阵A的主特征值其收敛速度为,用原点移位法求主特征值, 取0=2.9, 此时收敛速度为,16, 原点移位法使用简便, 不足之处在于0的选取十分困难, 通常需要对特征值的分布有一大概的了解, 才能粗略地估计0, 并通过计算不断进行修改.,17,若 ak 线性收敛于a, 即,当 k 充分大时，有, 幂法的加速Aitken加速法,18,可以证明, 用 逼近a, 这就是Aitken加速法.,把上式右端记为,即 比 快., 将Aitken方法用于幂法产生的序列k, 可加快幂法的收敛速度.,19,例 用Aitken加速法求矩阵,的按模最大的特征值和相应的特征向量, 取 x(0)=(0, 0, 1)T.,解,20,反幂法 用于计算矩阵按模最小的特征值及其特征向量, 也可用来计算对应于一个给定近似特征值的特征向量, 是目前求特征向量最有效的方法., 反幂法,21,设A为n阶实可逆矩阵，其特征值满足,对应的特征向量分别 u1, u2, , un, 则A1的特征值满足,对应的特征向量分别 un, un-1, , u2, u1., 反幂法：计算n以及相应的特征向量., 反幂法,22, 对于A1应用幂法迭代，可求得矩阵A1的主特征值1/ n, 从而求得A的按模最小的特征值n., 反幂法基本思想,23, 反幂法迭代公式为, 任取初始向量x(0)=y(0)0, 构造向量序列, 迭代向量x(k+1)可以通过解方程组求得, 当k充分大时,24,定理 设A为非奇异矩阵且有n个线性无关的特征向量，其对应的特征值满足,则对任何初始非零向量x(0) (n0), 由反幂法构造的向量序列x(k), y(k)满足, 收敛速度比值为,25, 在反幂法中也可用原点移位法来加速迭代过程或求其他特征值及特征向量., 设已知A的一个特征值 的近似值 *, 因为* 接近, 一般应有 0| * | i* | (i ) 故*是矩阵A*I的按模最小的特征值，比值 |(* )/(i* )|较小. 因此对A*I用反幂法 求*一般收敛很快，通常只要迭代二、三次就能达到较高的精度., 带原点移位的反幂法,26, 原点移位反幂法,任取初始向量x(0)=y(0)0,迭代向量x(k+1)可以通过解方程组求得,27,为了节省计算量，可以先对A*I 作三角分解,已知 y(k) 求 x(k+1) 可通过下列方式进行,28, 原点移位反幂法计算公式,任取初始向量x(0)=y(0)0, 先对A*I作三角分解,已知y(k