数值计算方法（南京大学）第8章矩阵特征值问题

1、数值计算方法数值计算方法【第二版】电子教案【第二版】电子教案科学出版社科学出版社2121世纪高等院校教材电子教案系列世纪高等院校教材电子教案系列南京大学数学系南京大学数学系 林成森教授林成森教授授课教材授课教材数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森3 第第8 8章章 矩阵特征值问题矩阵特征值问题 工程实践中有多种振动问题，如桥梁工程实践中有多种振动问题，如桥梁 或建筑物或建筑物的振动，机械机件、飞机机翼的振动，及的振动，机械机件、飞机机翼的振动，及 一些稳定一些稳定性分析和相关分析可转性分析和相关分析可转 化为求矩阵特征值与特征向化为求矩阵特

2、征值与特征向量的问题。量的问题。 但高次多项式求根精度低但高次多项式求根精度低 , 一般不作为求解方一般不作为求解方法法. 目前的方法是针对矩阵不同的特点给出不同的目前的方法是针对矩阵不同的特点给出不同的有效方法有效方法. ()ijAaAfIAn n nn n矩矩 阵阵的的 特特 征征 值值 是是的的 特特 征征 多多 项项 式式的的个个 零零 点点 . .数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森4本章主要内容：本章主要内容：第一节第一节 特征值的估计和数值稳定性特征值的估计和数值稳定性第二节第二节 幂法和反幂法幂法和反幂法第三节第三节 求矩阵

3、全部特征值的求矩阵全部特征值的QR方法方法数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森5第一节第一节 特征值的估计和数值稳定性特征值的估计和数值稳定性 为为格格希希格格林林圆圆盘盘。则则称称，令令阶阶矩矩阵阵对对定定义义iiiinijjijinnijraZCZZniaraAn ), 2 , 1( ,)(1一、格希格林圆盘一、格希格林圆盘(Gerschgorin(Gerschgorin) )数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森6 nnnnnniniinixxxxaaaaaaaaaxAxAx1111

4、1212111211 ，则则有有最最大大元元为为的的特特征征向向量量规规范范化化使使其其，将将设设有有数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森7二、特征值问题的稳定性二、特征值问题的稳定性内内。为为中中心心的的格格希希格格林林圆圆盘盘必必须须在在以以此此式式说说明明，得得到到因因为为个个方方程程是是其其第第iiinijjijiijnijjjijiiaraanjxxaai 11), 2 , 1( , 1,数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森8第二节第二节 幂法和反幂法幂法和反幂法 求矩阵的按模

5、最大的特征值与相应的特征向量。求矩阵的按模最大的特征值与相应的特征向量。它是通过迭代产生向量序列，由此计算特征值和特它是通过迭代产生向量序列，由此计算特征值和特征向量。征向量。一、幂法一、幂法数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森9 12(1)(2)( )(0)(1)( )( )(1)( )(1)1(1,2, )(1,2, ), ,(1 ,2,),/,ininkkkkkkiinnAininxxxyAykykyyy 设设阶阶实实矩矩阵阵 的的特特征征值值满满足足且且与与相相应应的的特特征征向向量量线线性性无无关关。给给定定初初始始向向量量y由y

6、由迭迭代代公公式式产产生生向向量量序序列列可可以以证证明明，当当 充充分分大大时时，有有相相应应的的特特征征向向量量为为。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森10 ( )(0)( )11 (1,2, )(1,2, , ) , iiiniiixinuninyx 为为简简便便，不不妨妨设设。因因为为线线性性无无关关，故故必必存存在在 个个不不全全为为零零的的数数使使得得。()(1)(0)( )( )11()(1)(2)()211211 () ()()nnkkkkikiiiiiikkkknnnyAyA yAxxyxxx 由由数值计算方法【第二版】

7、电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森1111( )( )211()(1)( )(1)1111210,(2,3, ) lim() lim() ( )inkikiiiiikkinkkkikiiiinxxkyxxx 设设由由得得故故只只要要 充充分分大大，就就有有( )(1)1(1)( )(1)1111(1)1( )( )( ) , (1,2,) kikkkkkikikkiyyxyxyinyyyi 因因此此，可可把把作作为为与与相相应应的的特特征征向向量量的的近近似似。由由为为的的第第 个个分分量量。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大

8、学林成森南京大学林成森1221 A 按按上上面面式式子子计计算算矩矩阵阵 按按模模最最大大的的特特征征值值与与相相应应的的特特征征向向量量的的方方法法称称为为幂幂法法。 幂幂法法的的收收敛敛速速度度依依赖赖于于比比值值，比比值值越越小小，收收敛敛越越快快。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森13(0)1()(1)()(1)1111 10, 2,(1)0(1 ) kkkyyxyx 两两点点说说明明：）如如果果的的选选取取恰恰恰恰使使得得幂幂法法计计算算仍仍能能进进行行。因因为为计计算算过过程程中中舍舍入入误误差差的的影影响响，迭迭代代若若干干

9、次次后后，必必然然会会产产生生一一个个向向量量它它在在方方向向上上的的分分量量不不为为零零，这这样样，以以后后的的计计算算就就满满足足所所设设条条件件。）因因计计算算过过程程中中可可能能会会出出现现溢溢出出或或成成为为的的情情形形。解解决决方方法法：每每次次迭迭代代所所求求的的向向量量都都要要归归范范化化。因因此此，幂幂法法实实际际使使用用的的计计算算公公式式是是0012 1( )( )( )()( )( )( )max()(, ,.)kkkkkkkZyyAZCyZyCk数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森141( )( )1 1.(),(

10、,),2 .1,03.max4. 5., ,66.,1, 3ijnkkkriri nAayyyNkryyCyZyAZCCykNkk ( ( ) )算算法法：输输入入初初始始向向量量误误差差限限 ， 最最大大迭迭代代次次数数 。置置求求整整数数 ，使使， y y计计算算置置若若输输出出停停机机；否否则则，转转若若置置转转 ；否否则则，输输出出失失败败 信信息息，停停机机。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森1503001011212100210120 0 1100 0 101 2200 5 10 52 2 5()()()( )()( )( )

11、()( )( , , ) ,. ( , , ) , ( ,) , ( ,. , ) , ( . ,. ) , TTTTTAyZyyAZCyZCyAZC用用 幂幂 法法 求求 矩矩 阵阵的的 按按 模模最最 大大 的的 特特 征征 值值 和和 相相 应应 的的 特特 征征 向向 量量 。取取例例 ：解解 ： 2 5. , 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森16(8)(7)(8)(9)(8)31(2.7650948, 2.9981848,2.9990924) 2.9990924(0.9219772, 0.9996973,1)(2.843651

12、7, 2.9993946,2.9996973). 2.99969732.99909240.000604910 .2.9996973. yAZCZyAZ 由由故故相相应应特特(1)123121 (2.8436517, 2.9993946,2.9996973) 3,2,11 -1,1 2 .3TxA 征征向向量量为为。事事实实上上， 的的特特征征值值，与与对对应应的的特特征征向向量量为为（，）。此此例例中中比比值值为为数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森17两种特殊情况两种特殊情况:12121112()(1)()11(1)( )1111. 1,

13、 ( ( ) )mmnmkkmmkmknmnmnmAnyxxxx 前前面面假假定定如如果果按按模模最最大大的的特特征征值值有有多多个个，即即幂幂法法是是否否有有效效？（ ）是是重重根根，即即矩矩阵阵 仍仍有有 个个线线性性无无关关的的特特征征向向量量。此此时时有有 显显然然，只只要要1()(1)()11(1)()11(1)12()(), y() mkkmmmmkimkikkxxxxAyyy 不不全全为为零零，当当 充充分分大大时时，就就有有因因也也是是矩矩阵阵 相相应应于于的的特特征征向向量量，故故有有为为相相应应的的特特征征向向量量，即即对对这这种种情情况况幂幂法法仍仍然然有有效效。数值计算

14、方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森18 1213( )(1)(2)(3)( )3112311( )(21)21(1)(2)(2 )2(1)(2)112112(2)211,2( )2, ( 1)()() ()()kkkkknnnkkkkkkikiAnyxxxxykxxxxxxyy （ ）且且矩矩阵阵 有有 个个线线性性无无关关的的特特征征向向量量。由由上上式式可可知知，是是个个摆摆动动序序列列，当当 充充分分大大时时，有有(2)( )(1)1(1)1(2)112( )(1)(2)112(1)( )1(1)111(1)( )11(2)112/ ( 1

15、) ( 1)2 2( 1)kkiikkkkkkkkkkkkkyyyxxyxxyyxyyx 又又由由故故在在这这种种情情况况下下，仍仍可可按按幂幂法法产产生生向向量量序序列列。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森19 12121(1)( )1( )12 nmmnkkkAyAyyAn 综综上上可可知知，当当 的的特特征征值值分分布布为为或或时时，用用幂幂法法可可以以计计算算出出 及及相相应应的的特特征征向向量量。如如果果按按迭迭代代所所得得向向量量序序列列呈呈有有规规律律的的摆摆动动，则则可可能能为为的的情情况况。否否则则应应考考虑虑用用别别的

16、的方方法法求求解解。此此外外，当当矩矩阵阵无无 个个线线性性无无关关的的特特征征量量时时，幂幂法法收收敛敛很很慢慢，亦亦应应考考虑虑改改用用其其他他方方法法。幂幂法法计计算算简简便便易易行行，它它是是求求大大型型稀稀疏疏矩矩阵阵按按模模最最大大特特征征值值的的常常用用方方法法。幂法小结幂法小结数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森20二、幂法的加速 因为幂法的收敛速度是线性的，而且依赖于比值因为幂法的收敛速度是线性的，而且依赖于比值 ,当比值接近于当比值接近于1时，幂法收敛很慢。幂法时，幂法收敛很慢。幂法加速有多种，介绍两种加速有多种，介绍两

17、种。12 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森21( )(1)( )(1)(1)(2)( )211211 ()() ()() iikkkkkkknnnAApIApApIApIyAyyApI ypppxxxpp 1. 原1. 原点点移移位位法法矩矩阵阵 与与的的特特征征值值有有以以下下关关系系：若若是是 的的特特征征值值，则则就就是是的的特特征征值值，而而且且相相应应的的特特征征向向量量不不变变。如如果果对对矩矩阵阵按按计计算算，则则有有数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森22()(1)2

18、11122111211 ()() ()() (2,3, )kkkkknnniiyApI ypppuuuppppppinp 适适当当地地选选取取 ，使使得得且且1ApIpA 这这样样，用用幂幂法法计计算算的的最最大大模模特特征征值值及及相相应应特特征征向向量量的的收收敛敛速速度度比比对对 用用幂幂法法计计算算要要快快。这这种种加加速速收收敛敛的的方方法法称称为为原原点点 平平移移法法。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森23123123221222221121121 00)1(), 2 (2,3,2 ) nnninnnnnnppAppppin

19、pp 原原点点平平移移法法使使用用简简便便，但但 的的选选取取困困难难。在在一一些些简简单单情情形形， 可可估估计计。如如当当矩矩阵阵 的的特特征征值值满满足足（或或时时，取取则则有有且且 11 因因此此，用用原原点点平平移移法法求求可可使使收收敛敛速速度度加加快快。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森24(0)( )(1)(4)4140 51302.9,102.8(1,1,1) ,()6.9140 510.10100.1(3.1000568,2.214326, 0.968766 TkkApAyyApI yApIy - -4 4, ,用用原

20、原点点平平移移法法求求矩矩阵阵 的的按按模模最最大大的的特特征征值值，要要求求误误差差不不超超过过1 10 0 。取取一一按按进进行行计计解解算算： 例例：4(5)54541) 3.1000568(3.0999984,2.2142846, 0.9687501) 3.09999840.000058410y 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森2511232121 3.09999842.95.9999984 (3.0999984,2.2142846, 0.9687501) . 6,3,2.8,1,20.11 3.131TAxAApp 所所以以，

21、矩矩阵阵 的的按按模模最最大大的的特特征征值值为为相相应应的的特特征征向向量量为为 不不难难求求出出， 的的特特征征值值为为若若对对 直直接接用用幂幂法法，则则比比值值而而用用原原点点平平移移法法，则则有有因因此此收收敛敛速速度度明明显显加加快快。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森26 1211222112121 lim 0 ()22kkkkkkkkkkkkkkkkkkkkkkkaaaacaaaaaakaaaaaaaaaaaaaaaaaaaaaAitken 2 2. . A A i i t tk ke en n加加速速如如果果序序列列线线

22、性性收收敛敛到到 ，即即则则当当 充充分分大大时时，有有序序列列比比更更快快地地收收敛敛到到 ，这这就就是是加加速速法法。将将这这一一方方 kC法法用用于于幂幂法法所所产产生生的的序序列列，可可加加快快幂幂法法的的收收敛敛速速度度。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森2710101221002101021 1.(),(,),2 .1,0,0,13.max4. ()5. 26.,77. , ijnririnrAayyyNkryyyCyZyAZyCaaaaaapykN 算算 法法 ：输输 入入初初 始始 向向 量量误误 差差 限限 ， 最最 大

23、大 迭迭 代代 次次 数数。置置求求 整整 数数 ， 使使，计计 算算置置计计 算算若若输输 出出停停 机机 ； 否否 则则 ， 转转若若置置,1,3p kk 转转； 否否 则则 ， 输输 出出 失失 败败 信信 息息 ， 停停 机机 。( (也也 可可 采采 用用 幂幂 法法 迭迭 代代 两两 步步 或或 三三 步步 ， 加加 速速 一一 次次 的的 方方 法法 ）数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森28三、反幂法三、反幂法 反幂法是计算矩阵按模最小的特征值及特征向反幂法是计算矩阵按模最小的特征值及特征向量的方法，也是修正特征值、求相应特

24、征向量的最量的方法，也是修正特征值、求相应特征向量的最有效的方法。有效的方法。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森2911111 , 1 AnnuAAxxxA xA xxAAAAA 设设 为为阶阶非非奇奇异异矩矩阵阵，为为 的的特特征征值值与与相相应应的的特特征征向向量量，即即此此式式表表明明，的的特特征征值值是是 的的特特征征值值的的倒倒数数，而而相相应应的的特特征征向向量量不不变变。因因此此，若若对对矩矩阵阵用用幂幂法法，即即可可计计算算出出的的按按模模最最大大的的特特征征值值，其其倒倒数数恰恰为为的的按按模模最最小小的的特特征征值值。

25、 这这就就是是反反幂幂法法的的基基本本思思想想。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森301( )(1)( )1(1)( ) kkkkkAAAyyyA yyA 因因为为的的计计算算比比较较麻麻烦烦，而而且且往往往往不不能能保保持持矩矩阵阵 的的一一些些好好性性质质（如如稀稀疏疏性性），因因此此，反反幂幂法法在在实实际际运运算算时时以以求求解解方方程程组组 代代替替幂幂法法迭迭代代求求得得，每每迭迭代代一一次次要要解解一一个个线线性性方方程程组组。由由于于矩矩阵阵在在迭迭代代过过程程中中不不变变，故故可可对对 先先进进行行三三角角分分解解，每每

26、次次迭迭代代只只要要解解两两个个三三角角形形方方程程组组。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森31( )( )( )1( )( )( )(1)( )1.2.max, 3. kkkriri nkkkkkAPALUryyCyyZCLWPZUyW 反反幂幂法法计计算算的的主主要要步步骤骤：对对 进进行行三三角角分分解解求求整整数数 ，使使得得计计算算解解方方程程组组数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森32 0 () ()iiijjiiijjiiAAIAI 用用带带原原点点平平移移的的反反幂幂法

27、法来来修修正正特特征征值值，并并求求相相应应的的特特征征向向量量是是非非常常有有效效的的。设设已已知知的的一一个个特特征征值值的的近近似似值值为为，因因接接近近，一一般般有有故故是是矩矩阵阵的的按按模模最最小小的的特特征征值值，且且由由上上式式可可知知，比比值值较较小小。因因此此，对对用用反反幂幂法法求求一一般般收收敛敛很很快快，通通常常只只要要经经过过二二、三三次次迭迭代代就就能能达达到到较较高高的的精精度度。反幂法的一个应用反幂法的一个应用数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森33111.(),(,),2 .1,13.()max5. 11

28、16 .,77.,1,ijnririnrAaxxxNkuP AILUryyyCyZLWZUyWyCyukNkk 算算 法法 ：输输 入入近近 似似 值值 ， 初初 始始 向向 量量误误 差差 限限 ， 最最 大大 迭迭 代代 次次 数数。置置作作 三三 角角 分分 解解 4 4. .求求 整整 数数 ， 使使，计计 算算置置若若则则 置置, ,输输 出出停停 机机 ； 否否 则则 ， 转转若若置置,4u 转转； 否否 则则 ， 输输 出出 失失 败败 信信 息息 ， 停停 机机 。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森34(0)2100210

29、12(0,0,1) . 2.930.9310 2.9300.931010.931000.9310 01000.01/ 0.9 3 1 TAAyAIAI ，用用反反幂幂法法求求矩矩阵阵 接接近近2 2. . 9 93 3的的特特征征值值，并并求求相相应应的的特特征征向向量量，取取对对作作三三角角：分分解解得得例例解解：4931000.931/ 0.9333.0000954,310(1, 0.9992431,0.9991478)(1,-1,1)0.001.TTxr 按按算算法法迭迭代代 次次，与与准准确确值值 的的误误差差小小于于，与与准准确确值值比比较较，残残差差数值计算方法【第二版】电子教案数

30、值计算方法【第二版】电子教案 南京大学林成森南京大学林成森35 第三节第三节 求矩阵全部特征值的求矩阵全部特征值的QR方法方法 6060年代出现的年代出现的QRQR算法是目前计算中小型矩阵的算法是目前计算中小型矩阵的全部特征值与特征向量的最有效方法。全部特征值与特征向量的最有效方法。 理论依据：理论依据：任一非奇异实矩阵都可分解成一个正交矩阵任一非奇异实矩阵都可分解成一个正交矩阵Q Q和一个和一个上三角矩阵上三角矩阵R R的乘积，而且当的乘积，而且当R R的对角元符号取定时，的对角元符号取定时，分解是唯一的。分解是唯一的。 一、求矩阵全部特征值的一、求矩阵全部特征值的QR方法方法数值计算方法【

31、第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森3611 QRQR (1,2,). kkkkkkAQ RkAR QAAA 方方法法的的基基本本思思想想是是利利用用矩矩阵阵的的分分解解通通过过迭迭代代格格式式将将化化成成相相似似的的上上三三角角阵阵（或或分分块块上上三三角角阵阵），从从而而求求出出矩矩阵阵的的全全部部特特征征值值与与特特征征向向量量。111111121112, (2 ,3, ) kAAQ RQARAR QQAQAAAAk 由由即即。于于是是即即与与相相似似。同同理理可可得得，。故故它它们们有有相相同同的的特特征征值值。数值计算方法【第二版】电子教案数值

32、计算方法【第二版】电子教案 南京大学林成森南京大学林成森37 可证，在一定条件下，基本可证，在一定条件下，基本QRQR方法产生的矩方法产生的矩阵序列阵序列A Ak k “ “基本基本”收敛于一个上三角阵（或收敛于一个上三角阵（或分块上三角阵）。即主对角线（或主对角线子块）分块上三角阵）。即主对角线（或主对角线子块）及其以下元素均收敛，主对角线（或主对角线子及其以下元素均收敛，主对角线（或主对角线子块）以上元素可以不收敛。特别的，如果块）以上元素可以不收敛。特别的，如果A A是实对是实对称阵，则称阵，则A Ak k “ “基本基本”收敛于对角矩阵。收敛于对角矩阵。数值计算方法【第二版】电子教案数

33、值计算方法【第二版】电子教案 南京大学林成森南京大学林成森38QR方法的实际计算步骤方法的实际计算步骤HouseholderAHessenbergB 用用阵阵作作正正交交相相似似变变换换上上第第阵阵一一步步.*:* 1kkkGivenkkkBQ RBBR Q 用变换产生迭代序列用变换产生迭代序列第二步第二步12*n 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森39HouseholderAB 用用阵阵作作正正交交相相似似变变换换（对对称称阵阵）三三对对角角阵阵* 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成

34、森40二、化一般矩阵为上二、化一般矩阵为上Hessenberg阵阵111211121222123233311 (2,3,), Househ old e rnnnnnnnnniihhhhhhhhhhhHhhhinA 称称形形如如 的的矩矩阵阵为为上上海海森森堡堡（H H e es ss se en nb be er rg g) )阵阵。如如果果此此对对角角线线元元全全不不为为零零 则则称称该该矩矩阵阵为为不不可可约约的的上上H H e es ss se en nb be er rg g矩矩阵阵。讨讨论论用用变变换换将将一一般般矩矩阵阵相相似似变变换换成成H H e es ss se en nb

35、be er rg g阵阵数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森4111111111 ,1000 01 HouseholderHHH AHHHHHnHouseholder 首首先先，选选取取矩矩阵阵使使得得经经相相似似变变换换后后的的矩矩阵阵的的第第一一列列中中有有尽尽可可能能多多的的零零元元素素。为为此此，应应取取为为如如下下形形式式其其中中为为阶阶矩矩阵阵。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森42111211111221121311212131(,) ,(,) ,TTTnnaa HH A

36、HH aH A Haaaaaaaa 于于是是有有 其其中中222222111111.(, 0) 0,2nnnnTaaAaaHH aH AHn 只只要要取取使使得得就就会会使使得得变变换换后后的的矩矩阵阵的的第第一一列列出出现现个个零零元元。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森432211221222211221000*0100*00*0022, .nnnHouseholderHH H AH HHnnHouseholderHHHHH H AH HHHHHessenberg 同同理理，可可构构造造如如下下列列形形式式矩矩阵阵使使得得* *如如此

37、此进进行行次次，可可以以构构造造个个矩矩阵阵使使得得其其中中为为上上矩矩阵阵AH。特特别别地地，当当 为为实实对对称称矩矩阵阵，则则经经过过上上述述正正交交变变换换后后，变变为为三三对对角角阵阵。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森441221522 23 2105 2 22 2 021002412,022, (2,2)2(1,0)(22,2) :TTTHouseholderAAHouseholderHHu 用用变变换换将将矩矩阵阵 化化成成上上H H e es ss se e例例解解n nb be er rg g阵阵。求求矩矩阵阵满满：足

38、足，数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森4522 22222210442220122222442210000100220022220022TTuuHIu uH 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森462112 100052223201001052 22 222002202102202410022100052510100103222 000223220012220022HH H AH H 于于 是是 有有数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林

39、成森47用用Household方法对矩阵方法对矩阵A作正交相似变换作正交相似变换, 使使A相似与上相似与上Hessenberg阵，算法如下：阵，算法如下：(1)(1)111221111111(1)112,1,2,.,21(1)()()() ) ,()(0,.,0,.,)kkTkknkkkiki kkkkkkkkkkkknkknHIUUsign aaaUaaa ，计算计算数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森481(2)kHAA计计算算 (1)11(1),1,11()21,nkjlljlkkkijijjijk kntuaiknaat u （ ）

40、（ ）(1)11(1)1,.,1(1)(2)1,.,nkiilll kkkijijijinta ujknaat u 1(3)kAHA计计算算 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森49三、上三、上Hessenberg阵的阵的QR分解分解对对上上Hessenberg阵阵只需要将其次对角线上的只需要将其次对角线上的元素约化为零，用元素约化为零，用Given变换比用变换比用Householder变变换更节省计算量。为此先介绍换更节省计算量。为此先介绍Given变换。变换。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南

41、京大学林成森50,11cossin11sincos11 ()i jiRjjin n阶阶方方阵阵称称为为平平面面旋旋转转阵阵，或或称称为为G Gi iv ve en ns s变变换换阵阵。定定义义 、平面旋转阵、平面旋转阵(Givens(Givens变换阵变换阵) )数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森511,1,TTi ji ji ji jRRIRRRi i, ,j j平平面面旋旋转转阵阵的的（ ）平平面面旋旋转转阵阵是是非非对对称称交交质质：阵阵性性的的正正。,2Ti ji jRR（ ）也也是是平平面面旋旋转转阵阵。( (3 3) )d

42、de et t( () )= =1 1数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森521,.,Rxxxxi i, ,j jT T1 12 2n n平平面面旋旋转转阵阵的的作作用用：（ ）将将向向量量 = =的的第第j j个个分分量量约约化化为为零零。,cossinsincos1,., ;,i jiijjijkkyRxyxxyxxyxkn ki j, ,若若令令，有有 111,222121212cossinsincoscossinsincosyxRyxxxxxxx ,.,i jRxx xxxT T12n12n左左乘乘向向量量 = =只只改改变变 的的

43、第第i i个个分分量量和和第第j j个个分分量量。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森530tanjjixyx令令，得得2222cossiniiijjjijxxCrxxxxSrxx 所所以以，取取22,0iijijjyCxSxrxxy 于于是是 ,., ,.,0,.,.i jRxxxr xxxxT T1 1i i- -1 1i i+ +1 1j j- -1 1j j+ +1 1n n= =jxix jy调调整整 ，可可将将 约约化化为为零零。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森542,.

44、,xxxxT T1 12 2n n（ ）将将向向量量 = =的的第第i i+ +1 1个个分分量量到到第第n n个个分分量量约约化化为为零零。22,11,., ,0,.,i iiiRxxxrxxrxxT T1 1i i- -1 1i i+ +2 2n n= =,2,122212,., ,0,0,.,i ii iiiiRRxxxrxxrxxxT T1 1i i- -1 1i i+ +3 3n n= =,2,122,., ,0,.,0,i ni ii iinRRRxxxrrxxT T1 1i i- -1 1= =数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林

45、成森55,(3)i ji jiiji jjRAARAARRARAAT TT T左左乘乘 只只改改变变 的的第第i i，j j行行。右右乘乘 只只改改用用对对矩矩阵阵 作作变变换换得得变变 的的第第i i，j j列列。只只改改变变 的的第第i i，j j行行和和到到的的结结第第论论i i，j j列列。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森562,1,4,0,0.xxrT TT T已已知知向向量量 = =，试试用用G Gi iv ve en ns s变变换换将将 约约化化为为例例(1)(1)2,1,4x xxT T：记记 = =，对对计计解解算算

46、C C和和S S。122222121221,55xxCSxxxx1,2(1)(2)1,221055120550015,0,4TRRxx 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森57(2)4,21xS 5 5对对计计算算C C和和S S, ,C C= =2 21 1 (1)1,31,34021010,21,0,04021TRRx 5 52 21 15 52 21 1(2)5,0,4Tx数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森58、用、用 GivensGivens变换对变换对上上Hessenberg

47、阵作阵作QR分解分解(1)(1)(1)11121(1)(1)(1)21222(1)(1)1 1 nnnnnnbbbbbbBbbnGivensBQR 对对上上H essenberg阵H essenberg阵, ,通通常常用用个个变变换换阵阵可可将将它它化化成成上上三三角角矩矩阵阵，从从而而得得到到 的的分分解解式式。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森59(1)211111(2)(2)(2)112131(2)(2)(2)22232(2)(2)(2)1232333(2)(2)1 0(cossin00sincos00(1,2)0011(1,2)

48、nnnnnnnbRrbbbbbbRBBbbbbb 具具体体步步骤骤为为：设设否否则则进进行行下下一一步步），取取旋旋转转矩矩阵阵则则(1)(1)(1)(1)1121111112111 cos, sin, .bbrbbrr 其其中中数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森602322222( 3 )( 3 )( 3 )( 3 )11213111( 3 )( 3 )( 3 )223212( 3 )( 3 )( 3 )333132( 3 )( 3 )4341 0(10cossinsincos (3, 2)11 (3 , 2)nnnnnnnbRrbbb

49、brbbbbbbRBbb （）设设否否 则则 进进 行行 下下 一一 步步 ） ， 再再 取取 旋旋 转转 矩矩 阵阵 则则3( 3 )4( 3 )( 3 )1( 2 )( 2 )( 2 )2( 2 )23222222223222 cos, sin, ()() .nnnnnBbbbbbrbbrr 其其 中中数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森611( )( )( )( )1111111( )( )( )11111( )( )( )1( )( )( )1111( )( )1 (1, ) kkkkkkkknnkkkkkkknknkkkkkknk

50、nkkkkkknknkknnnnBR kk Brbbbbrbbbbhhbbbbb 1k 假假设设上上述述过过程程已已进进行行了了步步，有有数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森62()1()()1()2()21 0,11 (1,)cossinsincos1 cos, sin, ()() .kkkkkkkkkkkkkkkkkkkkkkkkbR kkbbrrrbb 设设取取其其中中数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森63(1)(1)(1)11111(1)(1)1(1)(1)(1)111111(

51、1)(1)(1)21212(1)(1)1 (1, )1kkkkknkkkkkknkkkkkkkknknkkkkkknknkknnnnrbbbrbbR kk BBbhbbhhbbn 于于是是因因此此，最最多多做做次次旋旋转转变变换换，即即( )( )( )( )112131( )( )2232( )33 ( ,1) (2,1)(1,2)nnnnnnnnnnnHR n nR nnRBrbbbrbbRrbr 得得数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森64213212132123( ,1),(2,3, ) 4,() TTTnnTTTnnR i iin

52、HR RRRQRQR RRnQRO nHRQQRQR 因因为为均均为为正正交交矩矩阵阵，故故其其中中仍仍为为正正交交矩矩阵阵。可可算算出出完完成成这这一一过过程程的的运运算算量量约约为为比比一一般般矩矩阵阵的的分分解解的的运运算算量量少少一一个个数数量量级级。可可证证明明仍仍是是上上H H e es ss se en nb be er rg g阵阵，于于是是可可按按上上述述步步骤骤一一直直迭迭代代下下去去，这这样样得得到到的的方方法法的的运运算算量量比比基基本本QR方方法法大大为为减减少少。需需要要说说明明的的是是，通通常常用用方方法法计计算算特特征征值值，然然后后用用反反幂幂法法求求其其相相

53、应应的的特特征征向向量量。数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森6522532644445 (6,4)64 (1,0)(652,4)10 2010.9160250.2773500.8320500.55470020.2773500.08397470.5547000.832050TTTTTQRAAuuuIu u 用用方方法法求求矩矩阵阵的的全全部部特特征征值值。首首先先将将 化化成成上上H H e es ss se en nb be e例例：r rg g：阵阵，取取解解110000.8320500.55470000.5547000.832050H

54、 于于是是 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森6611221111151.3867503.3282007.2111021.2307688.15384000.1538462.230767, 5( 7.21102)8.774964 cos50.56980. sin0.821781 HH AHHAHQRBHrr 即即为为与与 相相似似的的上上H H e es ss se en nb be er rg g阵阵。将将进进行行分分解解，记记取取0.5698030.8217810(2,1)0.8217810.5698030001R 数值计算方法【第二版】电子教案数值计算方法【第二版】电子教案 南京大学林成森南京大学林成森67122222228.7749641.8015968.597089(2,1)00.4383101.91103000.1538462.230767 (0.438310)( 0.153846)0.464526, cos0.4383100.943564, sin0.1538460.