โ Scribed by V. Pan
No coin nor oath required. For personal study only.
Almtraet--Lower and upper bounds on the absolute values of the eigenvalues of an n x n real symmetric matrix A are given by (trace A ,,)t/m for both negative and positive even m. (The bounds are within a factor of 2 from the eigenvalues already for m > log 2 n.) We present algorithms for computing trace A " by means of the inversion of some auxiliary matrices of the form 21-.4, and we estimate the solution cost for the important special classes of matrices (Toeplitz and Toeplitz-like, banded and sparse having small separator families). The cost is substantially lower than in the approach based on the powering of A. The resulting computation of the eigenvalue bounds is deterministic (it does not depend on the choice of an auxiliary vector as is the case for the power and inverse power methods).
๐ SIMILAR VOLUMES
A recursive algorithm for the implicit derivation of the determinant of a symmetric quindiagonal matrix is developed in terms of its leading principal minors. The algorithm is shown to yield a Sturmian sequence of polynomials from which the eigenvalues can be obtained by use of the bisection process