The computation of the eigenvalues and orthogonal eigenvectors of an N x N real symmetric tridiagonal matrix is a well known problem in numerical analysis. The problem frequently arises in the determination of eigenvalues and eigenvectors of dense and banded symmetric matrices and in connection with various families of orthogonal polynomials and special functions satisfying three term recurrence relations. Numerous algorithms exist for the solution of this problem, which typically require O(N2) operations for the determination of eigenvalues and O(N3) operations for the determination of orthogonal eigenvectors.;In this thesis we propose a new class of fast algorithms for the computation of the eigenvalues of a symmetric tridiagonal matrix in O( N ln N) operations. Such an algorithm may be combined with any one of the existing methods for the determination of eigenvectors of a symmetric tridiagonal matrix with known eigenvalues. The underlying technique is a divide-and-conquer approach which determines eigenvalues of a larger tridiagonal matrix from those of constituent matrices by the use of relations of their characteristic polynomials. The evaluation of characteristic polynomials is accelerated by the use of a technique known as the Fast Multipole Method. We provide a detailed presentation of a prototype for this class of algorithms and discuss several generalizations.;An implementation of a prototype for this class of algorithms has been developed in FORTRAN, which serves to provide a comparison with existing techniques in terms of running time and accuracy. We present numerical results which demonstrate the effectiveness of the method.
展开▼
机译：N x N实对称三对角矩阵的特征值和正交特征向量的计算是数值分析中众所周知的问题。在确定密集和带状对称矩阵的特征值和特征向量时，以及与满足三项递归关系的各种正交多项式族和特殊函数相关的问题经常出现。存在许多用于解决该问题的算法，通常需要O（N2）运算来确定特征值，并需要O（N3）运算来确定正交特征向量。 O（N ln N）运算中对称三对角矩阵的特征值的计算。这样的算法可以与用于确定具有已知特征值的对称三对角矩阵的特征向量的现有方法中的任何一种结合。底层技术是一种分治法，该方法利用组成矩阵的特征多项式的关系从组成矩阵的特征值确定较大的三对角矩阵的特征值。通过使用称为快速多极方法的技术，可以加快特征多项式的评估速度。我们提供了此类算法的原型的详细介绍，并讨论了几种概括。; FORTRAN中已经开发了此类算法的原型的实现，它可以在运行时间和运行时间方面与现有技术进行比较。准确性。我们提供数值结果，证明了该方法的有效性。
展开▼
