Estimating Extremal Eigenvalues and Condition Numbers of Matrices

The paper describes “probabilistic” algorithms which may be used to make rough estimates of the largest and smallest eigenvalues of a positive definite matrix and the condition number of a nonsingular matrix in the 2-norm. Given $\varepsilon > 0$ and a prescribed relative error, the algorithms compute estimates which, with probability at least $1 - \varepsilon $, have relative errors less than that prescribed. In particular, the method gives a reliable way to estimate the condition number of a matrix of large degree.