The Power Method for Eigenvalues and Eigenvectors

The Power Method: An Iterative Recipe

Let's quickly recall the algorithm we'll be using, which is often called the Normalized Power Method:

1. Choose an initial non-zero vector ${\mathbf{x}}^{(0)}$. A vector of all ones, e.g., $\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right)$, is a common starting point.
2. For each iteration $k=1,2,3,\dots$:
   a. Multiply the matrix $A$ by the vector from the previous step: ${\mathbf{y}}^{(k)}=A{\mathbf{x}}^{(k-1)}$.
   b. Find the element of ${\mathbf{y}}^{(k)}$ with the largest absolute value. This value is our new estimate for the dominant eigenvalue, ${\lambda }_1$. Let's call it ${\mu }^{(k)}$.
   c. Scale the vector ${\mathbf{y}}^{(k)}$ by this value to get our new eigenvector approximation: ${\mathbf{x}}^{(k)}=\frac{1}{{\mu }^{(k)}}{\mathbf{y}}^{(k)}$.
3. Repeat this process until the values of ${\mu }^{(k)}$ and the vector ${\mathbf{x}}^{(k)}$ stabilize to a desired level of accuracy.

A Step-by-Step Demonstration

Watching someone work through a problem is often the best way to learn a numerical process. The following video demonstrates the Power Method on a 3x3 matrix, starting with an initial vector of all ones. It clearly shows the core loop of the algorithm: multiply, find the largest value, and normalize.

As you saw in the video, each iteration produces two key pieces of information:

• The Eigenvalue Approximation (${\mu }^{(k)}$): This is the scalar value you factor out at each step—the component of the unscaled vector with the largest magnitude. As you perform more iterations, this value will converge to the dominant eigenvalue.
• The Eigenvector Approximation (${\mathbf{x}}^{(k)}$): This is the normalized vector at the end of each iteration. Its components will converge to the corresponding components of the dominant eigenvector (scaled such that its largest component is 1).

Let's walk through another example in text form to solidify this process.

The table in the resource you just read beautifully illustrates the convergence. After 8 steps, the eigenvalue approximation is 9.000056 (very close to the true value of 9), and the eigenvector approximation is $\left(\begin{array}{c}0.400002\\ 1\end{array}\right)$, which is extremely close to the true eigenvector $\left(\begin{array}{c}0.4\\ 1\end{array}\right)$.

The image below shows a similar process for a different 2x2 matrix. It visually lays out the iteration on the left and the resulting approximation (eigenvalue estimate factored out, and the normalized eigenvector) on the right.

Notice how the eigenvalue estimate (the factor in front of the vector on the right) changes with each step: -4, 10, -22, 46, -94, 190. This doesn't seem to be converging! This is a good example of how the sign can flip if the dominant eigenvalue is negative, but the magnitude of the estimate will still converge. However, the vector itself does show signs of convergence. Look at the top component: 2.50, 2.80, 2.91, 2.96, 2.98, 2.99. It's clearly approaching 3.

When to Stop?

In an exam, you might be asked to perform a specific number of iterations. But if not, how do you know when to stop? You stop when the results are "good enough" for your needs. This is typically decided by checking the difference between successive approximations.

For example, you might decide to stop when the absolute difference between two consecutive eigenvalue estimates is less than some small tolerance, say 0.001:

Alternatively, you could check if the change in the eigenvector is minimal, often by checking the norm of the difference between ${\mathbf{x}}^{(k)}$ and ${\mathbf{x}}^{(k-1)}$. As the video LINK mentions around the end of its explanation, you continue until you get the "same answer" in repeated iterations, meaning the change is negligible.

Conclusion

In this lesson, we put the Power Method into practice. You have seen how to execute the iterative algorithm by hand through video and text-based examples, reinforcing each step of the process.

Here are the key takeaways from our practical application:

• The Power Method is a simple loop: Multiply the matrix by the current vector, identify the largest component, and scale the vector with that component.
• The scaling factor at each step, ${\mu }^{(k)}$, serves as the current approximation for the dominant eigenvalue.
• The resulting scaled vector, ${\mathbf{x}}^{(k)}$, is the current approximation for the dominant eigenvector.
• The process is repeated until the eigenvalue and eigenvector approximations converge to a desired level of precision.

So far, we've only focused on finding the largest eigenvalue. But what if we need to find the smallest eigenvalue? The Power Method can be cleverly adapted for this purpose as well. In our next lesson, we will explore the Inverse Power Method, which does exactly that.