Page 390 - Applied Numerical Methods Using MATLAB

POWER METHOD 379
Proof. According to Theorem 8.1, the eigenvectors {v n ; n = 1: N} of an N × N
matrix A whose eigenvalues are distinct are independent and thus can constitute
abasis for an N-dimensional linear space. Consequently, any initial vector x 0
can be expressed as a linear combination of the eigenvectors:

x 0 = α 1 v 1 + α 2 v 2 +· · · + α N v N (8.3.2)

Noting that Av n = λ n v n , we premultiply both sides of this equation by A
to get

Ax 0 = α 1 λ 1 v 1 + α 2 λ 2 v 2 +· · · + α N λ N v N

λ 2 λ N
= λ 1 α 1 v 1 + α 2 v 2 +· · · + α N v N
λ 1 λ 1
and repeat this multiplication over and over again to obtain
k
x k = A x 0
k k

= λ k λ 2 λ N k (8.3.3)
1
1 α 1 v 1 + α 2 v 2 +· · · + α N v N → λ α 1 v 1
λ 1 λ 1
which will converge to an eigenvector v 1 as long as α 1 = 0. Since we keep
scaling before multiplying at every iteration, the largest component of the limit
vector of the sequence generated by Eq. (8.3.1) must be λ 1 .

x k v 1 (8.1.1) v 1
x k+1 = A → A = λ 1 (8.3.4)
||x k || ∞ ||v 1 || ∞ ||v 1 || ∞
Note that the scaling prevents the overflow or underflow that would result from
|λ 1 | > 1or |λ 1 | < 1.

Remark 8.3. Convergence of Power Method

1. In the light of Eq. (8.3.3), the convergence speed of the power method
depends on how small the magnitude ratio (|λ 2 |/|λ 1 |) of the second largest
eigenvalue λ 2 over the largest eigenvalue λ 1 is.
2. We often use x 0 = [ 11 ·· · 1 ] as the initial vector. Note that
if it has no component in the direction of the eigenvector (v 1 )
2
corresponding to the dominant eigenvalue λ 1 —that is, α 1 = x 0 v 1 /||v 1 || =
ž
0 in Eq. (8.3.2)—the iteration of the scaled power method leads to the limit
showing the second largest magnitude eigenvalue λ 2 and its corresponding
eigenvector v 2 . But, if there is more than one largest (dominant) eigenvalue
of equal magnitude, it does not converge to either of them.