Mathematics 172 – Numerical Analysis 2 Discussion 4 – A First Numerical Eigenvalue Technique April 15, 1999

Situation

Suppose we have a (real) n × n matrix A, and

• Assume that A is diagonalizable. Recall: (by definition) this means that there is a basis of R^{n} – β = {x_{1}, …, x_{n}} which consists of eigenvectors of A:

Ax_{i} = λ_{i}x_{i}

for each i = 1, …, n, and some scalars λ_{i} (the eigenvalues).

• Moreover, assume that there is a unique largest eigenvalue in absolute value, say λ_{1}: |λ_{1}| > |λ_{j}| for all j = 2, …, n. We will call λ_{1} the dominant eigenvalue.

If we take an arbitrary non-zero vector x and expand it in terms of the basis β consisting of eigenvectors of A:

(1)  x = c_{1}x_{1} + c_{2}x_{2} + … + c_{n}x_{n} ,

then the expansion of A^{k}x be for a general k ≥ 1 will be

\begin{aligned}A^{k}x & = c_{1}A^{k}x_{1} + c_{2}A^{k}x_{2} + ⋯ + c_{n}A^{k}x_{n} \\ & = c_{1}λ_{1}^{k}x_{1} + c_{2}λ_{2}^{k}x_{2} + ⋯ + c_{n}λ_{n}^{k}x_{n} \end{aligned}

It is not difficult to show that if we define

∥x∥_{β} = max_{1≤i≤n} |c_{i}|

using the coefficients from the expansion (1), then we get a vector norm on R^{n} (similar to the ∞ norm, but using the β-coordinates of vectors rather than the standard coordinates). We can assume from the start that ∥x_{i}∥_{β} = 1 also, if we like.

Questions

• Assuming c_{1} ≠ 0, what is the vector of β-norm = 1 in the direction of A^{k}x for large k? What happens to that vector as k → ∞? Does this give you an idea for a numerical technique to determine λ_{1}? (Note: To determine λ_{1}, it may help also to think about determining x_{1}, since Ax_{1} = λ_{1}x_{1}.)

• This “power method” yields only the dominant eigenvalue of A. But we might also possibly apply a similar idea with matrices derived from A to get other eigenvalues. For instance, how are the eigenvalues of A^{−1} related to the eigenvalues of A (assuming of course that A^{−1} exists!)? If we apply the method above using the matrix A^{−1}, what do we get as k → ∞?

• If we apply the method above using the matrix (A−sI)^{−1}, what do we get as k → ∞? Explain.