Relatively robust representations of symmetric tridiagonals

AbstractLet 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 κ