矩阵特征值的估计毕业论文

本科毕业设计说明书（论文）第1页共22页1引言随着科学技术的发展和良好性能计算机的日益普及，大规模的计算问题正越来越多的引起人们的重视。而矩阵在科学计算中起着重要作用，所以，矩阵理论与应用越来越受到数学学者、工程技术人员和科技人员的关注。矩阵理论不仅是一门重要的数学理论，而且在数值分析、最优化方法、数学模型等数学分支上有极其重要的应用。由于利用矩阵理论与方法来处理错综复杂的工程问题时，具有表达简洁、对工程问题的实质刻画深刻等特点，因此利用矩阵理论方法来处理工程技术的各种问题越来越受到工程界人士的重视。数值代数和矩阵理论与应用已成为众多科学领域的数学工具。矩阵计算的理论和方法与方程组的求解是矩阵理论的一个重要方向，已经成为经济学、生物学、现代物理学等领域处理数学问题不可缺少的强大工具，成为数学计算的一个重要分支。许多实际问题最后常常归结为一个或一些大型系数矩阵为特殊矩阵的线性方程组的求解问题。随着科学的发展，矩阵理论已被广泛地运用到应用数学、计算机科学、经济学、工程学、系统科学等诸多方面，成为现代科技领域处理大量有限维形式与数量关系的强有力的工具。对矩阵理论的现代研究与系统工程、优化方法及稳定理论、群论、图论等有着密切的相互关系。作为数学中的一个分支，包含了丰富的内容，成为一门最有实用价值的数学理论。特征值问题是矩阵理论的一个主要研究领域，对它的研究具有重要的理论意义和实用价值。许多科学和工程问题如结构力学中的固有频率分析以及控制系统中的稳定性问题，最终都转化为特征值问题。由于特征值问题在许多学科中具有广泛的应用，因此矩阵特征值的界的估计及求解的理论研究等是当今计算数学和科学与工程计算研究领域的重大课题，国际上研究工作也十分活跃，人们开始从各个方面来研究矩阵的特征值。11矩阵的特征值111矩阵特征值问题的概述矩阵的特征值问题既是一个理论上非常有意义的问题，同时又有着广泛的应用。总的来说就是要满足这样一个关系AXX,，X0，C是方阵ACNN的特征值，XCN是与其相适应的特征向量。而奇异值是对任意矩阵来说的不一定本科毕业设计说明书（论文）第2页共22页是方阵，若把矩阵A的共轭转置记作AH，那么A的奇异值就是AAH12的特征值。矩阵A的所有特征值的集合称为矩阵的谱。在矩阵代数中，特征值奇异值问题和矩阵的谱分析条件数问题是密切相关的，它们是矩阵最基本也是最重要的特征，在工程和物理学方面应用也很广泛，具有重要的研究意义和价值。但是对于阶数较高的矩阵，要计算出他的特征值和奇异值是相当困难的，所以估算出他们的范围就显得尤为重要了。从估计的结果来看，所给出的范围越小，精度就越高。而国内外很多学者都在试图估算他们的最小范围，所以这类问题在国际上仍然是一个热点研究问题。预备知识在这里我们将讨论这些内容的初等基础理论，它包括两个方面第一部分是向量，矩阵及运算的定义；第二部分是由向量或矩阵的思想引出的各种概念之间的抽象关系，例如线性相关，列空间等。为了理解后面所提到的算法的描述，必须熟悉矩阵的运算，也要深入掌握矩阵的理论。定义1111设ACNN，若C,0CN，使得A成立，则称为A的特征值，为A的对应特征值的特征向量。将上式的形式改写为IA00这表明特征向量是齐次线性方程组IAX0的非零解，由线性方程组的理论知，为A的特征值的充分必要条件是行列式DETIA0称为矩阵A的特征方程，特征方程的根就是A的特征值。多项式FADETIA称为A的特征多项式，而矩阵IA称为A的特征矩阵。性质1111设ACNN，则FANTRAN11NDETA其中TRAAIINI1为矩阵A的迹。性质1121N阶矩阵A有且仅有N个特征值，其中M重特征值以M个计。然而5次或5次以上的多项式方程一般是没有公式求解的。所以对于阶数较大本科毕业设计说明书（论文）第3页共22页的矩阵，实际上求特征值是非常困难的，因而就要研究特征值的各种近似求法，在第二章与第三章中的幂法和QR算法正是求特征值近似值的基本方法。性质1131设1，2，N为AAIJNN的N个特征值（I未必互异），则TRAI,DETAINI1NI1，显然DETA0当且仅当A具有零特征值。设AAIJCMN，用AAIJ表示以A的元素的共轭复数为元素组成的矩阵，而AHAT称为A的共轭转置矩阵。矩阵的共轭转置运算性质1AHAT2ABHAHBH3KAHKAH4ABHBHAH5AHHA6如果A可逆，则AH1A1H性质1141设为N阶矩阵A的特征值，则1也是矩阵AT的特征值；2为矩阵AH的特征值；3若A非奇异，1为矩阵A1的特征值。112矩阵特征值估计的一些基本方法向量迭代法矩阵A的特征值是它的特征多项式的根。我们知道，阶数超过四次的多项式的根一般不能用有限次运算求得，因而矩阵特征值的计算方法本质上总是迭代的。所谓向量迭代法是指不破坏原始矩阵A，而是利用A进行运算，产生一些迭代向量的求解方法，这类方法大多用来求矩阵的部分特征值（常是较大或较小的一部分）本科毕业设计说明书（论文）第4页共22页和相应的特征向量，特别适用于高阶或稀疏矩阵的情况。变换方法求解特征值问题的变换方法，是利用一系列特殊的变换矩阵（初等下三角矩阵，HOUSEHOLDER矩阵，平面旋转矩阵等），从矩阵A出发逐次进行相似变换，使变换后的矩阵趋于容易求得特征值的特殊形状（对角形，三角形，拟三角形等），更有效的是先将原矩阵A经相似变换约化为特殊形状的中间矩阵（三对角阵，准上三角阵等），然后再对这类特殊形状的中间矩阵逐次进行变换。大多数变换方法用于求解全部特征值问题，其优点是收敛速度快，计算结果精确可靠，但由于原矩阵A被破坏，当A是稀疏时，在运算过程中很难保持矩阵的稀疏性。此外，这类方法调用计算机外部设备也较困难，因而大多数变换方法适宜于求解中小规模的稠密矩阵的全部特征值问题。12本文的研究内容本文主要根据盖尔圆定理来研究矩阵的特征值问题，以及盖尔圆定理的适用范围，如何缩小所求矩阵特征值的范围，对初始矩阵做相似变换时变换矩阵的选取。并且研究了特征值的隔离方法。本文的结构安排如下第一章主要阐述了本文的选题背景和研究意义，总结了前人在特征值估计和特征值包含区域方面的一些重要结论，最后对本文主要研究内容作了一个简单的介绍。第二章求解矩阵特征值的一些具体方法。第三章盖尔圆定理的在矩阵特征值的估计上的应用及举例说明。怎样缩小求解的矩阵的特征值的范围，怎样确定矩阵特征值的变换矩阵及举例。第四章对全文进行总结。2求矩阵特征值的基本方法21幂法与反幂法本科毕业设计说明书（论文）第5页共22页幂法是求方阵的最大特征值及对应特征向量的一种迭代法。首先我们来介绍幂法设AN有N个线性相关的特征向量V1，V2，VN，对应的特征值1，2，N，满足|1|2|N|因为V1，V2，VN为CN的一组基，所以任给X00，NIIIVAX10所以有211111110NIIIKIKNIKKIINIIKINIIIKKVAVAVAVAAVAAXA若A10，则因11I知，当K充分大时AKX01KA1V1CV1是1的特征向量另一方面，记MAXXXI，其中|XI|X|，则当K充分大时，111111111111111010MAXMAXMAXMAXMAXMAXVAVAVAVAXAXAKKKKKK若A10，则因舍入误差的影响，会有某次迭代向量在V1方向上的分量不为0，迭代下去可求得1及对应特征向量的近似值。在实际计算中，若|1|1则|1KA1|，若|1|R1|N|则定理结论仍成立。此时不同初始向量的迭代向量序列一般趋向于1的不同特征向量。幂法的迭代公式1MAXKKKKKAYXXXY逆幂迭代法是幂迭代法的变形，用来计算非奇异矩阵A按模最小特征值及相应特征向量。设A非奇异，且0|2|N|0，VI为I对应的特征向量，I1，2，N。记XV1，V2，VN，若有直接三角分解X1LU（杜利特尔分解），则331序列AK本质收敛于上三角阵，其主对角元素均为A的特征值。上HESSENBERG矩阵的QR方法及带原点平移的QR方法在使用QR方法之前，先A将作正交相似变换化为上HESSENBERG矩阵H，然本科毕业设计说明书（论文）第10页共22页后对H作QR迭代，可大量节省运算量。GIVENS变换记SSIN，CCOS，则CSSCJ为旋转变换正交阵。推广到N维KICSSCKIJ111111,称为GIVENS矩阵或GIVENS变换（旋转变换）。易知JI，K，为正交阵。对上HESSENBERG矩阵用GIVENS变换作QR分解NNNNINIIININIIINNINNIIIIIIHHHHHHHHHHHHHHHHHHCSSCHIIJ,1,11,1,1,1,21,22222111,1112111111,1,令HI1,ISIHIICIHI1,I0，即选择I使右边第I1行第I列元素为0，而H的第I行与第I1行零元素位置上左乘JI，I1，I后仍为0，其他行则不变。（可以证明）这样I1，2，N1共N1次左乘J后H变为上三角阵R。即U定理R，其中UTJN1，N，N1J1，2，1正交，且为下HESSENBERG阵，U为上HESSENBERG阵HURQR分解记H1H，设H1U1R1令H2R1U1，则H2为本科毕业设计说明书（论文）第11页共22页上HESSENBERG阵。此变换约需4N2次乘除和加减运算。一般的有KKKKKKURHRUH1得上HESSENBERG阵列HK。注对N阶上H阵施行几次迭代后，主对角线下的次对角线上会出现小元素近似为0，将上H阵分块，分别使用QR算法这样可节省计算时间且便于并行处理。带原点平移的QR方法若在上述QR迭代中产生得HK都不可约（即不能将HK分块）则可仿照幂法中的原点平移法。取平移量对H1I作QR分解H1IQ1R1，令H2R1Q1I，即IQRHRQIHKKKKKK1K1，2，则K有HKH1A。若I为A的特征值|1|2|N|，则HK的第J个次对角元收敛速度取决于1KJJ。若接近于N收敛将会很快。23实对称矩阵特征值的估计及应用定理1COLLATZ设A为N阶实对称矩阵,XX1,XN是一任意N维向量，记YAX，则至少有A的一个特征值满足MINYIXIMAXYIXI。这一定理形式简单且便于应用，但也有不足，就是它不知道被包含的到底是一个还是哪几个特征值，而且往往所得界限太宽。针对第一个缺点，笔者提出了同步向量的概念，推广了上述定理11。针对后一缺点，笔者指出9可以应用迭代法和基于同步向量的包含定理，获得正矩阵的最大与最小特征值的包含关系。继以上工作。本文给出了任意实对称矩阵最大与最小特征值的可以逐步收敛的又一包含关系，由此进一步给出了矩阵特征值的一种新算法并分析了这种新算法的利弊和计算实例。231实对称矩阵特征值的总体上、下界业已证明，实对称矩阵的特征值全是实数。注意到当A是实对称矩阵时，A2是正定或半正定矩阵；而对适当选取的正数，AI必为正定矩阵，这里I是单位本科毕业设计说明书（论文）第12页共22页阵。又在经过以上两种转换后A2与AI均与A有相同的特征函数族。基于这些事实，以下只讨论正定矩阵。设A是正定矩阵，则AK仍为正定矩阵。记TKTRAKK1,2,N，显然TK1K2KNKK1,2,这里12N是A的N个特征值。定理2TKKK1,2,N构成严格单调下降序列。证明因为TK1K1N1NK1NK设N是A的M重特征值1MN，即NN1NM1NM，则TK1K1NMNMNK11NK1K109995这里T8与T8是A4与A4的所有元素的平方和。除由推论4计算1外，注意到对适当的正数，1亦可由矩阵BIA来估计。若记B的特征值为12N，显然有1N，于是可由推论1、2估计N再转换得1的下界。例2矩阵A同例1，取4，则，B4IA211121110，B83363195853195336685858586则3T161630002853，由此得到1099971。232实对称矩阵最大、最小特征值的包含关系上节只是导出了实对称矩阵最大特征值的上界与最小特征值的下界。至于最大特征值的下界，注意到在寻求N的上界时，我们计算了AK。文5已证明AK的第一列就是与N相应的特征向量XN的似值，这样可以采用以下两种方法之一获得N的下界方法一由瑞利商NAYK,YKYK,YK，K1,2,这里YK是AK的第一列。方法二由COLLATZ定理NLIMKAYKJYKJ至于1的上界，同样可以由A1K的第一列用以上两种方法之一来获取，也可以通过BIA应用以上两种方法之一来获取。例3矩阵A同例1，由A4与A4的表达式可以求得AY4532,531,1031T，于是由瑞利商又得349960。而由式得348364。类似地因本科毕业设计说明书（论文）第14页共22页A1Y4051074,04893,001031T，由瑞利商得12998986，即10，I1，2，N则,DIAG1,1,121211NNBBBABBBDIAGAPPB与A有相同特征值而B的第I个盖尔圆为1NIJJIJIJIIBBAAZZ，AIII本科毕业设计说明书（论文）第18页共22页NNNNNNNNBBBAAAAAAAAABBBB2121222211121121111NNNNNNNNNABBABBABBAABBABBABBAA221122422212111121211适当选取B1，B2，BN就有可能使B的某些盖尔圆的半径比A的相应盖尔圆的半径小。事实上，利用相似矩阵的性质，可使A的某些圆盘半径及连通性发生变化1欲缩小GI，可取BI最大。2欲缩小除GI外的圆，可取BI最小。下面我们再来看一个例子例2，估计400200101308001012001090A的特征值范围。解A的三个盖尔圆分别为G1Z|Z09|013；G2Z|Z08|014；G3Z|Z04|0033G3，较好。为了更好地估计另外两个特征值可取B3最小取B1B21，B301即1011P，则40201000130800100120010901APPB本科毕业设计说明书（论文）第19页共22页所以G1Z|Z09|0022；G2Z|Z08|0023；G3Z|Z04|03三个盖尔圆分离，故有1G1，2G2，3G3。从以上的结果说明，只要选取合适的矩阵对原矩阵进行相似变化，就能够使特征值分离，使每个圆盘中只包含一个特征值。本科毕业设计说明书（论文）第20页共22页结论本文中，主要通过介绍盖尔圆定理的应用来研究特征值的包含区域问题，第二章中，罗列了一些求矩阵特征值得算法，包含了乘幂法，反乘幂法，子空间迭代法，LANCZOS方法，JACOBI方法，GIVENS方法，LR和QR方法。第三章中，由矩阵的相似变换来缩小盖尔圆的半径以达到缩小矩阵特征值的包含区域，以及对角矩阵元素的具体选取问题。在论文的写作过程中，关于这方面的文章在逐年增多，人们越来越倾向于用盖尔圆法来研究矩阵特征值的问题。盖尔圆法的研究渐渐成为热点问题，而且这里关于用盖尔圆法的问题还有很多没有解决，比如前面提到的如何最优的选取变换矩阵的元素。矩阵的理论和计算博大精深，在这里我只是简单的做了一些研究，由于本人水平有限，不足之处还请专家见谅。本科毕业设计说明书（论文）第21页共22页致谢首先感谢南京理工大学对我的教育和培养，在这种良好的学术氛围中学到了丰富的知识，锻炼和培养了良好的学术素养。本论文的完成，要感谢我的导师朱元国教授，是他带我走进了学术研究的殿堂本文从选提到完成都是在朱老师的悉心指导下进行的。朱老师还提供了大量详实的资料供我参阅，每一篇论文他都认真阅读和批改，我所取得的每一点小小的成绩都凝聚了他无数的心血和汗水他对学术工作的一丝不苟、锲而不舍的精神，是我们学习的榜样，深深的感染了我。在此，我向他表示深深的感谢在此