Page 142 - Numerical methods for chemical engineering

128 3 Matrix eigenvalue analysis

Convergence of power method with a degenerate
leading eigenvalue
We have assumed that |λ 1 | > |λ 2 |. What happens if |λ 1 |=|λ 2 |? In general, the power
[1]
[2]
method oscillates and the sequence v , v , . . . fails to converge. However, for the
special case of a Hermitian, positive-semidefinite matrix, all eigenvalues must be real and
non-negative. The only way that |λ 1 |=|λ 2 | is if λ 1 = λ 2 . In the limit k →∞,
k
k

k
c 1 λ w [1] + c 2 λ w [2] λ c 1 w [1] + c 2 w [2]
2
1
[k]
1
v ≈ k k = (3.141)
λ c 1 w
c 1 λ w [1] + c 2 λ w [2] k [1] + c 2 w [2]
1 2 1
[2]
Therefore, the method converges to some linear combination of w [1] and w . But, if both
w [1] and w [2] are eigenvectors for λ 1 = λ 2 , c 1 w [1] + c 2 w [2] is one as well and the power
method converges to an eigenvector for λ 1 = λ 2 , but the exact eigenvector found depends
upon the initial guess.
Finding the next largest eigenvalues of a
positive-semidefinite matrix
Let us say that by the power method we have found the largest magnitude eigenvalue λ 1
and its associated eigenvector w [1] for a positive-semidefinite matrix A. We now want to
compute the next largest eigenvalue λ 2 . To do so, we generate at random some new vector,
that we can express as a linear combination of eigenvectors,

v [0] = c 1 w [1] + c 2 w [2] +· · · + c N w [N]
(3.142)
[ j]
[ j]
Aw = λ j w c j ∈ C
[1]
As the eigenvectors of a Hermitian matrix are orthogonal, w [2] is orthogonal to w .We
then can project out the w [1] component by the operation,

˜ v [0] = I − w [1] w [1] T v [0] = v [0] − w [1] w [1] · v [0]
[1] [2] [N] [1]
= c 1 w + c 2 w +· · · + c N w − w (c 1 )
[2] [N]
= c 2 w +· · · + c N w (3.143)
We now take as our iteration rule,
T
[1] [1] [k]
I − w w A˜v
˜ v [k+1] = (3.144)
T
I − w [1] w [1] A˜v
[k]
[0]
In terms of the original expansion of v , the sequence is
k
k
c 2 λ w [2] +· · · + c N λ w [N]
N
2
˜ v [k] = k k (3.145)
c 2 λ w [2] +· · · + c N λ w
[N]
2 N
[2]
If |λ 2 | > |λ 3 |≥|λ 4 |≥· · · ≥|λ N |, this sequence converges to w . By continuing this
process, we compute the eigenvalues and eigenvectors in order of decreasing magnitude.