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

《求实对称三对角阵特征值的递归算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、ix(ShuXin-XieHunanRailwayProfessionalandTechnologyCollege)Abstract:ManySymmetricMatrixProblemscancomedowntoRealSymmetricTri-diagonalMatrixProblem.ARecursionAlgorithmforBisectiontoSeektheCharacteristicValueofRealSymmetricTri-diagonalMatrixisdiscussedinthispaper.ARecursionFu

3、nctionisdesignedtoseekallofthecharacteristicvalueanditcanseekrepeatcharacteristicvalue.Keywords:RecursionAlgorithm;Bisection;RealSymmetricTri-diagonalMatrix;CharacteristicPolynomialSerials;一、问题的提出对称矩阵特征值问题在解决非线性规划、优化、常微分方程等各种数学计算问题，以及结构力学、工程设计、计算物理、量子力学和模式识别等领域都有重要作用。目前，求实

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

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

6、个数为。进一步，若,则可知矩阵T的第k个特征值位于区间中。若矩阵的第k个特征值（特征值按从大到小顺序排列）位于区间中，而第k+1个特征值不在区间中，则。取区间中点(a+b)/2,计算。若，则第k个特征值位于区间中，若，则第k个特征值位于区间中。继续将区间分半，直到最后区间的长度少于等于预先给定的精度控制量TOL为止。取最后区间的中点作为特征值的近似。-5-5-TT0ba(a+b)/2λ图在区间[a,b]中找到第k个特征值三、求实对称三对角阵的特征值的递归算法考虑到每求一个特征值都要把区间反复分半，其中有许多重复计算。可以设计一个递归算法。在

7、区间分半时，从区间中点向两个方向搜索特征值。如果区间两个端点处的特征值个数相等，就不搜索。在搜索过程中，同时把特征值的近似值（区间中点值）保存下来。为了搜索一次求出所有特征值，用一个数组把n个特征值都存储下来。在搜索过程中，后面搜索到的精度更高的特征值会覆盖以前的特征值。最后存储下来的都是精度最高的特征值。输入：输出：特征值Step1计算特征值的界(谱半径)，Step2设计递归函数。1.设计if语句块，判断递归结束条件。2.设计else语句块，确定递归搜索方式。Step3设计求特征值个数函数(附录中有C++源码)1.循环递推求实对称三对角阵

8、的特征多项式序列。2.统计特征多项式序列中相邻项符号相同的个数。Step4调用递归函数。数值实例:1.递归算法的C++源码如下：#defineTOL0.00001//二分法求三对