矩阵特征值求解.docx

矩阵特征值求解的分值算法12组1．1矩阵计算的基本问题(1)求解线性方程组的问题.即给定一个n阶非奇异矩阵A和n维向量b,求一个n维向量x,使得Ax=b((2)线性最小二乘问题,即给定一个mxn阶矩阵A和m维向量b,求一个n维向量x,使得Ax一b=min{Ay一b,yeRn}((3)矩阵的特征问题,即给定一个n阶实(复)矩阵A,求它的部分或全部特征值以及对应的特征向量,也就是求解方程Ax=λx(一对解(λ,x),其中λeR(C),xeRn(Cn),即λ为矩阵A的特征值,x为矩阵A的属于特征值λ的特征向量。在工程上,矩阵的特征值具有广泛的应用,如大型桥梁或建筑物的振动问题:机械和机件的振动问题；飞机机翼的颤振问题;无线电电子学及光学系统的电磁振动问题;调节系统的自振问题以及声学和超声学系统的振动问题.又如天文、地震、信息系统、经济学中的一些问题都与矩阵的特征值问题密切相关。在科学上,计算流体力学、统计计算、量子力学、化学工程和网络排队的马尔可夫链模拟等实际问题,最后也都要归结为矩阵的特征值问题.由于特征值问题在许多科学和工程领域中具有广泛的应用,因此对矩阵的特征值问题的求解理论研究算法的开发软件的制作等是当今计算数学和科学与工程计算研究领域的重大课题,国际上这方面的研究工作十分活跃。1.2矩阵的特征值问题研究现状及算法概述对一个nxn阶实(复)矩阵A,它的特征值问题,即求方程(,是数值线性代数的一个中心问题.这一问题的内在非线性给计算特征值带来许多计算问题.为了求(λ,一个简单的想法就是显式地求解特征方程det(A一λI)=0(除非对于个别的特殊矩阵,由于特征方程的系数不能够用稳定的数值方法由行列式的计算来求得,既使能精确计算出特征方程的系数,在有限精度下,其特征多项式f(λ)=det(A一λI)的根可能对多项式的系数非常敏感.因此,这个方法只能在理论上是有意义的,实际计算中对一般矩阵是不可行的.首先,若矩阵A的阶数较大,则行列式det(A一λI)的计算量将非常大;其次,根据Galois理论,对于次数大于四的多项式求根不存在一种通用的方法,基于上述原因,人们只能寻求其它途径.因此,如何有效地!精确地求解矩阵特征值问题,就成为数值线性代数领域的一个中心问题.目前,求解矩阵特征值问题的方法有两大类:一类称为变换方法,另一类称为向量迭代方法.变换方法是直接对原矩阵进行处理,通过一系列相似变换,使之变换成一个易于求解特征值的形式,如Jacobi算法,Givens算法,QR算法等。变换方法由于要存储矩阵元素,因而它只适用于求解中小型矩阵,它一般和向量迭代方法结合起来使用.向量迭代方法是通过一系列矩阵向量乘积而求得特征值和特征向量的.由于向量迭代方法可采用压缩存储技术,因而它适合于求大规模矩阵的特征值问题,尤其是大型稀疏矩阵的部分特征值和特征向量问题,如Lanczos方法,Arnoldi方法,Davidson方法等,现在这类问题仍是比较热的研究课题。2分治方法的基础及理论研究2.1分治方法的概述考虑对称三对角矩阵T的特征值问题nTx=λx(n其中Tn=(|||||（βn-1n1(1981年Cuppen提出一种求上述对称三对角矩阵Tn所有特征值和特征向量的分而治之方法（divide一and一conquermethod).其基本思想是先将对称三对角矩阵T分割为两个分别为k根k阶和(n-k)根(n-k)阶低阶对称三对角子矩阵nT(0)和T(1).T(0)和T(1))可以用同样的方法也分别分割为两个更低阶的子矩阵,递归的采用这种分割技术可以把矩阵分割为一些能直接求出特征值的足够小的子矩阵(比如2阶或1阶矩阵),或者按照某种标准分割到适当阶数(如小于等于25阶)后,结合其它求矩阵特征值的方法,如QR算法,求出其特征值。在求出低阶矩阵特征值的基础上,开始胶合过程。在胶合阶段,分割前的矩阵T1的特征值的求,,出(所谓的“治之”)是建立在其两个子矩阵T(0)和T(1)的特征值的基础上的,其,,中T(0)和T(1).是在分割阶段由T1分割出的低阶子矩阵.随后的数值分析表明,Cuppen的方法存在着数值不稳定的危险,特别是当存在特征值束时,计算出的特征向量可能不正交。Gu和Eisenstat对Cuppen的方法作了改进,极大地降低了数值不稳定的危险性。Cuppen的方法在计算T的特征值的同时也需要计算对应的特征向量,并且n是在T(0)和T(1)的特征值和特征向量的基础上进行计算的.根据文中,当用残量nnTX-ΛX和正交性XTX-I作为检验准确性的标准时，Cuppen的方法比二分法或多分法精确的多。但文[3中，,如果用T作为衡量特征值准确性n的标准时,二分法或多分法精确些.此外Cuppen的分而治之方法要求矩阵乘积,存储量为O(n2),而二分法或多分法的存储量仅