第四章矩阵特征值与特征向量的计算

1、1第四章特征值与特征向量的计算第四章特征值与特征向量的计算 幂法和反幂法幂法和反幂法2幂法幂法 用于计算矩阵按模用于计算矩阵按模最大最大的特征值及其相应的的特征值及其相应的特征向量特征向量, 特别适用于大型稀疏矩阵特别适用于大型稀疏矩阵.1幂法和反幂法幂法和反幂法反幂法反幂法 用于计算矩阵按模用于计算矩阵按模最小最小的特征值及其特的特征值及其特征向量征向量, 也可用来计算对应于一个给定近似特征值也可用来计算对应于一个给定近似特征值的特征向量的特征向量.3设设A为为n阶实矩阵阶实矩阵, 其特征值为其特征值为 1, 2, , n, 相应的相应的特特征向量为征向量为u1, u2, , un. 且满足

2、条件且满足条件 n 32 u1, 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不为零不为零.1111

3、112211211111111)0(1)()1()()(uuuuuuAxAAxxknnknkkniikiiniiikkkk )() 1(1kikixx x(k+1)为为 1的特征向量的近似向量的特征向量的近似向量(除一个因子外除一个因子外).对任意向量对任意向量x(0), 有有 幂法的理论依据幂法的理论依据故故6 如果如果x(0)的选取恰恰使得的选取恰恰使得 1=0, 幂法仍能进行幂法仍能进行. 因因为计算过程中会有舍入误差为计算过程中会有舍入误差, 迭代若干次后迭代若干次后, 必然会必然会产生一个向量产生一个向量x(k), 它在它在u1方向上的分量不为零方向上的分量不为零, 这样这样以后的计

4、算就满足所设条件以后的计算就满足所设条件. 因为因为 计算过程中可能会出现上溢计算过程中可能会出现上溢(| 1|1)或下溢成为或下溢成为0 (| 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, 且

5、且 | 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)ma

6、x( ,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 1238910 0006049. 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

7、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(

8、 001 ii 且且120101 max 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 .

9、31 . 00102 r16 原点移位法使用简便原点移位法使用简便, 不足之处在于不足之处在于 0的选取十的选取十分困难分困难, 通常需要对特征值的分布有一大概的了解通常需要对特征值的分布有一大概的了解, 才能粗略地估计才能粗略地估计 0, 并通过计算不断进行修改并通过计算不断进行修改.17若若 ak 线性收敛线性收敛于于a, 即即0lim1 Caaaakkk当当 k 充分大时，有充分大时，有aaaaaaaakkkk 121kkkkkkaaaaaaa 12212)( 幂法的加速幂法的加速Aitken加速法加速法18可以证明可以证明 . 0lim,limaaaaaakkkkk 用用 逼近逼近a,

10、 这就是这就是Aitken加速法加速法. ka kkkkkkkaaaaaaa 12212)(把上式右端记为把上式右端记为ka 即即 比比 快快.aakaak 将将Aitken方法用于幂法产生的序列方法用于幂法产生的序列 k, 可加快可加快幂法的收敛速度幂法的收敛速度.19例例 用用Aitken加速法求矩阵加速法求矩阵 210120012A的按模最大的特征值和相应的特征向量的按模最大的特征值和相应的特征向量, 取取 x(0)=(0, 0, 1)T. .9918619. 2,9756097. 2,9285714. 2, 8 . 2, 5 . 2, 2654321 kkkkkkk 12212)(.0

11、004416. 3,0027472. 3,024999. 3,25. 34321 解解20反幂法反幂法 用于计算矩阵按模用于计算矩阵按模最小最小的特征值及其特的特征值及其特征向量征向量, 也可用来计算对应于一个给定近似特征值也可用来计算对应于一个给定近似特征值的特征向量的特征向量, 是目前求特征向量最有效的方法是目前求特征向量最有效的方法. 反幂法反幂法21设设A为为n阶实可逆矩阵，其特征值为阶实可逆矩阵，其特征值为对应的特征向量分别对应的特征向量分别 u1, u2, , un, 则则A 1的特征值为的特征值为|121 n ,|1|1|1121 n对应的特征向量分别对应的特征向量分别 un,

12、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)可以通过解方程组求得可以通过解方程组求得)

13、()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 在反幂法中也可用在反幂法中也可用原点移位法原点移位法来加速迭代过程来加速迭代过程

14、或求或求其他特征值及特征向量其他特征值及特征向量. 设已知设已知A的一个特征值的一个特征值 的近似值的近似值 *, 因为因为 * 接近接近 , 一般应有一般应有0| * | i * | ( i )故故 *是矩阵是矩阵A *I的按模最小的特征值，比值的按模最小的特征值，比值 |( * )/( i * )|较小较小. 因此对因此对A *I用反幂法用反幂法 求求 *一般收敛很快，通常只要迭代二、三次就一般收敛很快，通常只要迭代二、三次就能达到较高的精度能达到较高的精度. 带原点移位的带原点移位的反幂法反幂法26 原点移位反幂法原点移位反幂法任取初始向量任取初始向量x(0)=y(0) 0, )., 2

15、 , 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作三角分解作三角分

16、解 )., 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的对应于特征

17、值的对应于特征值 1.2679的特征向量的特征向量.31第五章第五章 插值法插值法 Lagrange插值插值 Newton插值插值 Newton向前向后公式向前向后公式 Hermite插值插值 样条插值样条插值32 为什么需要插值为什么需要插值? 函数表达式复杂函数表达式复杂, 不便于计算和进行理论分析不便于计算和进行理论分析; 没有函数表达式没有函数表达式, 只给出离散样点只给出离散样点. 找简单函数近似找简单函数近似, 即函数逼近即函数逼近. 函数逼近常用方法函数逼近常用方法: 插值法插值法, 曲线拟合法曲线拟合法. 插值法插值法: 多项式插值多项式插值, 三角多项式插值三角多项式插值.3

18、3 已知函数已知函数 f (x)在区间在区间 a, b上上 (n+1) 个不同点个不同点 x0, x1, x2, , xn 处的函数值处的函数值 yi= f (xi) (i=0, 1, 2, n), 求函数求函数 n(x), 使其满足使其满足(1) n(x)为至多为至多n次多项式，即次多项式，即(2) 满足插值条件满足插值条件nnnxaxaxaax 2210)( )., 1 , 0()()(niyxfxiiin n(x): 插值多项式插值多项式xi : 插值节点插值节点 a, b: 插值区间插值区间1 Lagrange插值插值34First-order second-order third-o

19、rder几何意义几何意义: n次多项式插值就是过次多项式插值就是过 (n+1)个点个点 (xi, f (xi) (i=0, 1, , n), 作一条多项式曲线作一条多项式曲线 y= n(x)近似曲线近似曲线 y=f(x).35 三个基本问题三个基本问题 插值多项式插值多项式 n(x)是否存在唯一？是否存在唯一？ 若若 n(x)存在存在, 截断误差截断误差 f (x) n(x)=? 如何求如何求 n(x)？36 插值多项式插值多项式 n(x)的存在唯一性的存在唯一性 nnnnnnnnnnnnnnyxaxaxaaxyxaxaxaaxyxaxaxaax2210112121101002020100)(

20、)()( n 次多项式次多项式 n(x)有有(n+1)个待定系数个待定系数ai (i=0, 1, 2, , n), 插值条件插值条件 n(xi)= f (xi)= yi (i=0, 1, 2, , n)也是也是(n+1)个个, 恰好给出恰好给出(n+1)个方程个方程.37 )()()()(11112102102222212110200nnnnnnnnnxfxfxfxfaaaaxxxxxxxxxxxx即即系数矩阵系数矩阵A的行列式是的行列式是Vandermonde行列式，其值为行列式，其值为 njijiijxxA,0,)()det( 当插值节点当插值节点xi (i=0, 1, 2, , n)互不

21、相同时，此行列互不相同时，此行列式不为式不为0, 即系数矩阵即系数矩阵A可逆可逆. 因此因此ai (i=0, 1, 2, , n), 存在唯一，即存在唯一，即 n(x)存在唯一存在唯一.38 插值余项与误差估计插值余项与误差估计)()()(xxfxRnn 截断误差或插值余项截断误差或插值余项定理定理 若若,)()1(baCxfn 则存在则存在 (a, b), 使得使得).()()!1()()(10)1(nnnxxxxxxnfxR 证明证明, 0)()()( iniinxxfxR 故故).()()()(10nnxxxxxxxKxR 其中其中 K (x)是与是与 x有关的待定函数有关的待定函数.如

22、何求如何求 K (x) ?39现把现把x看成是看成是a, b上的固定点上的固定点, 作辅助函数作辅助函数)()()()()()(10nnxtxtxtxKttftF )(0)()()(10 xFxFxFxFn 即即 F(t )在在a, b上有上有 n+2 个零点个零点. 根据根据Rolle定理定理, F (t )在在 F(t )的两个零点之间至少有一个零点的两个零点之间至少有一个零点, 故故 F (t )在在(a, b)内至少有内至少有 (n+1)个零点个零点. 对对F (t )再应用再应用Rolle 定理，定理， 可知可知F (t )在在(a, b)内内至少有至少有 n 个零点个零点. 依此类

23、推依此类推, F(n+1) (t )在在(a, b)内至少内至少有一个零点有一个零点, 记之为记之为 (a, b), 使得使得, 0)()!1(0)()()1()1( xKnfFnn 则则40因此因此.),(,)!1()()()1(xbanfxKn且依赖且依赖 )()()()(10nnxxxxxxxKxR ).()()!1()(10)1(nnxxxxxxnf 若若,)(max1)1(, nnbaxMxf则则| )()( |)!1(| )(|101nnnxxxxxxnMxR 41 当当 n =1时时, 线性插值余项为线性插值余项为).,(),)(2)( )(1010 xxxxxxfxR 当当 n

24、 =2时时, 抛物线插值余项为抛物线插值余项为).,(),)()(6)( )(20210 xxxxxxxxfxR 42求求 L1(x)(1) 至多至多1次多项式次多项式;).1 , 0()()(1 iyxfxLiii(2)已知已知ix1x)(iixfy 1y0 x0y Lagrange方法求插值多项式方法求插值多项式 当用当用Lagrange方法求插值多项式时方法求插值多项式时, 其其n次插次插值多项式记为值多项式记为Ln(x). n=1的情形的情形43x0 x1)()(0010101xxxxyyyxL 10100101yxxxxyxxxx 1100)()(yxlyxl )(0 xl1次多项式

25、次多项式ix1x0 x01)(1xl1次多项式次多项式ix1x0 x01n = 1 线性插值多项式线性插值多项式 L1(x)是过两点是过两点 (x0, y0), (x1, y1)的直线方程的直线方程44已知已知ix1x)(iixfy 1y0 x0y求求 L2(x)(1) 至多至多2次多项式次多项式;).2 , 1 , 0()()(2 iyxfxLiii(2)2x2y 二次插值多项式二次插值多项式45n = 2)()()(2101201xxxxxxxxxl )()()(1202102xxxxxxxxxl )()()()()()()(2211002xfxlxfxlxfxlxL )(2010 xxx

26、x )(0 xl)(1xx )(2xx )(0 xl2次多项式次多项式ix1x0 x012x0)(1xl2次多项式次多项式)(2xl2次多项式次多项式ix1x0 x02x01ix1x0 x02x01 二次插值多项式二次插值多项式46l1(x)f (x1)l2(x)f (x2)l0(x)f (x0)x0 x1x2 二次插值多项式二次插值多项式L2(x)47 二次插值多项式二次插值多项式48已知已知ix2x1xnx)(iixfy 1y2yny0 x0y求求 Ln(x)(1) 至多至多n次多项式次多项式;)., 1 , 0()()(niyxfxLiiin (2)插值节点插值节点插值多项式插值多项式

27、n次次Lagrange插值多项式插值多项式49)()()()()(1100 xlyxlyxlyxlyxLnniin 其中其中 li (x) 为插值为插值基函数基函数)(xlin次多项式次多项式)()()(1110niiiiiiixxxxxxxxxx )(xli)(0 xx )(1xx )(1 ixx)(1 ixx)(nxx ,)()()(0 nijjjijixxxxxl)., 1 , 0(ni ixixnx0 x11x1 ix1 ix00000 n次次Lagrange插值多项式插值多项式50例例 已知函数已知函数 y=lnx 的函数表如下的函数表如下xi2.56492.48492.39792.3026f (xi6391分别用分