An Analysis of the Rayleigh--Ritz Method for Approximating Eigenspaces\symbolmark{1}

Abstract

This paper concerns the Rayleigh--Ritz method for computing an approximation to an eigenspace $\clx$ of a general matrix $A$ from a subspace $\clw$ that contains an approximation to $\clx$. The method produces a pair $(N, \tilde X)$ that purports to approximate a pair $(L, X)$, where $X$ is a basis for $\clx$ and $AX = XL$. In this paper we consider the convergence of $(N, \tilde X)$ as the sine $\epsilon$ of the angle between $\clx$ and $\clw$ approaches zero. It is shown that under a natural hypothesis\,---\,called the uniform separation condition\,---\,the Ritz pairs $(N, \tilde X)$ converge to the eigenpair $(L, X)$. When one is concerned with eigenvalues and eigenvectors, one can compute certain refined Ritz vectors whose convergence is guaranteed, even when the uniform separation condition is not satisfied. An attractive feature of the analysis is that it does not assume that $A$ has distinct eigenvalues or is diagonalizable. (Also cross-referenced as UMIACS-TR-99-24)