[Math] Does the power method converge

approximationeigenvalues-eigenvectorsmatricesnumerical methods

I want to check if the power method converges for the matrix $A$ and the vector $\vec{v} $ where $$A=\begin{pmatrix}\lambda & 1 \\ 0 & -\lambda\end{pmatrix} \text{ and }
\vec{v} =\begin{pmatrix}1 \\ 1\end{pmatrix}$$

Do we have to apply some steps of the power method and see if the results converge to the absolute maximum eigenvalue of the matrix A or is there a criterion for convergence?

Best Answer

In the power iteration $ \vec{v}_{n+1} = A \vec{v}_n$ and we normalize each vector $\vec{v}_{n+1} \leftarrow \vec{v}_{n+1} / \| \vec{v}_{n+1} \|$. Note that

\begin{equation} A^2 = \lambda^2 \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} = \lambda^2 I \end{equation}

Thus, $\vec{v}_{2n} = A^{2n} \vec{v}_0 = \lambda^{2n} \vec{v}_0$ with $\vec{v}_0 = [1,1]^{\intercal}$. Normalizing vector gives

\begin{equation} \vec{v}_{2n} \leftarrow \frac{1}{\sqrt{2}}\begin{bmatrix}1\\1\end{bmatrix} \end{equation}

While $\vec{v}_{2n+1} = A^{2n+1} \vec{v}_0 = A A^{2n} \vec{v}_0 = \lambda^{2n} A \vec{v}_0 = \lambda^{2n}[\lambda+1,-\lambda]^{\intercal}$. Normalizing gives

\begin{equation} \vec{v}_{2n+1} \leftarrow \frac{1}{\sqrt{(\lambda+1)^2+\lambda^2}} \begin{bmatrix}(\lambda+1)\\-\lambda \end{bmatrix} \end{equation}

Iterations oscillate between these two vectors, thus the iterations do not converge.

The convergence rate of power method is determined by the ratio $\rho = |\lambda_1| / |\lambda_2| \geq 1$, where $\lambda_1$ and $\lambda_2$ are the first and second largest eigenvalues (in magnitude). The larger the ratio is, the better convergece rate the iteration have.

In the case of your matrix, eigenvalues are $\lambda_1 = |\lambda|$ and $\lambda_2 = |-\lambda|$, and the ratio is $\rho = 1$. So the iteration do not converge.