第八章 特征值问题的计算方法

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

2、的根的集合：的根的集合：谱集谱集( )A 1212det()() ()()pnnnpIA 其中其中12;()pijnnnnij 称称 为为 的的代数重数代数重数（简称（简称重数重数）；）；ini ()iimnrankIA 为为 的的几何重数几何重数。i iimn 2Def设设 ，n nAC iimn 对于矩阵对于矩阵 的的特征值特征值 ，如果，如果Ai ，则称该特征值，则称该特征值 为为 的一个的一个半单半单特征值。特征值。Ai 若若 的所有特征值都是的所有特征值都是半单半单的，则称的，则称 是是非亏损非亏损的。的。AA是是非亏损非亏损的等价条件是的等价条件是 有有n个个线性无关线性无关的特征

3、向量的特征向量AA3Def设设 ，,n nA BC 若存在矩阵若存在矩阵 ，使得，使得P1B P AP 则称则称 和和 是是相似相似的。的。AB相似相似矩阵有相同的特征值矩阵有相同的特征值1AxxPAP PxPx BPxPx Axx 设设寻求已知矩阵寻求已知矩阵 的的相似相似矩阵矩阵 ，要求：，要求：矩阵矩阵 的的特征值特征值和和特征向量特征向量容易计算容易计算ABB本章本章QR算法的算法的基本思想：基本思想：8 1 1. .Th1(, )iir 设设 ，有，有 r个个互不相同互不相同的特征值的特征值 ，n nAC 其其重数重数分别为分别为 ，则一定存在，则一定存在非奇异非奇异矩阵矩阵11()

4、(),();iiinniikiJdiag JJCir 使得使得（Jordan分解）分解）1(, )in ir n nPC 其中其中112( (), (), ()rP APdiag JJJJ 11()iijiiJ ()jiJ 且除了且除了 的的排列排列次序次序外，外， 是是唯一唯一的。的。J称作称作 的的Jordan标准型标准型AJ8 1 2. .Th设设 ，则存在，则存在酉酉矩阵矩阵 ，使得：，使得：n nAC （Schur分解）分解）其中其中 是是上三角上三角矩阵，且适当选择矩阵，且适当选择 ，可使，可使 的元素的元素HUAUT n nUC TUT按任意指定的顺序排列。按任意指定的顺序排列。

5、8 1 3. .Th设设 ，令，令()n nijAaC （圆盘圆盘定理）定理）/*Disc Theorem*/则则1( ):;,iiiijj iG AzCzaain 12( )( )( )( )nAG AGAGA 8 1 4. .Th设设 为为对称对称矩阵，则存在矩阵，则存在正交正交矩阵矩阵n nAR （谱谱分解定理）分解定理）/*Spectral Decomposition*/其中其中 是是 的的n个特征值。个特征值。n nQR 使得使得1(,)TnQ AQdiag 1,nA8 1 5. .Th设设 为为对称对称矩阵，且矩阵，且 的特征值为的特征值为n nAR （极大极小极大极小定理）定理）

6、其中其中 表示表示 中所有中所有k维子空间的全体。维子空间的全体。则有则有12n A0maxminniTiTuu Auu u 10min maxnn iTTuu Auu u nk nR设设 为为对称对称矩阵，其特征值分别为矩阵，其特征值分别为8 1 6. .Th,n nA BR （Weyl定理）定理）则有则有1212;nn 21 2;, ,iiABin说明：说明：对称对称矩阵的特征值总是矩阵的特征值总是良态良态的。的。注意注意：实际问题中矩阵一般都是由：实际问题中矩阵一般都是由计算计算或或实验实验得到，得到，本身必然存在本身必然存在误差误差，不妨假设，不妨假设 BAA 21 2;, ,iiAi

7、n 2 幂法与幂法与反幂法反幂法/*Power Method and Reversed Power Method*/幂法幂法是计算一个矩阵的是计算一个矩阵的模最大模最大的特征值和对应的特征的特征值和对应的特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为乘幂法乘幂法）。）。 一、一、幂法幂法的的基本思想与算法基本思想与算法假设假设 是可是可对角化对角化的，即的，即 存在如下分解：存在如下分解： n nAC A1AXX 其中其中1(,)ndiag 1;,n nnXxxC 不妨假设不妨假设12n 对于对于0nuC 01122;nniuxxxC011nnkkkjjjjjjjA uA xx 1

8、1121() )njkkjjjxx 011211() )knjkjjkjA uxx 11()x k 01kkkA uu 说明：当说明：当k充分大时充分大时, 的一个的一个近似特征向量近似特征向量为为1 特征向量可以相差一个特征向量可以相差一个倍数倍数01kkkA uu 因为向量因为向量 中含有中含有未知量未知量 ，实际不能计算，实际不能计算1 ku但我们关心的仅是但我们关心的仅是 的的方向方向，故作如下处理：，故作如下处理：0kkkA uu 令令其中其中 为为 的的模最大分量模最大分量k 0kA u11121011121() )() )njkkjjkjnkjkkjjjxxA uxx 11()x

9、kx 幂法迭代幂法迭代算法算法：1kkkAuu 1limlimlimkkkkkkAuu 1Axx 1k For k=1,2,3,1kkyAu kky if1kkuu 输出输出 和和kuk kkkyu 001,uu 设设 和和 均均收敛收敛，由，由算法算法知知kuk 幂法幂法可以计算矩阵的可以计算矩阵的模最大模最大的特征值和对应的特征向量的特征值和对应的特征向量1ku 解：解：Step12 1013 1014A 例例1 1：利用利用幂法幂法求下列矩阵求下列矩阵 的模的模最大的特征值及相应的最大的特征值及相应的特征向量特征向量.A01 1 1()Tu (取初始向量为取初始向量为 )10355()T

10、yAu 15 11131 15()Tyu Step2212311555()TyAu25 222231112525()Tyu Step3321 84 24 92( .)TyAu34 92. 3330 36590 85371( .)Tyu Step4431 58543 92684 8537( .)TyAu 44 8537. 4440 32660 80901( .)Tyu 特征值及相应的特征值及相应的特征向量特征向量精确值精确值为为:4 7321. 0 26790 73201( .)Tu 幂法幂法的收敛性的收敛性：8 2 1. .Th12p 设设 有有 p个个互不相同互不相同的特征值满足：的特征值满

11、足：n nAC 且且模最大模最大特征值特征值 是是半单半单的，如果初始向量的，如果初始向量 在在的特征子空间上的的特征子空间上的投影投影不为零，则由不为零，则由幂法幂法算法产生的算法产生的1 ku向量向量序列序列 收敛到收敛到 的一个特征向量的一个特征向量 ，且，且数值数值1 0u1 1x序列序列 收敛到收敛到 。 k 1 特征特征子空间：子空间： 0Vx Axx 证明：证明：设设 有如下有如下Jordan分解：分解：A11(,)pAXdiag JJX iinniJC 是属于是属于 的的Jordan块构成的块上三角矩阵块构成的块上三角矩阵i 111nJI 是是半单半单的特征值的特征值1 10y

12、X u 令令将将 和和 如下分块：如下分块：yX12(,)TTTTpyyyy 12pnnn12(,)pXXXX 12pnnn1010(,)kkkpA uXdiag JJXu 111222kkkPppX J yX J yX J y 111222kkkpppX yX J yX J y 21112211()()pkkkppJJX yXyXy 0111222kkkkPppA uX J yX J yX J y 021122111()()kpkkppkJA uJX yXyXy 1111110()/()kiiiJJ 01110lim()kkkA uX y 记记11111X yxX y AXXJ 11111A

13、XX JX 11111AX yX y 111Axx 1kkkAuu 011kkkA u 0110kkkkA uA u 1111()kX yukX y 1limkkux 是属于是属于 的一个特征向量的一个特征向量1 1x1kkkAuu 1()kk 几点说明几点说明：定理定理8.2.1条件不满足时，条件不满足时，幂法幂法产生的产生的向量向量序列序列 ku可能有可能有若干若干个收敛于不同向量的个收敛于不同向量的子序列子序列；幂法幂法的收敛的收敛速度速度取决于取决于 的大小；的大小；21: 021122111()()kpkkppkJA uJX yXyXy 加速加速方法：适当选取方法：适当选取 ，对，对

14、 应用应用幂法幂法AI 称之为称之为原点平移法原点平移法1Axx 1Axxxx 1()()AI xx 原点平移法原点平移法不改变不改变矩阵矩阵 的特征向量的特征向量A幂法幂法可以计算第二个可以计算第二个模最大模最大特征值特征值 2 常用常用的方法：的方法：降阶降阶方法（方法（收缩收缩技巧）技巧）设已经计算出设已经计算出模最大模最大特征值特征值 及其特征向量及其特征向量 1 1x111Axx 对向量对向量 ，采用，采用复复的的Household变换计算变换计算酉酉矩阵矩阵1xP11 1Pxe 1111HPAPePAx 1111Px 1 1e 10HPAPB 其中其中 是是n-1阶方阵阶方阵B2

15、为为 的的模最大模最大特征值特征值 B二、二、反幂法的反幂法的基本基本思想与算法思想与算法反幂法反幂法是求一个矩阵的是求一个矩阵的模最小模最小的特征值和对应的特征的特征值和对应的特征 向量的一种向量的一种迭代迭代方法（又称为方法（又称为反迭代法反迭代法）。）。 设设 ，则，则Axx 11A xx 1A 对对 应用应用幂法幂法就可以求得矩阵就可以求得矩阵 的的模最小模最小的特征值和相应的特征向量。的特征值和相应的特征向量。A不妨假设不妨假设 的特征值为的特征值为11nn A则则 的特征值为的特征值为11nn 1A 1ii 反反幂法幂法算法算法：For k=1,2,3,1kkAyz kky if1

16、kkzz 输出输出 和和kzk kkkyz 001,zz limknkzx nnnAxx 若若 和和 均均收敛收敛，由，由幂法幂法知知kzk 1kz limknk 收敛收敛速度速度取决于取决于 的大小的大小1:nn 反反幂法幂法每次迭代都需要每次迭代都需要求解方程组求解方程组1kkAyz 带位移的带位移的反反幂法幂法：实际应用中，实际应用中，反反幂法幂法主要用于求主要用于求特征向量特征向量。且用某种方法已经得到且用某种方法已经得到 的特征值的特征值 的的近似值近似值A1 1 对矩阵对矩阵 采用采用反反幂法幂法迭代格式为：迭代格式为：AI 1 记记假设假设 的特征值满足的特征值满足120n A1

17、()kkAI vz kkkvzv For k=1,2,3,因为方程组的系数矩阵因为方程组的系数矩阵Doolittle分解化为两个分解化为两个三角三角方方是是固定固定的，通常采用的，通常采用( (选主元选主元) )AI 程组求解，从而减少工作量。程组求解，从而减少工作量。AILU 求解方程组求解方程组 化为：化为：1()kkAI vz 1kkkkLyzUvy 带位移的带位移的反反幂法幂法迭代格式：迭代格式： For k=1,2,3,1kkLyz kkUvy kkkvzv 收敛收敛速度速度取决于取决于 的大小的大小12 当当 时，收敛速度会非常快时，收敛速度会非常快1 设矩阵设矩阵 存在存在Doo

18、little分解：分解：AI 解：解：2 1013 1014A 例例2 2：用用带位移的带位移的反反幂法幂法求矩阵求矩阵12679. ）的近似特征向量。）的近似特征向量。33 对应特征值对应特征值 （精确值精确值为为A1 2679. AILU 其中其中1136591027310 1.L 073211000366210000011.U 01 1 1()Tz 10Lyz 1100000636619999.y Step1反反幂法幂法具有一次具有一次“迭代性迭代性”11Uvy 167763938496000018158199.v Step221Lyv 2100001107960073.y 22Uvy

19、220327411488072544673.v 2221 00000 73200 2679.vzv 所求所求近似近似特征向量为：特征向量为：3 Jacobi方法方法Jacobi法：计算法：计算实对称实对称矩阵全部特征值和相应特征向量矩阵全部特征值和相应特征向量 基本基本思想思想对对,n nTARAA Q存在存在正交正交矩阵矩阵 ，满足，满足12(,)TnQ AQdiag 记记12(,)nQq qq 则则1 2;, ,iiiAqq in 寻找寻找正交相似正交相似变换变换 ，将矩阵，将矩阵 约化为约化为对角阵对角阵即可即可QA正交相似正交相似变换求法：通过变换求法：通过Givens变换来实现变换来

20、实现 经典经典Jacobi方法方法设设,n nijijjiAaRaa 令令1122222111( )()()nnniiijFiijj iE AAaa 非对角非对角“范范数数”当当 时，时， 趋于一个趋于一个对角阵对角阵0( )E A A( , , )( , , )TGp qAG p q先来研究一下矩阵先来研究一下矩阵的元素和矩阵的元素和矩阵 的的元素元素之间的之间的关系关系。AGivens变换记为变换记为 ，下面通过，下面通过Givens变换变换( , , )G p q 对矩阵对矩阵 进行进行约化约化，使得，使得0( )E A A例如例如取取424;,npq cos ;sincs记记11a12

21、a24a13a14a13a22a12a23a23a33a34a14a24a34a44a10s000c000100s 0c10s000c000100s 0c11a12a 13a14a13a 23a33a34a10s000c000100s 0c 11a 13a 13a 33a ( )ipipiqbcasa;iqipiqbsaca(, )ip q 11a 13a 13a 33a 222( )pppppqqqbc ascas a 222qqpppqqqbs ascac a22()()pqpqppqqbcsasc aa 选取适当的选取适当的 ，由，由Givens变换将矩阵的变换将矩阵的下三角元素下三角元

22、素 尽可能多的化为尽可能多的化为零零：即：即非对角非对角“范数范数”尽可能的尽可能的小小。如果如果 ，则取，则取0pqa 10;cs否则否则，令，令2tan;qqpppqaastca 2210tt 220()()pqpqppqqbcs asc aa 首先首先由由 确定确定 2210tt 21sgn( )t 14()t 2211111cossectantc ;stc 其次其次确定旋转平面确定旋转平面( , )p q2222211()nniiiiFFiiEBBbAb 由由F-范数的范数的正交不变性正交不变性设设 经过一次经过一次正交相似正交相似变换后变为矩阵变换后变为矩阵AB22222211()n

23、niiiippqqppqqiibaaabb222222222( )( )()( )ppqqppqqpqEBEAaabbEAa 222222ppqqppqqpqaabba 注意注意到到旋转平面旋转平面 的选取方法：的选取方法：( , )p q1maxpqijij naa 经典经典Jacobi方法的迭代格式：方法的迭代格式：101 2 3( );, ,kTkijkkkAaG AGAA k 8 3 1. .Th对于经典对于经典Jacobi方法产生的矩阵序列方法产生的矩阵序列 ， kA存在存在 的特征值的一个排列的特征值的一个排列 满足满足A12,n 12lim(,)knkAdiag 证明见教材证明见

24、教材 经典经典Jacobi方法的迭代算法方法的迭代算法给定矩阵给定矩阵(),ijijjiAaaa 选取选取最佳旋转平面最佳旋转平面 ：( , )p q1maxpqijij naa For k=1,2,3,21sgn( );t 2qqpppqaaa 计算计算211;tc ;stc ipipiqacasa ;iqipiqasaca ,ifip q 计算计算222pppppqqqac ascas a 222;qqpppqqqas ascac a 220()()pqpqppqqacs asc aa ( )E A 直到直到需比较需比较 个元素个元素12()n n 习惯上称习惯上称 次次Jacobi迭代为

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

26、的矩阵逐步约化变换将一个给定的矩阵逐步约化为为上三角上三角矩阵或矩阵或拟上三角拟上三角矩阵的一种矩阵的一种迭代迭代方法方法 QR方法的方法的迭代迭代格式格式设设0n nAAC 令令111ARQ 011AQ R 对矩阵对矩阵 进行进行QR分解分解0A122AQ R 再对矩阵再对矩阵 进行进行QR分解分解1A一、一、QR基本迭代基本迭代方法方法QR方法是目前计算矩阵方法是目前计算矩阵全部全部特征值的特征值的最最有效有效的方的方法之一；具有法之一；具有收敛快收敛快、算法、算法稳定稳定等特点。等特点。一般地有：一般地有：1mmmAQ R 1 2;, ,mmmAR Qm 1HmmmmAQ AQ 矩阵序列

27、矩阵序列 中每一个矩阵都与原矩阵中每一个矩阵都与原矩阵 相似相似 mAAQR方法的迭代算法：方法的迭代算法：1mmmAQ R mmmAR Q For m=1,2,3,直到直到 近似近似为为上三角上三角阵阵mA由由迭代格式迭代格式同时还得到：同时还得到：2112HHHmmmAQQ Q AQQQ HmmmAQ AQ 记记12mmQQQQ 11mmmAQR 代入代入11mmmmQ QRAQ 11mmmmQ QRAQ 等式两端同时右乘等式两端同时右乘21mRR R112121mmmmmmQ QRRR RAQ RR R 记记21kkRRR R 11mmmmQRAQ R 21111111mmmmmmQRA

28、 QRA Q RA mmmAQ R 即即111 1()mmA er q 其中其中 是是 的的第一列第一列， 是是 的相应元素的相应元素1()mq11rmQmR可以看作是对矩阵可以看作是对矩阵 用用 为为1()mqA初始向量的初始向量的幂法幂法所得到的向量。所得到的向量。1eQR方法与方法与幂法幂法的关系：的关系： QR方法的方法的收敛收敛性性8 4 1. .Th设设 的特征值满足的特征值满足 ，且，且 的的LU则由则由QR迭代算法产生的矩阵迭代算法产生的矩阵 的对角线以的对角线以120n Ai ()mmijAa ()miiaY第第i行是行是 对应于对应于 的的左特征左特征向量；若向量；若 有有

29、 分解，分解，AY下的元素趋于下的元素趋于0，同时对角元素，同时对角元素 趋于趋于1(, )iin （QR方法的方法的收敛收敛性质）性质）证明：证明：令令1;XY 1(,)ndiag 则有则有AXY mmmAXYXLU ()mmmXLU ()mmX IEU 其中其中mmmIEL 0limmmE 01(, )iirin且且()mmmAX IEU ()mmQR IEU 1()mmmAQ IRE RRU 1mIRE R 当当m充分大时，充分大时， 存在唯一存在唯一QR分解：分解：1mmmIRE RQ R 01()(, )miirin且且mmQ RI 当当m充分大时充分大时limlimmmmmQRI(

30、)()mmmmAQQR RU QR （QR分解）分解）记记 的的QR分解为：分解为：XQR X为保证上述为保证上述QR分解中上三角矩阵的对角元为分解中上三角矩阵的对角元为正正，令，令111(,)nnDdiag 11211;(,)nnnnuuDdiaguu 11221()()mmmmmmAQQ D DD DR RU mmQ R 由由QR分解唯一性知：分解唯一性知：2112()HHHmHHmmmmmmAQ AQDDQ Q AQQ D D 代入代入11HAXYXXQR R Q 12112()HHmHmmmmADDQ R R Q D D 趋于趋于上三角上三角阵阵实际应用中遇到的多数特征值问题都是关于实

31、际应用中遇到的多数特征值问题都是关于实矩阵实矩阵的，所以自然希望设计只涉及实数运算的的，所以自然希望设计只涉及实数运算的QR迭代。迭代。 实实QR迭代迭代格式格式设设1n nAAR 二、实二、实Schur标准形标准形kkkAQ R 1kkkAR Q For k=1,2,3,为为正交正交矩阵矩阵为为上三角上三角阵阵kQkR8 4 2. .Th（实（实Schur分解）分解）设设n nAR ，则存在，则存在正交正交矩阵矩阵n nQR ，满足：，满足：11121222mmTmmRRRRRQ AQR 其中其中 为为实数实数或具有或具有一对复共轭一对复共轭特征值的特征值的2阶方阵阶方阵iiRiiiiiiR

32、 220()iiiiIR 特征值为特征值为iij ，其中，其中 为为虚单位虚单位j见文献见文献1311121222mmmmRRRRRR矩阵矩阵称为称为 的的Schur标准形标准形A定理定理8.4.2说明：只要求得矩阵的说明：只要求得矩阵的Schur标准形，标准形，就很容易求得矩阵的就很容易求得矩阵的全部全部特征值。特征值。缺陷缺陷： 很难得到很难得到QH 011h21h0022h32h12h0023h33h13h043h21,nh 31,nh 11,nh 41,nh 11,nnh 2,nh3,nh1,nh4,nh1,nnh 22,nh 32,nh 12,nh 0001,n nh ,n nh04

33、2,nh 12,nnh 称下述形状的矩阵为称下述形状的矩阵为上上Hessenberg矩阵矩阵三、上三、上Hessenberg化化设设 ，n nAR 寻求非奇异矩阵寻求非奇异矩阵 ，使得，使得 为上为上Hessenberg 矩阵矩阵，然后再对，然后再对 进行进行 迭代。迭代。1QAQ Q1QAQ QR 基本基本思想思想和和约化约化过程：过程：ijAa 记矩阵记矩阵Q下面采用下面采用Householde变换寻找变换寻找Step1 选取选取Householde变换变换 ，使得，使得1H111Hpe 其中其中1111aAA 令令11100HH 11111111101000aH AHHAH 1111 1

34、111aHHH AH 11a p2A0 2111AH A H 其中其中Step2 选取选取Householde变换变换 ，使得，使得2H221Hqe 下面对作下面对作 同样的处理，以此类推同样的处理，以此类推2A其中其中223AA 令令22100HH 2222322101000H AHAHH 22232HH A H 令令22100HH 1121122122101000aH H AH HHpeAH 111222apeH AH 3232AH A H 其中其中 11a p3A0 0 q0 22222232H A HHH A H 记记2112H H AH H 0 11h21h0 0 22h32h12h

35、 12H H为为正交正交阵阵按照前述方法，经过按照前述方法，经过n-2步后，可以得到：步后，可以得到：221122nnHH H AH HHH 其中其中H 011h21h0022h32h12h0023h33h13h043h21,nh 31,nh 11,nh 41,nh 11,nnh 2,nh3,nh1,nh4,nh1,nnh 22,nh 32,nh 12,nh 0001,n nh ,n nh042,nh 12,nnh 122nPH HH 记记 ，则，则TAPHP 称分解式称分解式 为矩阵为矩阵 的上的上Hessenberg分解分解TAPHP A 上上Hessenberg分解分解算法算法（8.4.

36、1）1 ,( (: , )vhouse A kn k For k=1:n-211(: ,: )() (: ,: )TA kn k nIvvA kn k n 1111( : ,: )( : ,: )()TAn knAn kn Ivv 然后对上然后对上Hessenberg矩阵进行矩阵进行QR迭代迭代设设Hyy TP APyy APyPy 上上Hessenberg矩阵的矩阵的QR迭代算法：迭代算法：1mmmHQ R mmmHR Q For m=1,2,3,直到直到 的的次对角次对角元素趋于元素趋于零零mH注意注意：此时的此时的QR分解可采分解可采用用Givens变换来实现；变换来实现；用用Given

37、s变换得到的变换得到的RQ仍仍然为上然为上Hessenberg矩阵；矩阵；上上Hessenberg分解不唯一。分解不唯一。若上若上Hessenberg矩阵的次对角元素均不为矩阵的次对角元素均不为零零，则称则称之为之为不可约不可约的上的上Hessenberg矩阵。矩阵。7Def定理定理8.4.3说明：在说明：在不可约不可约的条件下，的条件下，上上Hessenberg分解在相差一个分解在相差一个正负号正负号的意义下的意义下唯一唯一。见文献。见文献6 实用的实用的QR迭代算法（仅计算迭代算法（仅计算特征值特征值）Step1 由算法由算法8.4.1计算计算上上Hessenberg矩阵：矩阵：()TAH

38、P AP Step2（QR分解分解） For k=1:n-11 ( ), ( )( , ),(, )c k s kGivens H k k H kk 1111( )( )( :, : )( :, : )( )( )c ks kH k knH k kns kc k Step3（计算（计算RQ）Step4 重复步骤重复步骤Step23，直到，直到下次对角下次对角元素趋于元素趋于零零1111( )( )( : , :)( : , :)( )( )c ks kHn k kHn k ks kc k 四、四、三对角三对角化（化（对称对称矩阵的矩阵的上上Hessenberg化）化）TP APH 设设 为为对

39、称对称矩阵，矩阵， 的的上上Hessenberg分解为分解为n nAR A其中其中 为为对称三对角对称三对角矩阵。矩阵。HStep1 选取选取Householde变换变换 ，使得，使得1H111Hpe 其中其中11111TaAA 令令11100HH 111111111101000TaH AHHHA 11111 1111TaHHH AH 2111AH A H 其中其中 11ap2A0p0111H A H主要主要工作量工作量在于计算在于计算1THIvv 1111()()TTH AHIvvA Ivv 21111TTTTAAvvvv Avv Avv 21111()()TTTTAAv vv Avvv Avv 令令112;()TuAvuv