Approximating Eigenvalues and Eigenvectors

Math 303: Section 19

Dr. Janssen

Intro

\[ \def\R{{\mathbb R}} \def\b{{\mathbf{b}}} \def\x{{\mathbf{x}}} \def\v{{\mathbf{v}}} \def\w{{\mathbf{w}}} \DeclareMathOperator{\null}{Nul} \]

Preview Activity

Finding eigenvalues/eigenvectors is important! But the characteristic equation is often unwieldy and/or leads to approximations in its own right.

v = vector([1,0])
A = Matrix([[2,6],[5,3]])

for i in range(10):
    v = A*v
    largest_component=abs(max(v,key=abs))
    v=v/largest_component
    print(i)
    print(v)

0
(2/5, 1)
1
(1, 25/34)
2
(218/245, 1)
3
(1, 1825/1906)
4
(14762/15005, 1)
5
(1, 118825/119554)
6
(952058/954245, 1)
7
(1, 7623025/7629586)
8
(60997322/61017005, 1)
9
(1, 488037625/488096674)

Looks like the limiting vector is \(\left[\begin{matrix} 1 \\ 1 \end{matrix}\right]\), with eigenvalue 8.

So, taking larger powers of the matrix times an arbitrary starting vector seems to work! But why? And will it always?

The Power Method

Setup

Let \(A\) be an arbitrary \(2\times 2\) matrix with two linearly independent eigenvectors \(\v_1,\v_2\) corresponding to eigenvalues \(\lambda_1,\lambda_2\); we assume \(|\lambda_1| > |\lambda_2|\)¹.

1. In this case, we say \(\lambda_1\) is the dominant eigenvalue, and its eigenvector a dominant eigenvector.

The main argument

Since \(\v_1\) and \(\v_2\) are linearly independent, for any \(\x_0\in \R^2\) there exist \(a_1, a_2\in \R\) for which

\[ \x_0 = a_1 \v_1 + a_2 \v_2; \]

thus

\[ \x_k = A^k \x_0 = a_1 \lambda_1^k \v_1 + a_2 \lambda_2^k \v_2. \]

Activity 19.1

• Divide both sides of \(\x_k = a_1 \lambda_1^k \v_1 + a_2 \lambda_2^k \v_2\) by \(\lambda_1^k\); what happens as \(k\to \infty\)?

• Assuming \(a_1\ne 0\)¹, why do the vectors \(\x_k\) approach a vector in the direction of \(\v_1\) or \(-\v_1\)?

• What does this tell us about the sequence \(\{\x_k\}\) as \(k\to\infty\)?

If instead \(a_1 = 0\), then our initial guess doesn’t have any component in the direction of the (nonzero!) eigenvector we’re trying to approximate. Of course, the initial choice of seed isn’t that important, so we can just try another vector if the process doesn’t seem to be working.

1. Why do we need \(a_1 \ne 0\)? What if \(a_1 = 0\)?

Power Method: Pros and Cons

• Straightforward to implement!
• Find the (approximate) eigenvector without needing the associated eigenvalue
• Makes assumptions!
• \(A\) is diagonalizable
• \(A\) has a dominant eigenvalue

Rayleigh quotients: approximating \(\lambda\)

Activity 19.2

Let \(A\) be \(n\times n\), \(\lambda\) an eigenvalue, and \(\v\) the corresponding eigenvector.

• Explain why \(\lambda = \frac{\lambda (\v\cdot \v)}{\v\cdot \v}\).

• Use the previous result to explain why \(\lambda = \frac{(A\v)\cdot \v}{\v\cdot\v}\).

These quotients are called Rayleigh quotients.

The upshot is that when the vectors in the sequence \(\x_k\) approach a dominant eigenvector of \(A\), the quotients

\[ \frac{(A\x_k)\cdot \x_k}{\x_k\cdot \x_k} \]

approximate the dominant eigenvalue of \(A\).

The Process

• Select an arbitrary nonzero vector \(\x_0\) as an initial guess to a dominant eigenvector.
• Let \(\x_1 = A \x_0\), \(k = 1\)
• To avoid having the magnitudes of successive approximations become excessively large, scale this approximation by the entry \(\alpha_k\) in \(\x_k\) of largest absolute value. Then replace \(\x_k\) by \(\frac{1}{|\alpha_k|} \x_k\).
• Calculate the Rayleigh quotient \(r_k = \frac{(A\x_k)\cdot \x_k}{\x_k\cdot \x_k}\).
• Let \(\x_{k+1} = A \x_k\). Increase \(k\) by 1 and repeat steps 3 through 5.

If \(\x_k\) converges to a dominant eigenvector of \(A\), then \(r_k\) converges to the dominant eigenvalue of \(A\).

Book discusses another method, the Inverse Power Method, for approximating other (nondominant) eigenvalues/vectors under certain circumstances. We’re going to skip it.