Chapter 6

Vector iteration (power method)

6.1Simple vector iteration

In this chapter we consider the simplest method to compute a single extremal eigenvalue.

The hope is that x(k) converges to the eigenvector belonging to the eigenvalue of largest magnitude. As we are interested only in the direction but not in the length of the eigenvector, there is no need to normalize the iterates in (6.1), well at least in theory. In practice, x(k) may either underflow (if kAk < 1) or overflow (if kAk > 1) for large k. Thus, one usually adds a normalization step to (6.1), leading to Algorithm 6.1.

Algorithm 6.1 Simple vector iteration

1:Choose a starting vector x(0) Fn with kx(0)k = 1.

2:k = 0.

3:repeat

4:k := k + 1;

5:y(k) := Ax(k−1);

6:µk := ky(k)k;

7:x(k) := y(k)/µk;

8:until a convergence criterion is satisfied

may assume without loss of generality (w.l.o.g.) that A is upper triangular.

111

6.2Convergence analysis

Let us now assume that (the upper triangular)

Then, the eigenvector of A corresponding to its largest eigenvalue λ1 is e1. We will now show that the iterates x(k) converge to e1. More precisely, we will show that the angle(x(k), e1) between x(k) and e1 goes to zero with k → ∞. Let

with kx(k)k = 1. Then,

If we omit the normalization kx(k)k = 1, which we will do for convenience, then this becomes

This means that for the convergence analysis we look at the iteration (6.1), while the actual implementation follows closely Algorithm 6.1.

First, we simplify the form of A in (6.4), by eliminating s1,

The vector t that realizes this transformation has to satisfy

λ1t + s1 − t S2 = 0 ,

or

This equation has a solution if and only if λ1 6 σ(S2) This is the case for assumption (6.5).

Thus,

t = s1(S2 − λ1I)−1.

Figure 6.1: Norms of powers of B in (6.10).

We will apply this theorem to the case M = λ−1 1S2, the matrix norm ||| · ||| will be the ordinary 2-norm. Thus, for any ε > 0 there is a K(ε) N with

We can choose ε such that

|µ2| + ε < 1.

With this we have

in particular,