Relatively robust representations of symmetric tridiagonals

✍ Scribed by Beresford N. Parlett; Inderjit S. Dhillon

• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 231 KB
• Volume: 309
• Category: Article
• ISSN: 0024-3795
• DOI: 10.1016/s0024-3795(99)00262-1

✦ Synopsis

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 1 and 2 ; LDL t -→ 2 L 1 D 1 L t 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 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|L t )/ LDL t 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