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

本科毕业设计说明书（论文）第1页共22页1引言随着科学技术的发展和良好性能计算机的日益普及，大规模的计算问题正越来越多的引起人们的重视。而矩阵在科学计算中起着重要作用，所以，矩阵理论与应用越来越受到数学学者、工程技术人员和科技人员的关注。矩阵理论不仅是一门重要的数学理论，而且在数值分析、最优化方法、数学模型等数学分支上有极其重要的应用。由于利用矩阵理论与方法来处理错综复杂的工程问题时，具有表达简洁、对工程问题的实质刻画深刻等特点，因此利用矩阵理论方法来处理工程技术的各种问题越来越受到工程界人士的重视。数值代数和矩阵理论与应用已成为众多科学领域的数学工具。矩阵计算的理论和方法与方程组的求解是矩阵理论的一个重要方向，已经成为经济学、生物学、现代物理学等领域处理数学问题不可缺少的强大工具，成为数学计算的一个重要分支。许多实际问题最后常常归结为一个或一些大型系数矩阵为特殊矩阵的线性方程组的求解问题。随着科学的发展，矩阵理论已被广泛地运用到应用数学、计算机科学、经济学、工程学、系统科学等诸多方面，成为现代科技领域处理大量有限维形式与数量关系的强有力的工具。对矩阵理论的现代研究与系统工程、优化方法及稳定理论、群论、图论等有着密切的相互关系。作为数学中的一个分支，包含了丰富的内容，成为一门最有实用价值的数学理论。特征值问题是矩阵理论的一个主要研究领域，对它的研究具有重要的理论意义和实用价值。许多科学和工程问题如结构力学中的固有频率分析以及控制系统中的稳定性问题，最终都转化为特征值问题。由于特征值问题在许多学科中具有广泛的应用，因此矩阵特征值的界的估计及求解的理论研究等是当今计算数学和科学与工程计算研究领域的重大课题，国际上研究工作也十分活跃，人们开始从各个方面来研究矩阵的特征值。1．1矩阵的特征值1.1.1矩阵特征值问题的概述矩阵的特征值问题既是一个理论上非常有意义的问题，同时又有着广泛的应用。总的来说就是要满足这样一个关系：Ax=λx,，x≠0，λ∈C是方阵A∈Cn×n的特征值，X∈Cn是与其相适应的特征向量。而奇异值是对任意矩阵来说的(不一定本科毕业设计说明书（论文）第2页共22页是方阵)，若把矩阵A的共轭转置记作AH，那么A的奇异值就是AAH12的特征值。矩阵A的所有特征值的集合称为矩阵的谱。在矩阵代数中，特征值奇异值问题和矩阵的谱分析条件数问题是密切相关的，它们是矩阵最基本也是最重要的特征，在工程和物理学方面应用也很广泛，具有重要的研究意义和价值。但是对于阶数较高的矩阵，要计算出他的特征值和奇异值是相当困难的，所以估算出他们的范围就显得尤为重要了。从估计的结果来看，所给出的范围越小，精度就越高。而国内外很多学者都在试图估算他们的最小范围，所以这类问题在国际上仍然是一个热点研究问题。预备知识在这里我们将讨论这些内容的初等基础理论，它包括两个方面：第一部分是向量，矩阵及运算的定义；第二部分是由向量或矩阵的思想引出的各种概念之间的抽象关系，例如线性相关，列空间等。为了理解后面所提到的算法的描述，必须熟悉矩阵的运算，也要深入掌握矩阵的理论。定义1.1.11设A∈Cn×n，若λ∈C,0≠ξ∈Cn，使得Aξ=λξ成立，则称λ为A的特征值，ξ为A的对应特征值λ的特征向量。将上式的形式改写为λI−Aξ=0ξ≠0这表明特征向量ξ是齐次线性方程组λI−Ax=0的非零解，由线性方程组的理论知，λ为A的特征值的充分必要条件是行列式detλI−A=0称为矩阵A的特征方程，特征方程的根就是A的特征值。多项式fAλ=detλI−A称为A的特征多项式，而矩阵λI−A称为A的特征矩阵。性质1.1.11设A∈Cn×n，则fAλ=λn−trAλn−1+⋯+−1ndetA其中trA=aiini=1为矩阵A的迹。性质.1.1.21n阶矩阵A有且仅有n个特征值，其中m重特征值以m个计。然而5次或5次以上的多项式方程一般是没有公式求解的。所以对于阶数较大本科毕业设计说明书（论文）第3页共22页的矩阵，实际上求特征值是非常困难的，因而就要研究特征值的各种近似求法，在第二章与第三章中的幂法和QR算法正是求特征值近似值的基本方法。性质1.1.31设λ1，λ2，⋯，λn为A=aijn×n的n个特征值（λi未必互异），则trA=λi,detA=λini=1ni=1，显然detA=0当且仅当A具有零特征值。设A=aij∈Cm×n，用A=aij表示以A的元素的共轭复数为元素组成的矩阵，而AH=AT称为A的共轭转置矩阵。矩阵的共轭转置运算性质：1)AH=AT2)A+BH=AH+BH3)kAH=kAH4)ABH=BHAH5)AHH=A6)如果A可逆，则AH−1=A−1H性质1.1.41设λ为n阶矩阵A的特征值，则1)λ也是矩阵AT的特征值；2)λ为矩阵AH的特征值；3)若A非奇异，λ−1为矩阵A−1的特征值。1.1.2矩阵特征值估计的一些基本方法向量迭代法矩阵A的特征值是它的特征多项式的根。我们知道，阶数超过四次的多项式的根一般不能用有限次运算求得，因而矩阵特征值的计算方法本质上总是迭代的。所谓向量迭代法是指不破坏原始矩阵A，而是利用A进行运算，产生一些迭代向量的求解方法，这类方法大多用来求矩阵的部分特征值（常是较大或较小的一部分）本科毕业设计说明书（论文）第4页共22页和相应的特征向量，特别适用于高阶或稀疏矩阵的情况。变换方法求解特征值问题的变换方法，是利用一系列特殊的变换矩阵（初等下三角矩阵，Householder矩阵，平面旋转矩阵等），从矩阵A出发逐次进行相似变换，使变换后的矩阵趋于容易求得特征值的特殊形状（对角形，三角形，拟三角形等），更有效的是先将原矩阵A经相似变换约化为特殊形状的中间矩阵（三对角阵，准上三角阵等），然后再对这类特殊形状的中间矩阵逐次进行变换。大多数变换方法用于求解全部特征值问题，其优点是收敛速度快，计算结果精确可靠，但由于原矩阵A被破坏，当A是稀疏时，在运算过程中很难保持矩阵的稀疏性。此外，这类方法调用计算机外部设备也较困难，因而大多数变换方法适宜于求解中小规模的稠密矩阵的全部特征值问题。1．2本文的研究内容本文主要根据盖尔圆定理来研究矩阵的特征值问题，以及盖尔圆定理的适用范围，如何缩小所求矩阵特征值的范围，对初始矩阵做相似变换时变换矩阵的选取。并且研究了特征值的隔离方法。本文的结构安排如下：第一章：主要阐述了本文的选题背景和研究意义，总结了前人在特征值估计和特征值包含区域方面的一些重要结论，最后对本文主要研究内容作了一个简单的介绍。第二章：求解矩阵特征值的一些具体方法。第三章：盖尔圆定理的在矩阵特征值的估计上的应用及举例说明。怎样缩小求解的矩阵的特征值的范围，怎样确定矩阵特征值的变换矩阵及举例。第四章：对全文进行总结。2求矩阵特征值的基本方法2.1幂法与反幂法本科毕业设计说明书（论文）第5页共22页幂法是求方阵的最大特征值及对应特征向量的一种迭代法。首先我们来介绍幂法：设An有n个线性相关的特征向量v1，v2，„，vn，对应的特征值1，2，„，n，满足|1||2|„|n|因为{v1，v2，„，vn}为Cn的一组基，所以任给x(0)0，niiivax1)0(所以有])([)(21111111)0(niiikiknikkiiniikiniiikkvavavavAavaAxA若a10，则因11i知，当k充分大时A(k)x(0)1ka1v1=cv1是1的特征向量另一方面，记max(x)=xi，其中|xi|=||x||，则当k充分大时，111111111111111)0(1)0()max()max()max()max()max()max(vavavavaxAxAkkkkkk若a1=0，则因舍入误差的影响，会有某次迭代向量在v1方向上的分量不为0，迭代下去可求得1及对应特征向量的近似值。在实际计算中，若|1|1则|1ka1|，若|1|1则|1ka1|0都将停机。所以我们必须采用“规范化”的方法。乘幂法的实际计算格式如下：)()1()()()()max(kkkkkAyxxxy，k=0，1，2，„定理2.1-13任给初始向量0)0(x有，特征值特征向量1)(11)()max(lim)max(limkkkkxvvy证明：yk=xkmaxxk=Ayk−1maxAyk−1=Axk−1maxxk−1maxAxk−1maxxk−1=⋯=AkxomaxAkxo=本科毕业设计说明书（论文）第6页共22页λ1ka1v1+aini=2λiλ1kvimaxλ1ka1v1+aini=2λiλ1kvi)max()max(])([max])([11111121112111vvvavavavavavakniikiiniikii而1111111)1()()max()max()max()max())max(max()max()max(vvvAvvvAAyxkkk由于乘幂法的计算公式依赖于特征根的分布情况，因此实际使用时很不方便，特别不适于自动计算。只是在矩阵阶数非常高，无法利用其他更有效的算法时，才用乘幂法计算少数几个控制特征值和相应的特征向量。然而，乘幂法的基本思想是重要的，由它可以诱导出一些更有效的算法。若A的特征值不满足条件，幂法收敛性的分析较复杂，但若1=2=„=r且|1||r+1|„|n|则定理结论仍成立。此时不同初始向量的迭代向量序列一般趋向于1的不同特征向量。幂法的迭代公式：)()1()()()()max(kkkkkAyxxxy逆幂迭代法是幂迭代法的变形，用来计算非奇异矩阵A按模最小特征值及相应特征向量。设A非奇异，且0λnλn−1≤⋯λ2≤λ1,则A的按模最小特征值λn的倒数恰好为A−1的按模最大特征值，而特征向量保持不变。于是对A−1应用幂法便可计算λn及其对应特征向量xn的逆幂迭代式：Auk=uk−1mk=maxukvk=ukmkk=1,2,⋯类似于幂迭代法，当v0=αixini=1中αn≠0时，有mk→1λn,vk→1maxxn。本科毕业设计说明书（论文）第7页共22页由于在上式中需要求解一方程组，通常将A进行LU分解，则每次迭代只需要求解两个三角形方程组即可。由于逆幂迭代法依然是线性收敛，为加速收敛，所以可用带圆点位移的逆幂迭代法。思想：若已知jˆ为j的近似值，则1)ˆ(jA的特征值是jnjjjˆ1,...,ˆ1,...,ˆ11而显然jjˆ1非常大（最大）比值jijjˆˆ很小迭代公式：,...2,1,0)ˆ()max()()1()()()(kyxIAxxykkjkkk当k时有nkjjjkjjkxxvvy)max(1ˆˆ1)max()max()()()(或注：(1)若有分LR解LRIAPj)ˆ(则迭代公式,...2,1,0)max()1()1()()1()()()(kzRxPyLzxxykkkkkkk(2)在上式中直接取z(1)=(1，„，1)T作初值开始迭代称为半次迭代法2.2QR算法QR算法是用来求解矩阵全部特征值的一种有效方法，它最早由J.G.F.Francis在1961年提出并且对于对阵矩阵和非对称矩阵都适用。QR算法的基本思想就是利用矩阵A的QR分解构造出一个正交相似矩阵序列Ak,使得Ak趋向于一个分块上三角形式，其中对角块是一阶或二阶的子块。下面给出算法步骤：本科毕业设计说明书（论文）第8页共22页设A∈Rn×n非奇异，记A1=A,Ak=QkRkAk+1=RkQkk=1,2,⋯由QR分解可知，Qkk=1,2,⋯为正交矩阵，Rk为上三角矩阵，且若Rk的主对角元均为正数，则上述每一迭代步骤中分解式是唯一。同时由上式得，Ak+1=QkTAkQk,即Ak+1相似于Ak，它们