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 ε > 0 and a prescribed relative error, the algorithms compute estimates which, with probability at least 1 - ε, 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.