求实对称三对角阵特征值的递归算法

1、求实对称三对角矩阵特征值的递归算法(谢树新 1、湖南铁道职业技术学院信息系湖南铁道职业技术学院2、武汉大学国际软件学院）摘 要：许多对称矩阵特征值问题最后归结为解实对称三对角矩阵特征值问题。本文为采用二分法求实对称三对角矩阵特征值设计了一个递归算法。 用一个递归函数就可以求出所有特征值，而且能求重特征值。关键词：递归算法二分法实对称三对角矩阵特征多项式序列中图分类号:文献标识码: A Recursion Algorithm to Seek the Characteristic value of Real Symmetric Tri-diagonal Matrix(ShuXin-Xie Huna

2、n Railway Professional and Technology College)Abstract:Many Symmetric Matrix Problems can come down to Real Symmetric Tri-diagonal Matrix Problem. A Recursion Algorithm for Bisection to Seek the Characteristic Value of Real Symmetric Tri-diagonal Matrix is discussed in this paper. A Recursion Functi

3、on is designed to seek all of the characteristic value and it can seek repeat characteristic value.Key words: Recursion Algorithm; Bisection; Real Symmetric Tri-diagonal Matrix; Characteristic Polynomial Serials; 一 、问题的提出对称矩阵特征值问题在解决非线性规划、优化、常微分方程等各种数学计算问题，以及结构力学、工程设计、计算物理、量子力学和模式识别等领域都有重要作用。目前，求实对称

4、矩阵的特征值的方法分串行算法和并行算法。串行算法主要有：Jacobi算法、幂方法、,Krylov 方法、Lanczos方法、Frame方法、QR 方法、Givens-Householder变换算法等。Givens-Householder变换算法是首先把实对称矩阵通过Givens变换或Householder变换化为实对称三对角阵，再通过二分法来求特征值。用二分法求实对称三对角阵特征值的串行算法的缺点是：一次只能求一个特征值,且不能求重特征值1,2,3,4,5。本文用一个递归函数来求解实对称三对角阵的所有特征值，且能求重特征值。二、区间分半算法求实对称三对角阵的特征值算法简介设T为实对称三对角矩阵

5、： 用表示矩阵T-I的阶顺序主子式，如下：从上式显然有。把上述行列式按最后一行展开可以得到三项递推关系式。其中：规定。特别，。因此是矩阵T的特征多项式，多项式序列叫矩阵T的特征多项式序列。设T的特征值为：。由于矩阵T的谱半径不超过T的任何一种范数，因此T的任何一个特征值都满足这样矩阵T的全部特征值必在区间上，易知。其中规定：下面介绍在区间中寻找矩阵T的特征值方法：设a,b为二实数，且ab。据上述推论可知，大于a的特征值个数为，大于b的特征值个数为。显然矩阵T在区间中的特征值个数为。进一步，若,则可知矩阵T的第k个特征值位于区间中。若矩阵的第k个特征值（特征值按从大到小顺序排列）位于区间中，而第

6、k+1个特征值不在区间中，则。取区间中点(a+b)/2,计算。若，则第k个特征值位于区间中，若，则第k个特征值位于区间中。继续将区间分半，直到最后区间的长度少于等于预先给定的精度控制量TOL为止。取最后区间的中点作为特征值的近似。-TT0ba(a+b)/2图 在区间a,b中找到第k个特征值三、求实对称三对角阵的特征值的递归算法考虑到每求一个特征值都要把区间反复分半，其中有许多重复计算。可以设计一个递归算法。在区间分半时，从区间中点向两个方向搜索特征值。如果区间两个端点处的特征值个数相等，就不搜索。在搜索过程中，同时把特征值的近似值（区间中点值）保存下来。为了搜索一次求出所有特征值，用一个数组把

7、n个特征值都存储下来。在搜索过程中，后面搜索到的精度更高的特征值会覆盖以前的特征值。最后存储下来的都是精度最高的特征值。输入：输出：特征值Step1 计算特征值的界(谱半径)， Step2 设计递归函数。1.设计if语句块，判断递归结束条件。2.设计else语句块，确定递归搜索方式。Step3 设计求特征值个数函数(附录中有C+源码)1.循环递推求实对称三对角阵的特征多项式序列。2.统计特征多项式序列中相邻项符号相同的个数。Step4 调用递归函数。数值实例:1.递归算法的C+源码如下：#define TOL 0.00001 /二分法求三对角矩阵的精度容限float Tinf;/定义谱半径 T

8、inf=fabs(deltasize-1)+fabs(alfasize-2); if (Tinffabs(delta0)+fabs(alfa0) ) Tinf=fabs(delta0)+fabs(alfa0); for (int i=1;isize-1;i+) if (Tinffabs(alfai-1)+fabs(deltai)+fabs(alfai) ) Tinf=fabs(alfai-1)+fabs(deltai)+fabs(alfai); /-区间分半法(二分法)求特征值- void halfeigen(float a,float b,float deltaN,float alfaN-1

9、,float lamdaN,int size) /a,b储存区间a,b的端点，deltaN 储存主对角元，alfaN-1储存次对角元 / lamdaN 储存特征值，size储存对角矩阵的阶数 if ( b-aTOL ) /递归结束条件 lamdas(a,delta,alfa,size)-1=(a+b)/2; /保存特征值 else /递归求特征值 if (s(a+b)/2,delta,alfa,size)s(b,delta,alfa,size) ) /右边递归搜索 halfeigen(a+b)/2,b,delta,alfa,lamda,size); /-区间分半法(二分法)求实对称三对角阵的特

10、征值-/-求大于x的特征值个数- int s(float x,float deltaN,float alfaN-1,int size) /统计大于x的特征值个数 double pN;/声明三对角阵的特征多项式 p0=1; p1=delta0-x; for (int i=2;isize+1;i+) pi=(deltai-1-x)*pi-1-alfai-2*alfai-2*pi-2;/循环求特征多项式序列 int count=0; / (统计特征多项式序列的符号数（相邻项同号的个数） for (int i=1;i0 & pi-10 ) count+; else if (pi0 & pi-10 ) count+; return count; halfeigen(-Tinf, Tinf, delta, alfa, lamda, size); /调用递归函数参 考 文 献1 邓健新，解实对称矩阵特征值问题的并行算法，数值计算与计算机应用，1997年12月。2 B. N. PARL ETT. The symmetric eigenvalue problem. Prentice HallM1Englewood Cliffs ,NJ ,1980.作者简介：谢树新，男，19