第八章 特征值问题的计算方法[教育研究]

1、 第八章第八章 特征值问题的计算方法特征值问题的计算方法 /*Computational Method of Eigenvalue Problem*/ 本章主要介绍矩阵的本章主要介绍矩阵的特征值特征值和和特征向量特征向量的计算方法。的计算方法。 特征值特征值和和特征向量特征向量的的基本概念与性质基本概念与性质 1 基本概念与性质基本概念与性质 1Def设设 ，若存在向量，若存在向量 和复数和复数 满足满足 n n AC n xC Axx ，则称，则称 是矩阵是矩阵 的的特征值特征值， 是特征值是特征值 x A 相应的相应的特征向量特征向量。 0det()IA ( )det() A pIA 特征

2、特征多项式多项式 的根的集合：的根的集合：谱集谱集 ( )A 1章节课堂 12 12 det()() ()() p n nn p IA 其中其中 12 ;() pij nnnnij 称称 为为 的的代数重数代数重数（简称（简称重数重数）；）； i n i () ii mnrankIA 为为 的的几何重数几何重数。 i ii mn 2Def设设 ， n n AC ii mn 对于矩阵对于矩阵 的的特征值特征值 ，如果，如果A i ，则称该特征值，则称该特征值 为为 的一个的一个半单半单特征值。特征值。A i 若若 的所有特征值都是的所有特征值都是半单半单的，则称的，则称 是是非亏损非亏损的。的。

3、AA 是是非亏损非亏损的等价条件是的等价条件是 有有n个个线性无关线性无关的特征向量的特征向量AA 2章节课堂 3Def设设 ，, n n A BC 若存在矩阵若存在矩阵 ，使得，使得P 1 BP AP 则称则称 和和 是是相似相似的。的。AB 相似相似矩阵有相同的特征值矩阵有相同的特征值 1 AxxPAP PxPx BPxPx Axx 设设 寻求已知矩阵寻求已知矩阵 的的相似相似矩阵矩阵 ，要求：，要求： 矩阵矩阵 的的特征值特征值和和特征向量特征向量容易计算容易计算 AB B 本章本章QR算法的算法的基本思想：基本思想： 3章节课堂 8 1 1. .Th 1(, ) i ir 设设 ，有，

4、有 r个个互不相同互不相同的特征值的特征值 ， n n AC 其其重数重数分别为分别为 ，则一定存在，则一定存在非奇异非奇异矩阵矩阵 1 1()(),(); ii i nn iiki Jdiag JJCir 使得使得 （Jordan分解）分解） 1(, ) i n ir n n PC 其中其中 1 12 ( (), (), () r P APdiag JJJJ 1 1 () i i ji i J () ji J 且除了且除了 的的排列排列 次序次序外，外， 是是唯一唯一的。的。J 称作称作 的的Jordan标准型标准型A J 4章节课堂 8 1 2. .Th 设设 ，则存在，则存在酉酉矩阵矩阵

5、 ，使得：，使得： n n AC （Schur分解）分解） 其中其中 是是上三角上三角矩阵，且适当选择矩阵，且适当选择 ，可使，可使 的元素的元素 H UAUT n n UC TUT 按任意指定的顺序排列。按任意指定的顺序排列。 8 1 3. .Th 设设 ，令，令 () n n ij AaC （圆盘圆盘定理）定理）/*Disc Theorem*/ 则则 1( ):;, iiiij j i G AzCzaain 12 ( )( )( )( ) n AG AGAGA 5章节课堂 8 1 4. .Th 设设 为为对称对称矩阵，则存在矩阵，则存在正交正交矩阵矩阵 n n AR （谱谱分解定理）分解定

6、理）/*Spectral Decomposition*/ 其中其中 是是 的的n个特征值。个特征值。 n n QR 使得使得 1 (,) T n Q AQdiag 1, , n A 8 1 5. .Th 设设 为为对称对称矩阵，且矩阵，且 的特征值为的特征值为 n n AR （极大极小极大极小定理）定理） 其中其中 表示表示 中所有中所有k维子空间的全体。维子空间的全体。 则有则有 12n A 0 maxmin n i T iT u u Au u u 1 0 min max n n i T T u u Au u u n k n R 6章节课堂 设设 为为对称对称矩阵，其特征值分别为矩阵，其特征

7、值分别为 8 1 6. .Th , n n A BR （Weyl定理）定理） 则有则有 1212 ; nn 2 1 2;, , ii ABin 说明：说明：对称对称矩阵的特征值总是矩阵的特征值总是良态良态的。的。 注意注意：实际问题中矩阵一般都是由：实际问题中矩阵一般都是由计算计算或或实验实验得到，得到， 本身必然存在本身必然存在误差误差，不妨假设，不妨假设 BAA 2 1 2;, , ii Ain 7章节课堂 2 幂法与幂法与反幂法反幂法/*Power Method and Reversed Power Method*/ 幂法幂法是计算一个矩阵的是计算一个矩阵的模最大模最大的特征值和对应的特

8、征的特征值和对应的特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为乘幂法乘幂法）。）。 一、一、幂法幂法的的基本思想与算法基本思想与算法 假设假设 是可是可对角化对角化的，即的，即 存在如下分解：存在如下分解： n n AC A 1 AXX 其中其中 1 (,) n diag 1 ;, n n n XxxC 不妨假设不妨假设 12n 对于对于 0 n uC 01122 ; nni uxxxC 8章节课堂 0 11 nn kkk jjjjj jj A uA xx 111 2 1 () ) n j kk jj j xx 0 11 2 11 () ) k n j k jjk j A u x

9、x 11( )x k 0 1 k kk A u u 说明：当说明：当k充分大时充分大时, 的一个的一个近似特征向量近似特征向量为为 1 特征向量可以相差一个特征向量可以相差一个倍数倍数 9章节课堂 0 1 k kk A u u 因为向量因为向量 中含有中含有未知量未知量 ，实际不能计算，实际不能计算 1 k u但我们关心的仅是但我们关心的仅是 的的方向方向，故作如下处理：，故作如下处理： 0 k k k A u u 令令其中其中 为为 的的模最大分量模最大分量 k 0 k A u 111 2 10 111 2 1 () ) () ) n jkk jj k j n kjkk jj j xx A

10、u xx 1 1 () x k x 10章节课堂 幂法迭代幂法迭代算法算法： 1kkk Auu 1 limlimlim kkk kkk Auu 1 Axx 1k For k=1,2,3, 1kk yAu kk y if 1kk uu 输出输出 和和 k u k k k k y u 00 1,uu 设设 和和 均均收敛收敛，由，由算法算法知知 k u k 幂法幂法可以计算矩阵的可以计算矩阵的模最大模最大 的特征值和对应的特征向量的特征值和对应的特征向量 1 k u 11章节课堂 解：解：Step1 2 10 13 1 014 A 例例1 1：利用利用幂法幂法求下列矩阵求下列矩阵 的模的模 最大的

11、特征值及相应的最大的特征值及相应的特征向量特征向量. A 0 1 1 1()Tu (取初始向量为取初始向量为 ) 10 355()TyAu 1 5 1 1 1 3 1 1 5 ()T y u Step2 21 2311 5 55 () T yAu 2 5 2 2 2 2311 1 2525 () Ty u 12章节课堂 Step3 32 1 84 24 92( .) T yAu 3 4 92. 3 3 3 0 36590 85371( .) Ty u Step4 43 1 58543 92684 8537( .) T yAu 4 4 8537. 4 4 4 0 32660 80901( .)

12、Ty u 特征值及相应的特征值及相应的特征向量特征向量精确值精确值为为: 4 7321. 0 26790 73201( .) T u 13章节课堂 幂法幂法的收敛性的收敛性： 8 2 1. .Th 12p 设设 有有 p个个互不相同互不相同的特征值满足：的特征值满足： n n AC 且且模最大模最大特征值特征值 是是半单半单的，如果初始向量的，如果初始向量 在在 的特征子空间上的的特征子空间上的投影投影不为零，则由不为零，则由幂法幂法算法产生的算法产生的 1 k u向量向量序列序列 收敛到收敛到 的一个特征向量的一个特征向量 ，且，且数值数值 1 0 u 1 1 x 序列序列 收敛到收敛到 。

13、 k 1 特征特征子空间：子空间： 0Vx Axx 14章节课堂 证明：证明：设设 有如下有如下Jordan分解：分解： A 1 1 (,) p AXdiag JJX ii nn i JC 是属于是属于 的的Jordan块构成的块上三角矩阵块构成的块上三角矩阵 i 1 11n JI 是是半单半单的特征值的特征值 1 1 0 yX u 令令 将将 和和 如下分块：如下分块： y X 12 (,) TTTT p yyyy 12p nnn 12 (,) p XXXX 12p nnn 1 010 (,) kkk p A uXdiag JJXu 111222 kkk Ppp X J yX J yX J

14、y 15章节课堂 111222 kkk ppp X yX J yX J y 2 11122 11 ()() p kkk pp J J X yXyXy 0111222 kkkk Ppp A uX J yX J yX J y 02 1122 111 ()() k p kk ppk J A uJ X yXyXy 11 111 10()/()k iii JJ 0 11 1 0lim() k k k A u X y 16章节课堂 记记 11 1 11 X y x X y AXXJ 11111 AXX JX 11111 AX yX y 111 Axx 1k k k Au u 0 11 k kk A u 0

15、1 1 0 kk k k A u A u 11 11 () k X y uk X y 1 lim k k ux 是属于是属于 的一个特征向量的一个特征向量 1 1 x 1kkk Auu 1( ) k k 17章节课堂 几点说明几点说明： 定理定理8.2.1条件不满足时，条件不满足时，幂法幂法产生的产生的向量向量序列序列 k u 可能有可能有若干若干个收敛于不同向量的个收敛于不同向量的子序列子序列； 幂法幂法的收敛的收敛速度速度取决于取决于 的大小；的大小； 21 : 02 1122 111 ()() k p kk ppk J A uJ X yXyXy 加速加速方法：适当选取方法：适当选取 ，对

16、，对 应用应用幂法幂法 AI 称之为称之为原点平移法原点平移法 1 Axx 1 Axxxx 1 ()()AI xx 原点平移法原点平移法不改变不改变 矩阵矩阵 的特征向量的特征向量 A 18章节课堂 幂法幂法可以计算第二个可以计算第二个模最大模最大特征值特征值 2 常用常用的方法：的方法：降阶降阶方法（方法（收缩收缩技巧）技巧） 设已经计算出设已经计算出模最大模最大特征值特征值 及其特征向量及其特征向量 1 1 x 111 Axx 对向量对向量 ，采用，采用复复的的Household变换计算变换计算酉酉矩阵矩阵 1 x P 111 Pxe 11 1 1 H PAPePAx 11 1 1 Px

17、1 1 e 1 0 H PAP B 其中其中 是是n-1阶方阵阶方阵B 2 为为 的的模最大模最大特征值特征值 B 19章节课堂 二、二、反幂法的反幂法的基本基本思想与算法思想与算法 反幂法反幂法是求一个矩阵的是求一个矩阵的模最小模最小的特征值和对应的特征的特征值和对应的特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为反迭代法反迭代法）。）。 设设 ，则，则Axx 1 1 A xx 1 A 对对 应用应用幂法幂法就可以求得矩阵就可以求得矩阵 的的 模最小模最小的特征值和相应的特征向量。的特征值和相应的特征向量。 A 不妨假设不妨假设 的特征值为的特征值为 11nn A 则则 的特征值

18、为的特征值为 11nn 1 A 1 i i 20章节课堂 反反幂法幂法算法算法： For k=1,2,3, 1kk Ayz kk y if 1kk zz 输出输出 和和 k z k k k k y z 00 1,zz lim kn k zx nnn Axx 若若 和和 均均收敛收敛，由，由幂法幂法知知 k z k 1 k z lim kn k 收敛收敛速度速度取决于取决于 的大小的大小 1 : nn 反反幂法幂法每次迭代都需要每次迭代都需要 求解方程组求解方程组 1kk Ayz 21章节课堂 带位移的带位移的反反幂法幂法： 实际应用中，实际应用中，反反幂法幂法主要用于求主要用于求特征向量特征向

19、量。 且用某种方法已经得到且用某种方法已经得到 的特征值的特征值 的的近似值近似值 A 1 1 对矩阵对矩阵 采用采用反反幂法幂法迭代格式为：迭代格式为： AI 1 记记 假设假设 的特征值满足的特征值满足 12 0 n A 1 () kk AI vz k k k v z v For k=1,2,3, 因为方程组的系数矩阵因为方程组的系数矩阵 Doolittle分解化为两个分解化为两个三角三角方方 是是固定固定的，通常采用的，通常采用( (选主元选主元) ) AI 程组求解，从而减少工作量。程组求解，从而减少工作量。 22章节课堂 AILU 求解方程组求解方程组 化为：化为： 1 () kk

20、AI vz 1kk kk Lyz Uvy 带位移的带位移的反反幂法幂法迭代格式：迭代格式： For k=1,2,3, 1kk Lyz kk Uvy k k k v z v 收敛收敛速度速度取决于取决于 的大小的大小 1 2 当当 时，收敛速度会非常快时，收敛速度会非常快 1 设矩阵设矩阵 存在存在Doolittle分解：分解：AI 23章节课堂 解：解： 2 10 13 1 014 A 例例2 2：用用带位移的带位移的反反幂法幂法求矩阵求矩阵 12679. ）的近似特征向量。）的近似特征向量。 33 对应特征值对应特征值 （精确值精确值为为 A 1 2679. AILU 其中其中 1 1365

21、91 027310 1 . . L 0732110 0036621 0000011 . . . U 0 1 1 1()Tz 10 Lyz 1 1 0000 0 6366 1 9999 . . . y Step1 24章节课堂 反反幂法幂法具有一次具有一次“迭代性迭代性” 11 Uvy 1 6776 3938 4960 000 1815 8199 . . . v Step2 21 Lyv 2 1 0000 1 1079 6 0073 . . . y 22 Uvy 2 20327 41 14880 72 5446 73 . . . v 2 2 2 1 0000 0 7320 0 2679 . .

22、. v z v 所求所求近似近似特征向量为：特征向量为： 25章节课堂 3 Jacobi方法方法 Jacobi法：计算法：计算实对称实对称矩阵全部特征值和相应特征向量矩阵全部特征值和相应特征向量 基本基本思想思想 对对, n nT ARAA Q存在存在正交正交矩阵矩阵 ，满足，满足 12 (,) T n Q AQdiag 记记 12 (,) n Qq qq 则则 1 2;, , iii Aqq in 寻找寻找正交相似正交相似变换变换 ，将矩阵，将矩阵 约化为约化为对角阵对角阵即可即可QA 正交相似正交相似变换求法：通过变换求法：通过Givens变换来实现变换来实现 26章节课堂 经典经典Jac

23、obi方法方法 设设, n n ijijji AaRaa 令令 11 2 22 22 111 ( )()() nnn iiij F iij j i E AAaa 非对角非对角“范范 数数” 当当 时，时， 趋于一个趋于一个对角阵对角阵0( )E A A ( , , )( , , ) T Gp qAG p q先来研究一下矩阵先来研究一下矩阵 的元素和矩阵的元素和矩阵 的的元素元素之间的之间的关系关系。A Givens变换记为变换记为 ，下面通过，下面通过Givens变换变换( , , )G p q 对矩阵对矩阵 进行进行约化约化，使得，使得 0( )E A A 27章节课堂 例如例如取取424;

24、,npqcos ;sincs 记记 11 a 12 a 24 a 13 a 14 a 13 a 22 a 12 a 23 a 23 a 33 a 34 a 14 a 24 a 34 a 44 a 1 0 s 00 0 c 00 010 0 s 0c 1 0 s 00 0 c 00 010 0s 0c 11 a 12 a 13 a 14 a 13 a 23 a 33 a 34 a 1 0 s 00 0 c 00 010 0s 0c 11 a 13 a 13 a 33 a ( ) ipipiq bcasa ; iqipiq bsaca (, )ip q 28章节课堂 11 a 13 a 13 a

25、33 a 22 2( ) pppppqqq bc ascas a 22 2 qqpppqqq bs ascac a 22 ()() pqpqppqq bcs asc aa 选取适当的选取适当的 ，由，由Givens变换将矩阵的变换将矩阵的下三角元素下三角元素 尽可能多的化为尽可能多的化为零零：即：即非对角非对角“范数范数”尽可能的尽可能的小小。 如果如果 ，则取，则取0 pq a 10;cs 否则否则，令，令 2 tan; qqpp pq aa s t ca 2 210tt 22 0()() pqpqppqq bcs asc aa 首先首先由由 确定确定 29章节课堂 2 210tt 2 1

26、sgn( ) t 1 4 ()t 22 111 11 cos sec tant c ;stc 其次其次确定旋转平面确定旋转平面( , )p q 22 222 11 ( ) nn iiii FF ii EBBbAb 由由F-范数的范数的正交不变性正交不变性 设设 经过一次经过一次正交相似正交相似变换后变为矩阵变换后变为矩阵AB 222222 11 () nn iiiippqqppqq ii baaabb 30章节课堂 22222222 2( )( )()( ) ppqqppqqpq EBEAaabbEAa 22222 2 ppqqppqqpq aabba 注意注意到到 旋转平面旋转平面 的选取方

27、法：的选取方法：( , )p q 1 max pqij ij n aa 经典经典Jacobi方法的迭代格式：方法的迭代格式： 10 1 2 3 ( ) ;, , kT kijkkk AaG AGAA k 8 3 1. .Th对于经典对于经典Jacobi方法产生的矩阵序列方法产生的矩阵序列 ， k A 存在存在 的特征值的一个排列的特征值的一个排列 满足满足 A 12 , n 12 lim(,) kn k Adiag 证明见教材证明见教材 31章节课堂 经典经典Jacobi方法的迭代算法方法的迭代算法 给定矩阵给定矩阵(), ijijji Aaaa 选取选取最佳旋转平面最佳旋转平面 ：( , )

28、p q 1 max pqij ij n aa For k=1,2,3, 2 1 sgn( ) ;t 2 qqpp pq aa a 计算计算 2 1 1 ; t c ;stc ipipiq acasa ; iqipiq asaca ,ifip q 计算计算 22 2 pppppqqq ac ascas a 22 2; qqpppqqq as ascac a 22 0()() pqpqppqq acs asc aa ( )E A 直到直到 需比较需比较 个元素个元素 1 2 ()n n 32章节课堂 习惯上称习惯上称 次次Jacobi迭代为一次迭代为一次“扫描扫描” 1 2 ()n n 循环循环J

29、acobi方法方法 每一次每一次Jacobi迭代不是去选择迭代不是去选择最佳旋转平面最佳旋转平面， 而是而是直接按照某种直接按照某种预先指定预先指定的顺序来的顺序来“扫描扫描” 自然自然顺序：顺序： 1 21 312 32 42( , )( , ),( , ),( , );( , ),( , ),( , );p qnn 3 43 531( , ),( , ),( , );(, );nnn 按照按照自然自然顺序的循环顺序的循环Jacobi方法是方法是渐进平方渐进平方收敛的收敛的 33章节课堂 4 QR 方方 法法 基本基本思想思想 利用利用正交相似正交相似变换将一个给定的矩阵逐步约化变换将一个给

30、定的矩阵逐步约化 为为上三角上三角矩阵或矩阵或拟上三角拟上三角矩阵的一种矩阵的一种迭代迭代方法方法 QR方法的方法的迭代迭代格式格式 设设 0 n n AAC 令令 111 ARQ 011 AQ R 对矩阵对矩阵 进行进行QR分解分解 0 A 122 AQ R 再对矩阵再对矩阵 进行进行QR分解分解 1 A 一、一、QR基本迭代基本迭代方法方法 QR方法是目前计算矩阵方法是目前计算矩阵全部全部特征值的特征值的最最有效有效 的方的方法之一；具有法之一；具有收敛快收敛快、算法、算法稳定稳定等特点。等特点。 34章节课堂 一般地有：一般地有： 1mmm AQ R 1 2;, , mmm AR Qm

31、1 H mmmm AQ AQ 矩阵序列矩阵序列 中每一个矩阵都与原矩阵中每一个矩阵都与原矩阵 相似相似 m AA QR方法的迭代算法：方法的迭代算法： 1mmm AQ R mmm AR Q For m=1,2,3, 直到直到 近似近似 为为上三角上三角阵阵 m A 由由迭代格式迭代格式同时还得到：同时还得到： 2112 HHH mmm AQQ Q AQQQ H mmm AQ AQ 记记 12mm QQQQ 11mmm AQR 代入代入 11mmmm Q QRAQ 35章节课堂 11mmmm Q QRAQ 等式两端同时右乘等式两端同时右乘 21m RR R 112121mmmmmm Q QRRR

32、 RAQ RR R 记记 21kk RRR R 11mmmm QRAQ R 21 111111 mm mmmm QRA QRA Q RA m mm AQ R 即即 111 1 ()mm A er q 其中其中 是是 的的第一列第一列， 是是 的相应元素的相应元素 1 ()m q 11 r m Q m R 可以看作是对矩阵可以看作是对矩阵 用用 为为 1 ()m q A 初始向量的初始向量的幂法幂法所得到的向量。所得到的向量。 1 e QR方法与方法与幂法幂法的关系：的关系： 36章节课堂 QR方法的方法的收敛收敛性性 8 4 1. .Th 设设 的特征值满足的特征值满足 ，且，且 的的 LU

33、则由则由QR迭代算法产生的矩阵迭代算法产生的矩阵 的对角线以的对角线以 12 0 n A i () m mij Aa ()m ii a Y 第第i行是行是 对应于对应于 的的左特征左特征向量；若向量；若 有有 分解，分解， AY 下的元素趋于下的元素趋于0，同时对角元素，同时对角元素 趋于趋于1(, ) i in （QR方法的方法的收敛收敛性质）性质） 证明：证明：令令 1; XY 1 (,) n diag 则有则有A XY mmm AXYXLU () mmm XLU () m m X IEU 其中其中 mm m IEL 0lim m m E 37章节课堂 01(, ) ii rin且且 ()

34、 mm m AX IEU () m m QR IEU 1 () mm m AQ IRE RRU 1 m IRE R 当当m充分大时，充分大时， 存在唯一存在唯一QR分解：分解： 1 mmm IRE RQ R 01 () (, ) m ii rin且且 mm Q RI 当当m充分大时充分大时 limlim mm mm QRI ()() mm mm AQQR RU QR （QR分解）分解） 记记 的的QR分解为：分解为：XQR X 38章节课堂 为保证上述为保证上述QR分解中上三角矩阵的对角元为分解中上三角矩阵的对角元为正正，令，令 1 1 1 (,) n n Ddiag 11 2 11 ;(,)

35、 nn nn uu Ddiag uu 1 1221 ()() mmmm mm AQQ D DD DR RU mm Q R 由由QR分解唯一性知：分解唯一性知： 2112 () HHHmHHm mmmmm AQ AQDDQ Q AQQ D D 代入代入 11H AXYXXQR R Q 1 2112 () HHmHm mmm ADDQ R R Q D D 趋于趋于上三角上三角阵阵 39章节课堂 实际应用中遇到的多数特征值问题都是关于实际应用中遇到的多数特征值问题都是关于实矩阵实矩阵 的，所以自然希望设计只涉及实数运算的的，所以自然希望设计只涉及实数运算的QR迭代。迭代。 实实QR迭代迭代格式格式

36、设设 1 n n AAR 二、实二、实Schur标准形标准形 kkk AQ R 1kkk AR Q For k=1,2,3, 为为正交正交矩阵矩阵 为为上三角上三角阵阵 k Q k R 8 4 2. .Th（实（实Schur分解）分解） 设设 n n AR ，则存在，则存在正交正交矩阵矩阵 n n QR ，满足：，满足： 11121 222 m mT mm RRR RR Q AQ R 其中其中 为为实数实数或具有或具有一对复共轭一对复共轭 特征值的特征值的2阶方阵阶方阵 ii R 40章节课堂 ii ii ii R 22 0() iiii IR 特征值为特征值为 ii j，其中，其中 为为虚单

37、位虚单位j 见文献见文献13 11121 222 m m mm RRR RR R 矩阵矩阵称为称为 的的Schur标准形标准形A 定理定理8.4.2说明：只要求得矩阵的说明：只要求得矩阵的Schur标准形，标准形， 就很容易求得矩阵的就很容易求得矩阵的全部全部特征值。特征值。 缺陷缺陷： 很难得到很难得到 Q 41章节课堂 H 0 11 h 21 h 0 0 22 h 32 h 12 h 00 23 h 33 h 13 h 0 43 h 21,n h 31,n h 11,n h 41,n h 11,nn h 2,n h 3,n h 1,n h 4,n h 1,nn h 22,n h 32,n

38、h 12,n h 000 1,n n h ,n n h 0 42,n h 12,nn h 称下述形状的矩阵为称下述形状的矩阵为上上Hessenberg矩阵矩阵 三、上三、上Hessenberg化化 42章节课堂 设设 ， n n AR 寻求非奇异矩阵寻求非奇异矩阵 ，使得，使得 为上为上 Hessenberg 矩阵矩阵，然后再对，然后再对 进行进行 迭代。迭代。 1 QAQ Q 1 QAQ QR 基本基本思想思想和和约化约化过程：过程： ij Aa 记矩阵记矩阵Q下面采用下面采用Householde变换寻找变换寻找 Step1 选取选取Householde变换变换 ，使得，使得 1 H 111

39、 Hpe 其中其中 11 11 a A A 令令 1 1 10 0 H H 11 11 1111 1010 00 a H AH HAH 43章节课堂 111 1 1111 aH HH AH 11 a p 2 A 0 2111 AH A H 其中其中 Step2 选取选取Householde变换变换 ，使得，使得 2 H 221 Hqe 下面对作下面对作 同样的处理，以此类推同样的处理，以此类推 2 A 其中其中 2 23 A A 令令 2 2 10 0 H H 222 23 22 1010 00 H A H A HH 22232 HH A H 44章节课堂 令令 2 2 10 0 H H 11

40、 2112 2122 1010 00 a H H AH H HpeAH 11 1222 a peH AH 3232 AH A H 其中其中 11 a p 3 A 0 0 q 0 222 22232 H A H HH A H 记记 2112 H H AH H 0 11 h 21 h 0 0 22 h 32 h 12 h 12 H H 为为正交正交阵阵 45章节课堂 按照前述方法，经过按照前述方法，经过n-2步后，可以得到：步后，可以得到： 221122nn HH H AH HHH 其中其中 H 0 11 h 21 h 0 0 22 h 32 h 12 h 00 23 h 33 h 13 h 0

41、43 h 21,n h 31,n h 11,n h 41,n h 11,nn h 2,n h 3,n h 1,n h 4,n h 1,nn h 22,n h 32,n h 12,n h 000 1,n n h ,n n h 0 42,n h 12,nn h 46章节课堂 122n PH HH 记记 ，则，则 T APHP 称分解式称分解式 为矩阵为矩阵 的上的上Hessenberg分解分解 T APHP A 上上Hessenberg分解分解算法算法（8.4.1） 1 ,( (: , )vhouse A kn k For k=1:n-2 11(: ,: )() (: ,: ) T A kn k

42、nIvvA kn k n 1111( : ,: )( : ,: )() T An knAn kn Ivv 然后对上然后对上Hessenberg矩阵进行矩阵进行QR迭代迭代 设设Hy y T P APyy APyPy 47章节课堂 上上Hessenberg矩阵的矩阵的QR迭代算法：迭代算法： 1mmm HQ R mmm HR Q For m=1,2,3, 直到直到 的的次对角次对角 元素趋于元素趋于零零 m H 注意注意：此时的此时的QR分解可采分解可采 用用Givens变换来实现；变换来实现； 用用Givens变换得到的变换得到的RQ仍仍 然为上然为上Hessenberg矩阵；矩阵； 上上He

43、ssenberg分解不唯一。分解不唯一。 若上若上Hessenberg矩阵的次对角元素均不为矩阵的次对角元素均不为零零， 则称则称之为之为不可约不可约的上的上Hessenberg矩阵。矩阵。 7Def 定理定理8.4.3说明：在说明：在不可约不可约的条件下，的条件下，上上Hessenberg 分解在相差一个分解在相差一个正负号正负号的意义下的意义下唯一唯一。见文献。见文献6 48章节课堂 实用的实用的QR迭代算法（仅计算迭代算法（仅计算特征值特征值） Step1 由算法由算法8.4.1计算计算上上Hessenberg矩阵：矩阵： () T AHP AP Step2（QR分解分解） For k=

44、1:n-1 1 ( ), ( )( , ),(, )c k s kGivens H k k H kk 1111 ( )( ) ( :, : )( :, : ) ( )( ) c ks k H k knH k kn s kc k Step3（计算（计算RQ） Step4 重复步骤重复步骤Step23，直到，直到下次对角下次对角元素趋于元素趋于零零 1111 ( )( ) ( : , :)( : , :) ( )( ) c ks k Hn k kHn k k s kc k 49章节课堂 四、四、三对角三对角化（化（对称对称矩阵的矩阵的上上Hessenberg化）化） T P APH 设设 为为对称

45、对称矩阵，矩阵， 的的上上Hessenberg分解为分解为 n n AR A 其中其中 为为对称三对角对称三对角矩阵。矩阵。 H Step1 选取选取Householde变换变换 ，使得，使得 1 H 111 Hpe 其中其中 111 11 T a A A 令令 1 1 10 0 H H 111 11 1111 1010 00 T a H AH HHA 1111 1 1111 T aH HH AH 2111 AH A H 其中其中 11 a p 2 A 0 p 0 50章节课堂 111 H A H 主要主要工作量工作量在于计算在于计算 1 T HIvv 1111 ()() TT H A HIvvA Ivv 2 1111 TTTT AAvvvv Avv Avv 2 1111 ()() TTTT A