Power Method

The simplest eigenvalue problem is to compute just the dominating eigenvalue along with its eigenvector. The power method presented in Algorithm 4.1 is the simplest iterative method for this task. Under mild assumptions it finds the eigenvalue of $A$ which has the largest absolute value, and a corresponding eigenvector.

Let $x_1$ be the eigenvector corresponding to $\lambda_1=\lambda_{\max}(A)$. The angle $\angle(z,x_1)$ between $x_1$ and $z$ is defined by the relation

$$\cos \angle(z,x_1)= \frac{z^{\ast} \, x_1} {\left\Vert z\right\Vert _2 \, \Vert x_1\Vert _2} .$$

If the starting vector $z$ and the eigenvector $x_1$ are perpendicular to each other, then $\cos\angle(z,x_1) = 0$. In this case the power method does not converge in exact arithmetic. On the other hand, if $\cos \angle(z,x_1)\not=0$, the power method generates a sequence of vectors that become increasingly parallel to $x_1$. This condition on $\angle(z,x_1)$ is true with very high probability if $z$ is chosen at random.

The convergence rate of the power method depends on $\vert \lambda_2 / \lambda_1\vert$, where $\lambda_2$ is the second largest eigenvalue of $A$ in magnitude. This ratio is generally smaller than $1$, allowing adequate convergence. But there are cases where this ratio can be very close to $1$, causing very slow convergence. For detailed discussions on the power method, see Demmel [114, Chap. 4], Golub and Van Loan [198], and Parlett [353].