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