Relatively robust representations of symmetric tridiagonals

Abstract

Let LDLt 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 Δ1 and Δ2; LDLt→Δ2LΔ1DΔ 1LtΔ2. The effect of Δ2 on the eigenvalues λi-τ is benign. In this paper we study the inner perturbations induced by Δ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 LDLt, 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|Lt) and conjecture that κ<n/∥LDLt∥. 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 ≤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. © 2000 Elsevier Science Inc.