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

1、 第八章第八章 特征值问题计算特征值问题计算 一、一、特征值特征值和和特征向量特征向量的的基本概念与性质基本概念与性质1 基本概念与性质基本概念与性质1Def设设 ，若存在向量，若存在向量 和复数和复数 满足满足n nAC nxC Axx ，则称，则称 是矩阵是矩阵 的的特征值特征值， 是特征值是特征值 x A 相应的相应的特征向量特征向量。0det()IA ( )det()ApIA 特征特征多项式多项式 的根的集合：的根的集合：谱集谱集( )A ( )max|:( )AA 矩阵矩阵A的特征根模的最大值称为矩阵的特征根模的最大值称为矩阵A的谱半径：的谱半径：于是得到两个特征根分别为：于是得到两

2、个特征根分别为：例例8.1 求矩阵求矩阵A的特征根与特征向量的特征根与特征向量特征特征多项式为：多项式为：3113A 31101301det()detAI 3113det 331()() 268 24()() 对应的特征向量对应的特征向量分别为：分别为：24, 11x 11x 于是得到两个特征根分别为：于是得到两个特征根分别为：例例8.2 求矩阵求矩阵A的特征根与特征向量的特征根与特征向量特征特征多项式为：多项式为：011 0A 01101 001det()detAI 11det 21 对应的特征向量对应的特征向量分别为：分别为：, ii 1xi 1ix 1212det()() ()()pnn

3、npIA 其中其中12;()pijnnnnij 称称 为为 的的代数重数代数重数（简称（简称重数重数）；）；ini ()iimnrankIA 为为 的的几何重数几何重数。i iimn 2Def设设 ，n nAC iimn 对于矩阵对于矩阵 的的特征值特征值 ，如果，如果Ai ，则称该特征值，则称该特征值 为为 的一个的一个半单半单特征值。特征值。Ai 若若 的所有特征值都是的所有特征值都是半单半单的，则称的，则称 是是非亏损非亏损的。的。AA是是非亏损非亏损的等价条件是的等价条件是 有有n个个线性无关线性无关的特征向量的特征向量AA一般的，对矩阵一般的，对矩阵A， 其特征多项式可表示为其特征多

4、项式可表示为3Def设设 ，,n nA BC 若存在矩阵若存在矩阵 ，使得，使得P1B P AP 则称则称 和和 是是相似相似的。的。AB相似相似矩阵有相同的特征值矩阵有相同的特征值1AxxPAP PxPx BPxPx Axx 设设寻求已知矩阵寻求已知矩阵 的的相似相似矩阵矩阵 ，要求：，要求：矩阵矩阵 的的特征值特征值和和特征向量特征向量容易计算容易计算ABB本章本章QR算法的计算算法的计算思想：思想：关于矩阵关于矩阵相似，相似，有后面的结论有后面的结论8 1 1. .Th1(, )iir 设设 ，有，有 r个个互不相同互不相同的特征值的特征值 ，n nAC 其其重数重数分别为分别为 ，则一

5、定存在，则一定存在非奇异非奇异矩阵矩阵11()(),();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 TU

6、T按任意指定的顺序排列。按任意指定的顺序排列。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设设 为为对称对称矩阵，且矩阵，且 的特征值为的特征

7、值为n nAR （极大极小极大极小定理）定理）其中其中 表示表示 中所有中所有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说明：说明：对称对称矩阵的特征值总是矩阵的特征值总是良态良态的。的。注意注意：实际问题中矩阵一般都是由：实际问题中矩阵一般都是由计算计算或或实验实验得到，得到，本身必然存在本身必然存在误差误差，不妨假

8、设，不妨假设 BAA 21 2;, ,iiAin 例例8.3求矩阵求矩阵A的特征根与特征向量的特征根与特征向量150505 15.A 其特征其特征多项式为：多项式为：1 50 5100 5 1 501.det()det.AI 232 于是得到两个特征根分别为：于是得到两个特征根分别为：21, 若取初始向量若取初始向量为：为：001x 先做先做xk+1=A*xk迭代，并计算迭代，并计算| xk+1 | / | xk | 可发现可发现对应的特征向量对应的特征向量分别为：分别为：11x 11x | xk |表示的分量模长的最大值，即取无穷范数表示的分量模长的最大值，即取无穷范数1.500000000

9、000001.666666666666671.800000000000001.888888888888891.941176470588241.969696969696971.984615384615381.992248062015501.996108949416341.998050682261211.99901.99951.99981.99991.9999| xk+1 | / | xk |xk0.5, 1.51.5, 2.53.5, 4.57.5, 8.515.5, 16.531.5,32.563.5,64.5127.5, 128.5255.5, 256.5511.5, 512.51023.5

10、, 1024.52047.5, 2048.54095.5, 4096.58191.5, 8192.51638.4, 1638.5结果表明结果表明| xk+1 | / | xk |收敛到最大特征收敛到最大特征根，根， xk 收敛到对应收敛到对应的特征向量。的特征向量。k123456789101112131415但但xk 的绝对值越来越大，的绝对值越来越大，xk / | xk |即为对应特征即为对应特征向量向量1;1考虑对每次迭代结果归一化，考虑对每次迭代结果归一化，若做如下迭代：若做如下迭代：xk+1=A*xk / | A*xk |则有则有xk 收敛到对应的特征向量，收敛到对应的特征向量，| A

11、*xk |收敛到最大特征根。收敛到最大特征根。1.500000000000001.666666666666671.800000000000001.888888888888891.941176470588241.969696969696971.984615384615381.992248062015501.996108949416341.998050682261211.99901.99951.99981.99991.9999| A*xk | xk0.3333,1.00000.6000,1.00000.7778,1.00000.8824,1.00000.9394,1.00000.9692,1.00

12、000.9845,1.00000.9922,1.00000.9961,1.00000.9980,1.00000.9990,1.00000.9995,1.00000.9998,1.00000.9999,1.00000.9999,1.0000结果表明结果表明| A*xk | 收敛到收敛到A的最大特的最大特征根，征根， xk 收敛到对收敛到对应的特征向量。应的特征向量。k123456789101112131415由此得到幂法的思想：由此得到幂法的思想：任取初始向量任取初始向量x0做以下迭代：做以下迭代：xk+1=A*xk / | A*xk |若干步后，用若干步后，用| A*xk | 作为最大特作为最

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

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

15、用下式迭代，若用下式迭代，收敛性依然成立收敛性依然成立 幂法迭代幂法迭代算法算法：1kkkAuu 1limlimlimkkkkkkAuu 1Axx 1k For k=1,2,3,1kkyAu kky if1kkuu 输出输出 和和kuk kkkyu 001,uu 设设 和和 均均收敛收敛，由，由算法算法知知kuk 幂法幂法可以计算矩阵的可以计算矩阵的模最大模最大的特征值和对应的特征向量的特征值和对应的特征向量1ku 1kkkAuu 因因解：解：Step12 1013 1014A 例例4 4：利用利用幂法幂法求下列矩阵求下列矩阵 的模的模最大的特征值及相应的最大的特征值及相应的特征向量特征向量.

16、A01 1 1()Tu (取初始向量为取初始向量为 )10355()TyAu 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. .

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

18、的块上三角矩阵i 111nJI 是是半单半单的特征值的特征值1 10yX 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()k

19、kkA uX y 记记11111X yxX y AXXJ 11111AXX 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()()kpkkppkJ

20、A uJX yXyXy 加速加速方法：适当选取方法：适当选取 ，对，对 应用应用幂法幂法AI 称之为称之为原点平移法原点平移法1Axx 1Axxxx 1()()AI xx 原点平移法原点平移法不改变不改变矩阵矩阵 的特征向量的特征向量A幂法幂法可以计算第二个可以计算第二个模最大模最大特征值特征值 2 常用常用的方法：的方法：降阶降阶方法（方法（收缩收缩技巧）技巧）设已经计算出设已经计算出模最大模最大特征值特征值 及其特征向量及其特征向量 1 1x根据对称矩阵的性质，有根据对称矩阵的性质，有 1( )AA 令2111111( )( )/()TTAAx xx x 构造如何求出其他如何求出其他特征值

21、特征值 ，及其特征向量，及其特征向量 23, 23,xx102 3,(, ,)Tix xi 2111111111211111110( )( )( )( )( )/()/()TTTTiiiiiiAxA xx x xx xAxA xx xx x xA xx 于是于是 22( )A 因而的最大特征根为，可以用幂法求得。 例例8.5 8.5 用幂法计算 0.225.05.025.00.10.15.00.10.1A的最大特征值和相应的特征向量. 计算过程如表8-1. 表8-1的结果是用8位浮点数字进行运算得到的， 的分量值是舍入值. 于是得到 ku5365323.21及相应的特征向量 和相应的特征向量的

22、真值（8位数字）为 1.)16497.0,74822116.0(T.)164966116.074822116.0(,5365258.211Tx 81m ax ()0(111)1(0 .9 0 9 10 .8 1 8 21)2 .7 5 0 0 0 0 05(0 .7 6 5 10 .6 6 7 41)2 .5 5 8 7 9 1 81 0(0 .7 4 9 40 .6 5 0 81)2 .5 3 8 0 0 2 91 5(0 .7 4 8 30 .6 4 9 71)2 .5 3 6 6 2 5 61 6(0 .7 4 8 30 .6 4 9 71)2 .5 3 6 5 8 4 01 7(0 .

23、7 4 8 20 .6 4 9 71)2 .5 3 6 5 5 9 81 8(0 .7 4 8 20 .6 4 9 71)2Tkkkxv表（ 规 范 化 向 量 ）.5 3 6 5 4 5 61 9(0 .7 4 8 20 .6 4 9 71)2 .5 3 6 5 3 7 42 0(0 .7 4 8 20 .6 4 9 71)2 .5 3 6 5 3 2 3幂法的加速幂法的加速 原点平移法原点平移法 由前面讨论知道，应用幂法计算 的主特征值的收敛速度主要由比值 来决定，但当 接近于1时，收敛可能很慢. A12rr 一个补救的办法是采用加速收敛的方法. 引进矩阵 ,pIAB其中 为选择参数. 设 的特征值为 ，则 的相应特征值为 ，而且 的特征向量相同. pAn,21Bpppn,21BA, 如果要计算 的主特征值 ，就要适当选择 使 仍然是 的主特征值，且使 A1pp1B.1212pp对 应用幂法，使得在计算 的主特征值 的过程中得到加速. 这种方法通常称为原点平移法. BBp1 例例 设 有特征值 44RA),4,3,2, 1(15jjj比值 . 作变换 9.0/12r),12(ppIAB则 的特征值为 B.1,0, 1,24321应用幂法