Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices
复制标题
DOI：
10.1016/j.laa.2003.12.028
复制
发表时间：
2004-08-01
影响因子：
1.1
通讯作者：
Parlett, BN
中科院分区：
文献类型：
--
作者：
Dhillon, IS;Parlett, BN
本文给出了计算n×n对称三对角矩阵T的k个特征向量的O(Nk)算法MR3，该算法的一个显著特点是计算了多个不同的LDLT乘积(L单位下三角，D对角线)。在精确的算术中，每个LDLT都是T的平移的因式分解。我们称之为(T的)各种LDLT乘积表示，粗略地说，每个闭合特征值簇都有一个表示。对于每个矩阵，算法的展开由表示树很好地描述。我们给出了这棵树，并用它来证明，如果每个表示满足三个规定的条件，那么计算的特征向量与工作精度是正交的，并且相对于原始矩阵T(C)2004具有较小的残差范数。
In this paper we present an O(nk) procedure, Algorithm MR3, for computing k eigenvectors of an n x n symmetric tridiagonal matrix T. A salient feature of the algorithm is that a number of different LDLt products (L unit lower triangular, D diagonal) are computed. In exact arithmetic each LDLt is a factorization of a translate of T. We call the various LDLt products representations (of T) and, roughly speaking, there is a representation for each cluster of close eigenvalues. The unfolding of the algorithm, for each matrix, is well described by a representation tree. We present the tree and use it to show that if each representation satisfies three prescribed conditions then the computed eigenvectors are orthogonal to working accuracy and have small residual norms with respect to the original matrix T. (C) 2004 Elsevier Inc. All rights reserved.