构造高斯消去法计算矩阵广义特征值问题

构造高斯消去法计算矩阵广义特征值问题

通过计算，只能通过d、e计算资源值的范围[d、e]。在将范围k分为k后，资源值确定为精度，其中k=[log2（2）e-d）。由于二分法收敛速度较慢，仅为线性收敛，因此在实际算法设计中，经常采用割线法、牛顿迭代、Laguerre迭代或广义Raleigh商迭代进行加速。3.2实对称矩阵广义特征值问题对于实对称矩阵广义特征值问题Ax=λBx，可以直接计算矩阵A-λB的各级顺序主子式，r=1,2，…，nλ．这样计算得到的序列邀Pr（λ）妖也具有在上节叙述的Sturm序列性质，从而可以利用二分/多分法进行计算。但由于矩阵A-λB的三项递推式很难得到，因而必须采用其它方式计算矩阵的Sturm序列。一种方式就是：计算矩阵A-λB的因子分解A-λB=UTDU，其中U为单位上三角矩阵。那么小于λ的特征值个数等于对角矩阵D的负元素的个数。更加常用的一种方式是采用一种变形的高斯消去法计算各级顺序主子式序列的变号数。该方法不是按列而是按行消去对角线以下的元素，从而随时可以计算顺序主子式的符号，进而确定矩阵（A,B）小于λ的特征值个数。在按行消元的过程中，同时按列选主元，进行行交换，保证数值的稳定性。作者在计算对称带状矩阵特征值问题和广义特征值问题时就利用了变形高斯消去法计算Sturm序列。4基于dc算法的矩阵广义特征值问题算法分治（Divide-and-Conquer）算法简称为DC算法，是一种较新的适合并行计算的矩阵广义特征值问题算法。DC算法的基本思想是将大问题分解为两个易于计算的子问题，先求解子问题，然后构成一个比原问题容易求解的广义特征值问题。对于子问题，仍可以对其继续利用DC算法，使矩阵规模达到很小，以便于计算。4.1t,s的特征值的计算对于对称三对角矩阵广义特征值问题（2），取k≈n/2，并令：其中Ti、Si是对称三对角矩阵，Si正定。下面的定理揭示了（T^,S^）和（T,S）的特征值之间的联系。定理1：设λ1燮λ2燮Λ燮λn是（T,S）的特征值，λ^1燮λ^2燮Λ燮λ^n是（T^,S^）的特征值，则：λ^i-1燮λi燮λ^i+1,i=2,3，…，n-1,由以上定理可知，（T^,S^）的特征值是（T,S）的特征值的很好近似。因此，从（T^,S^）的特征值出发，经过若干次Laguerre迭代就可以得到（T,S）的特征值，每个特征值的计算都是独立的，从而可以是并行的。关于广义实对称三对角矩阵特征值问题，作者提出了一种新的分治算法,它同样将矩阵划分为两个子矩阵,但k1+k2=n-1，两个子矩阵分别为原矩阵的左上角和右下脚的两个主子矩阵，可以为特征值λi提供相对更加精确的特征区间（λ^i+1，λ^i），因而可以减少计算时间。4.2．2.2特征值及特征关于对称带状矩阵广义特征值问题，作者提出了如下的划分策略：其中Ai,Bi∈R,k1+k2=n。并证明了如下定理。定理2：设λ1燮λ2燮Λ燮λn是矩阵对（A,B）的特征值，λ^1燮λ^2燮Λ燮λ^n是矩阵对(A^,B^)的特征值,则λ^i-r燮λi燮λ^i+r,i=1,2，…,n。其中，当i燮0时，λ^i=-∞；当i>n时，λ^i=∞。根据以上定理，就可以利用（3）式计算Sturm序列和3.1节介绍的二分/多分法计算特征值和特征向量。为了减少计算时间，可以利用广义Rayleigh商迭代进行加速。5同伦连续法5.1．a,t模式同伦连续法是求解矩阵广义特征值问题的一种新的并行算法。对于对称矩阵广义特征值问题Ax=λBx，令A(t)=(1-t)A0+tA,B(t)=(1-t)B0+tB，其中（A0,B0）是选定的便于计算且特征值与（A,B）的特征值比较接近的矩阵。构照同伦映射：对于微分方程（6），可以采用一般的计算微分方程的方法进行求解。6基于rocs的ts算法前面介绍的计算广义特征值问题的各种算法都要对矩阵进行变换，然后进行求解。另外还有一类算法，只用到矩阵与向量相乘而不作矩阵变换，此类算法就是迭代法。典型的迭代法有Lanczos、Davidson、Arnoldi、子空间迭代、Rayleigh商逆迭代等算法。下面主要介绍Lanczos算法。假设计算实对称矩阵广义特征值问题（1），该问题可以写为B-1Ax=λx，采用三项递推公式可产生列矩阵Q，使得B-1AQ=QT+R,其中Q=(q1,q2,…,qm),Q是B正交的：QTBQ=I,T=[βi,αi,βi+1],R=βm+1qm+1ekT是残差矩阵，初始向量‖q1‖=1。Lanczos算法可以描述如下：Step1：初始化。选取初始向量Step2：迭代。然后计算T的特征对（λ,y），则(λ,Qy)是(A,B)的特征对。业已证明对于Lanczos方法，T常含有(A,B)的极端特征值近似。所以在一定条件下，Lanczos算法是近似对称矩阵特征值和广义特征值问题的一个好算法。但是，Lanczos算法数值稳定性不好