Verified error bounds for all eigenvalues and eigenvectors of a matrix

Abstract

A verification method is presented to compute error bounds for all eigenvectors and eigenvalues, including clustered and/or multiple ones of a general, real, or complex matrix. In case of a narrow cluster, error bounds for an invariant subspace are computed because computation of a single eigenvector may be ill-posed. Computer algebra and verification methods have in common that the computed results are correct with mathematical certainty. Unlike a computer algebra method, a verification method may fail in the sense that only partial or no inclusions at all are computed. That may happen for very ill conditioned problems being too sensitive for the arithmetical precision in use. That cannot happen for computer algebra methods which are “never-failing” because potentially infinite precision is used. In turn, however, that may slow down computer algebra methods significantly and may impose limitations on the problem size. In contrast, verification methods solely use floating-point operations so that their computing time and treatable problem size is of the order of that of purely numerical algorithms. For our problem it is proved that the union of the eigenvalue bounds contains the whole spectrum of the matrix, and bounds for corresponding invariant subspaces are computed. The computational complexity to compute inclusions of all eigenpairs of an n × nmatrix is O(n3).