Appeared in SIAM Review 32 (1990) 576--610.

In this paper classical matrix perturbation theory is approached from a probabilistic point of view. The perturbed quantity is approximated by a first order perturbation expansion, in which the perturbation is assumed to be random. This permits the computation of statistics estimating the variation in the perturbed quantity. Up to the higher order terms that are ignored in the expansion, these statistics tend to be more realistic than perturbation bounds obtained in terms of norms. The technique is applied to a number of problems in matrix perturbation theory, including least squares and the eigenvalue problem. Additional files are available via anonymous ftp at: thales.cs.umd.edu in the directory /ftp/pub/reports (Also cross-referenced as UMIACS-TR-88-76)