Relatively robust representations of symmetric tridiagonals

Let LDLf be the triangular factorization of an unreduced symmetric tridiago nal matrix T - tau I. Small relative changes in the nontrivial entries of L and D may be represented by diagonal scaling matrices Delta(1) and Delta(2 ); LDLt --> Delta(2)L Delta(1)D Delta(1)L(t)Delta(2). The effect of Delta(2 ) on the eigenvalues lambda(i) - tau is benign. In this paper we study the inner perturbations induced by Delta(1). Suitable condition numbers govern the relative changes in the eigenvalues lambda(i) - tau. We show that when tau = lambda(j) is an eigenvalue then the relative condition number of lamb da(m) - lambda(j), m not equal j, is the same for all n twisted factorizati ons, one of which is LDLt, that could be used to represent T - tau I. See S ection 2. We prove that as tau --> lambda(j) the smallest eigenvalue has relative con dition number relcond = 1 + O(\tau - lambda(j)\). Each relcond is a rationa l function of tau. We identify the poles and then use orthogonal polynomial theory to develop upper bounds on the sum of the relconds of all the eigen values. These bounds require O(n) operations for an n x n matrix. We show t hat the sum of all the relconds is bounded by kappa trace (L\D\L-t) and con jecture that kappa < n/parallel to LDL(t)parallel to. The quantity trace(L\ D\L-t)/parallel to LDL(t)parallel to is a natural measure of element growth in the context of this paper. An algorithm for computing numerically orthogonal eigenvectors without reco urse to the Gram-Schmidt process is sketched. It requires that there exist values of t close to each cluster of close eigenvalues such that all the re lconds belonging to the cluster are modest (say less than or equal to 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 t he eigenvalues within a cluster which can be very complicated. (C) 2000 Els evier Science Inc. All rights reserved.