Abstract: Let LDL^t be the triangular factorization of an unreduced symmetric tridiagonal matrix T − τ I . Small relative changes in the nontrivial entries of L and D may be represented by diagonal scaling matrices Delta_1 and Delta_2; LDL^t → Delta_2 LDelta_1 D Delta_1L^tDelta_2. The effect of Delta_2 on the eigenvalues λi − τ is benign. In this paper we study the inner perturbations induced by Delta_1. Suitable condition numbers govern the relative changes in the eigenvalues λi − τ . We show that when τ = λj is an eigenvalue then the relative condition number of λm − λj , m != j , is the same for all n twisted factorizations, one of which is LDL^t, that could be used to represent T − τI. See Section 2.
We prove that as τ → λj the smallest eigenvalue has relative condition number relcond = 1 + O(|τ − λj |). Each relcond is a rational function of τ . We identify the poles and then use orthogonal polynomial theory to develop upper bounds on the sum of the relconds of all the eigenvalues. These bounds require O(n) operations for an n × n matrix. We show that the sum of all the relconds is bounded by κ trace (L|D|L^t) and conjecture that κ < n/∥LDL^t∥. The quantity trace(L|D|Lt)/∥LDLt∥ is a natural measure of element growth in the context of this paper.
An algorithm for computing numerically orthogonal eigenvectors without recourse to the Gram–Schmidt process is sketched. It requires that there exist values of τ close to each cluster of close eigenvalues such that all the relconds belonging to the cluster are modest (say leq 10), the sensitivity of the other eigenvalues is not important. For this reason we develop O(n) bounds on the sum of the relconds associated with a cluster. None of our bounds makes reference to the nature of the distribution of the eigenvalues within a cluster which can be very complicated.
Download: pdf
Citation
- Relatively Robust Representations for Symmetric Tridiagonals (pdf, software)
B. Parlett, I. Dhillon.
Linear Algebra and its Applications 309, pp. 121-151, November 2000.
Bibtex: