Page 204 - Matrices theory and applications

10.4. The Power Methods
n−1
which is equivalent to (k/λ)
n−1 k−n+1
λ
k
n
v .
M x ∼
(n − 1)!
Hence,
k−n+1
n
v

λ
k k 0 /(n − 1)!. We deduce that 187
x ∼ .
n
|λ| v
n
Since v is an eigenvector of M, the claims of the theorem have been proved.
The case where the algebraic and geometric multiplicities of λ are equal
(that is, M| E = λI E ), for example if λ is a simple eigenvalue, is especially
k 0
k 0
favorable. Indeed, M y = λ y , and therefore
k 0
1 0 M z
k
x = y + O .
0
y |λ| k
Theorem 4.2.1 thus shows that the error
1
k 0
x − 0 y
y
tends to zero faster than
k

ρ(M| F )+
,
ρ(M)
for every > 0. The convergence is thus of order one, and becomes faster
as the ratio |λ 2 |/|λ 1 | becomes smaller (arranging the eigenvalues by nonin-
creasing moduli). However, the convergence is much slower when the Jordan
blocks of M relative to λ are nontrivial. The error decays then like 1/k in
general.
The situation is more delicate when ρ(M) is the modulus of several
k
distinct eigenvalues. The vector x , suitably normalized, does not converge
in general but “spins” closer and closer to the sum of the corresponding
k
eigenspaces. The observation of the asymptotic behavior of x allows us
to identify the eigendirections associated to the eigenvalues of maximal
k
modulus. The sequence Mx does not converge and depends strongly on
k
the choice of the norm. However, log Mx converges in the Cesaro sense,
that is, in the mean, to log ρ(M) (Exercise 12).
Remark:The hypothesis on x 0 is generic, in the sense that it is satisfied for
n
0
every choice of x 0 in an open dense subset of CC .Ifbychance x belongs to
F, the power method furnishes theoretically another eigenvalue, of smaller
modulus. In practice, a large enough number of iterations always allows for
the convergence to λ. In fact, the number λ is rarely exactly representable in
a computer. If it is not, the linear subspace F does not contain any nonzero
0
representable vector. Thus the vector x , or its computer representation,
does not belong to F, and Theorem 10.4.1 applies.