Eigenvalue Estimates via Pseudospectra

In this note, given a matrix A ∈ C n × n (or a general matrix polynomial P ( z ) , z ∈ C ) and an arbitrary scalar λ 0 ∈ C , we show how to define a sequence μ k k ∈ N which converges to some element of its spectrum. The scalar λ 0 serves as initial term ( μ 0 = λ 0 ), while additional terms are constructed through a recursive procedure, exploiting the fact that each term μ k of this sequence is in fact a point lying on the boundary curve of some pseudospectral set of A (or P ( z ) ). Then, the next term in the sequence is detected in the direction which is normal to this curve at the point μ k . Repeating the construction for additional initial points, it is possible to approximate peripheral eigenvalues, localize the spectrum and even obtain spectral enclosures. Hence, as a by-product of our method, a computationally cheap procedure for approximate pseudospectra computations emerges. An advantage of the proposed approach is that it does not make any assumptions on the location of the spectrum. The fact that all computations are performed on some dynamically chosen locations on the complex plane which converge to the eigenvalues, rather than on a large number of predefined points on a rigid grid, can be used to accelerate conventional grid algorithms. Parallel implementation of the method or use in conjunction with randomization techniques can lead to further computational savings when applied to large-scale matrices.