Page 202 - Matrices theory and applications

185
10.4. The Power Methods
The standard method is especially designed for the search for the optimal
parameter in the SOR method for a tridiagonal matrix, where we have to
compute the spectral radius of the Jacobi iteration matrix (Theorem 9.4.1).
10.4.1 The Standard Method
Let M ∈ M n (CC) be a matrix. We search for an approximation of its eigen-
value of maximum modulus, whenever only one such exists. The standard
n 0 n
method consists in choosing a norm on CC , a unit vector x ∈ CC ,and
k
then computing successively the vectors x by the formula
1 k
k+1
x := Mx .
k
Mx
The justification of this method is given in the following theorem.
Theorem 10.4.1 One assumes that Sp M contains only one element λ of
maximal modulus (that modulus is thus equal to ρ(M)).
k
If ρ(M)= 0, the method stops because Mx =0 for some k< n.
n
n
Otherwise, let CC = E ⊕ F be the decomposition of CC ,where E, F are
stable linear subspaces under M,with Sp(M| E )= {λ} and λ ∈ Sp(M| F ).
0
k
Assume that x ∈ F.Then Mx =0 for every k ∈ IN and:
1.
k
lim Mx = ρ(M). (10.6)
k→+∞
2.
¯ k
λ k
V := lim x
k→+∞ ρ(M)
is a unit eigenvector of M, associated to the eigenvalue λ.

3. If V j =0,then
k
(Mx ) j
lim = λ.
k→+∞ x k
j
Proof
The case ρ(M) = 0 is obvious because M is then nilpotent. We may thus
assume that ρ(M) > 0.
0
0
0
0
0
0
Let x = y + z be the decomposition of x with y ∈ E and z ∈ F.
k 0
0
k 0
By assumption, y =0. Since M| E is invertible, M y =0. Since M x =
k 0
k 0
k 0
k 0
k 0
M y + M z , M y ∈ E,and M z ∈ F, we conclude that M x =0.