Franklin's Notes

Simultaneous iteration

Simultaneous iteration is an iterative method for extracting the eigenvalues of a matrix in a way that generalizes on power iteration . In particular, simultaneous iteration essentially consists of applying power iteration to several vectors at once, combined into a single matrix. While power iteration consists of repeatedly applying the matrix $A$ to a single vector and then normalizing, simultaneous iteration consists of repeatedly applying the matrix $A$ to a set of vectors and then orthonormalizing.

Let $A$ be an $m\times m$ matrix with values in $\mathbb R$, and let $V^{(0)}=[v_1^{(0)}|\cdots|v_n^{(0)}]$ be a matrix whose columns are linearly independent "eigenvector estimates" (which don't actually need to be very good estimates) with $n\leq m$. Define the sequence of matrices $V^{(k)}$ as follows: so that $A$ is applied $k$ times to each of the eigenvector estimates to form the columns of $V^{(k)}$. Further, let $V^{(k)}$ have the following reduced QR factorization : We can prove that, under certain assumptions, the columns of $\hat Q^{(k)}$ converge to eigenvectors of $A$ corresponding to the $n$ eigenvalues of largest magnitude as $k\to\infty$. In particular, we need to assume first that the $n+1$ leading-magnitude eigenvalues of $A$ have distinct magnitudes: and additionally that all the leading principal minors of $\hat Q^T V^{(0)}$ are nonsingular, where $\hat Q=[q_1|\cdots|q_n]$ is the matrix whose columns are the true unit eigenvectors corresponding to the eigenvalues $\lambda_1,\cdots,\lambda_n$. We also assume that $A$ is nondefective, i.e. that it has an eigenvalue decomposition .

To see why we have convergence given these assumptions, expand $A$ into its eigenvalue decomposition $A=Q\Lambda Q^T$, so that $A^k = Q\Lambda^k Q^T$. By discarding all eigenvalues of $\Lambda$ after the dominant $n$ eigenvalues, we have that where $\hat\Lambda$ consists of the principal $n\times n$ submatrix of $\Lambda$. This allows us to write and, since $\hat Q^T V^{(0)}$ is nonsingular, we have and because all principal submatrices of $\hat Q^T V^{(0)}$ are nonsingular, we can make similar claims involving only the first $n'$ eigenvalues/eigenvectors, for any $n'<n$. This allows us to claim by induction by analyzing successive columns spaces that the first column of $\hat Q^{(k)}$ converges to $\pm q_1$, and the second column of $\hat Q^{(k)}$ converges to $\pm q_2$, and so on by induction.

Simultaneous iteration would never be executed this way in practice: the matrices $V^{(k)}$ would be terribly conditioned. Rather than computing $V^{(1)},\cdots, V^{(k)}$ and then calculating the QR factorization of $V^{(k)}$, a more practical version of the algorithm computes a QR factorization at each step and uses each computed $Q$ matrix as the matrix of eigenvector estimates for the next step. It can be shown that this yields the same estimates as the above algorithm in exact arithmetic, while being much better conditioned.




back to home page