Randomized error estimation for eigenvalue approximation (Q1570401)

The paper is concerned with the average behavior of the error in iterative methods for eigenvalue and eigenvector estimation by methods based on Krylov information with respect to random start vectors. For a given matrix \(A\) with dominant eigenvalue of unit absolute value, let \(E(k,A,p)^p\) be the integral of the \(p\)-th power of the error for the \(k\)-th approximation of a particular eigenvalue over all start vectors from the unit sphere. A typical result of the paper asserts that for an approximation of a leading eigenvalue with unit absolute value and multiplicity \(r\) using the power method, \(E(k,A,p) = O((1-\delta)^{2k})\) if \(p < r\) and \(E(k,A,p) = O(\delta^{2kr/p})\) if \(p > r\), where \(\delta\) is the maximum modulus of the rest of the spectrum. These estimates are proved for normal matrices, extending earlier results by the author for real symmetric matrices. Similar results are shown for the approximation of eigenvectors and for the behavior of the Lanczos method when computing the smallest eigenvalue of a positive definite matrix. It is also shown that \(E(k,A,1) = O(k^{-1})\) regardless of the size of \(\delta\). The average error of a method for estimating the condition number with a random start vector is also analyzed.