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

求实对称三对角矩阵特征值的递归算法 (谢树新 1、湖南铁道职业技术学院信息系湖南铁道职业技术学院 2、武汉大学国际软件学院） 摘 要： 许多对称矩阵特征值问题最后归结为解实对称三对角矩阵特征值问题。本文为采用二分法求实对称三对角矩阵特征值设计了一个递归算法。 用一个递归函数就可以求出所有特征值，而且能求重特征值。 关键词： 递归算法　二分法　实对称三对角矩阵　特征多项式序列 中图分类号: 　　　文献标识码: A Recursion Algorithm to Seek the Characteristic value of Real Symmetric Tri-diagonal Matrix (ShuXin-Xie Hunan Railway Professional and Technology 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 Function 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; 一 、问题的提出 对称矩阵特征值问题在解决非线性规划、优化、常微分方程等各种数学计算问题，以及结构力学、工程设计、计算物理、量子力学和模式识别等领域都有重要作用。目前，求实对称矩阵的特征值的方法分串行算法和并行算法。串行算法主要有：Jacobi算法、幂方法、,Krylov 方法、Lanczos方法、Frame方法、QR 方法、Givens-Householder变换算法等。Givens-Householder变换算法是首先把实对称矩阵通过Givens变换或Householder变换化为实对称三对角阵，再通过二分法来求特征值。 用二分法求实对称三对角阵特征值的串行算法的缺点是：一次只能求一个特征值,且不能求重特征值[1,2,3,4,5]。本文用一个递归函数来求解实对称三对角阵的所有特征值，且能求重特征值。 二、区间分半算法求实对称三对角阵的特征值算法简介 设T为实对称三对角矩阵： 用表示矩阵T-λI的阶顺序主子式，如下： 从上式显然有。把上述行列式按最后一行展开可以得到三项递推关系式。其中：规定。特别，。因此是矩阵T的特征多项式，多项式序列叫矩阵T的特征多项式序列。 设T的特征值为：。由于矩阵T的谱半径不超过T的任何一种范数，因此T的任何一个特征值都满足这样矩阵T的全部特征值必在区间上，易知。其中规定： 下面介绍在区间中寻找矩阵T的特征值方法： 设a,b为二实数，且ab。据上述推论可知，大于a的特征值个数为，大于b的特征值个数为。显然矩阵T在区间中的特征值个数为。进一步，若,则可知矩阵T的第k个特征值位于区间中。 若矩阵的第k个特征值（特征值按从大到小顺序排列）位于区间中，而第k+1个特征值不在区间中，则。 取区间中点(a+b)/2,计算。若，则第k个特征值位于区间中，若，则第k个特征值位于区间中。继续将区间分半，直到最后区间的长度少于等于预先给定的精度控制量TOL为止。取最后区间的中点作为特征值的近似。 -TT -T T 0 b a (a+b)/2 λ 图 在区间[a,b]中找到第k个特征值 三、求实对称三对角阵的特征值的递归算法 考虑到每求一个特征值都要把区间反复分半，其中有许多重复计算。可以设计一个递归算法。在区间分半时，从区间中点向两个方向有哪些信誉好的足球投注网站特征值。如果区间两个端点处的特征值个数相等，就不有哪些信誉好的足球投注网站。在有哪些信誉好的足球投注网站过程中，同时把特征值的近似值（区间中点值）保存下来。为了有哪些信誉好的足球投注网站一次求出所有特征值，用一个数组把n个特征值都存储下来。在有哪些信誉好的足球投注网站过程中，后面有哪些信誉好的足球投注网站到的精度更高的特征值会覆盖以前的特征值。最后存储下来的都是精度最高的特征值。 输入： 输出：特征值 Step1 计算特征值的界(谱半径)， Step2 设计递归函数。 1.设计if语句块，判断递归结束条件。 2.设计else语句块，确定递归有哪些信誉好的足球投注网站方式。 S