Skip to main content

Subsection 10.2.2 Subspace iteration with a Hermitian matrix

This last algorithm in Subsection 10.2.1 can be reformulated to work with an arbitrary number of vectors to find a space spanned by an arbitrary number of eigenvectors:

\begin{equation*} \begin{array}{l} \widehat V := \mbox{ random } m \times n \mbox{ matrix} \\ ( \widehat V^{(0)}, R ) := {\rm QR}( \widehat V ) \\ A^{(0)} = { \widehat V V^{(0)}}^H A \widehat V V^{(0)} \\ {\bf for~} k:=0, \ldots \\ ~~~( \widehat V^{(k+1)}, R ) := {\rm QR}( A \widehat V^{(k)} ) \\ ~~~ A^{(k+1)} = {\widehat V^{(k+1)}~}^H A \widehat V^{(k+1)} \\ {\bf endfor} \end{array} \end{equation*}

By extending the reasoning behind the Power Method and the algorithms discussed in Subsection 10.2.2, we have informally arrived at the obervation that

  • \(A \) is Hermitian;

  • \(\vert \lambda_0 \vert \gt \vert \lambda_1 \vert \gt \cdots \gt \vert \lambda_{n-1} \vert \text{;}\) and

  • \(v_j \) has a component in the direction of \(x_j \text{,}\) an eigenvector associated with \(\lambda_j \text{,}\)

each \(v_j^{(j)} \) will converge to a multiple of \(x_j \text{.}\)

If some of the eigenvalues have equal magnitude, then the corresponding columns of \(\widehat V^{(k)} \) will eventually form a basis for the subspace spanned by the eigenvectors associated with those eigenvalues. The convergence of the first \(s \) columns of \(\widehat V^{(k)} \) to a basis for the subspace spanned by the eigenvectors associated with the largest (in magnitude) \(s \) eigenvalues is dictated by the ratio \(\lambda_{k}/\lambda_{k-1} \text{.}\)