Since we can choose ε arbitrarily small, we have proved

Theorem 6.2 Let the eigenvalues of A Fn×n be arranged such that |λ1| > |λ2| ≥ |λ3| ≥ · · · ≥ |λn|. Let u1 and v1 be right and left eigenvectors of A corresponding to λ1, respectively. Then, the vector sequence generated by Algorithm 6.1 converges to u1 in the sense that

Proof. We only have to show the requirement v1x(0)2 6= 0. In the previous derivation we assumed y1(0) = 1. This was done for convenience since the iteration does not depend

on scalings. So, an equivalent assumption is y1(0) 6= 0. From this, we immediately obtain [1, −t ]x(0) 6= 0. But [1, −t ] is the left eigenvector of A in (6.4) corresponding to its largest eigenvalue. With the considerations after (6.3) this translates to the claimed condition

v1x(0) 6= 0.

Remark 6.4. The quantity µk in Algorithm 6.1 converges to |λ1|. The sign of λ1 can be found by comparing single components of y(k) and x(k−1).

Remark 6.5. The convergence of the vector iteration is faster the smaller the quotient

|λ2|/|λ1| is.

Remark 6.6. If v1x(0) = 0 then the vector iteration converges to an eigenvector corresponding to the second largest eigenvalue. In practice, rounding errors usually prevent this behaviour of the algorithm. After a long initial phase the x(k) turn to u1.

Remark 6.7. In case that λ1 6= λ2 but |λ1| = |λ2| there may be no convergence at all. An

6.3A numerical example

In the following MATLAB script we assume that A is upper triangular and that the largest eigenvalue (in modulus) is at position (1,1), i.e., |a1,1| > |aj,j | for all j > 1.

%Demo Simple Vector Iteration

%

n = 6; randn(’state’,0);

A = diag([n:-1:1]) + triu(randn(n),1) % upper triangular matrix

Figure 6.2: Plot of three important quantities: eigenvalue, angle between eigenvector approximation and exact eigenvector, convergence rate of eigenvector

e = eye(n,1); % Right eigenvector corresponding to largest

%eigenvalue A(1,1)

%----------------------------------------------------------

x=x0; ang = norm(x - e*(e’*x))

hist = [ang,nan,nan];

if ~exist(’tol’), tol = 100*eps; end oldang = nan;

hist = [hist; [mue,ang,ang/oldang]]; oldang = ang;

end

Because the solution is known, we can compute the angle between iterate and true solution. We can even use this angle in the stopping criterion. The matrix A is given by

A =

The development of three important quantities is given in Fig. 6.2. In Fig. 6.3 the case is depicted when the initial vector is chosen orthogonal to the left eigenvector corresponding to λ1 = 6. Initially, the approximated eigenvalue is 5. Because the stopping criterion

Figure 6.3: Plot of three important quantities: eigenvalue, angle between eigenvector approximation and exact eigenvector, convergence rate of eigenvector. Here, the initial vector is chosen orthogonal to the left eigenvector corresponding to the largest eigenvalue

does not hold, the iteration continues until eventually rounding errors take e ect.

6.4The symmetric case

Let us now consider the Hermitian/symmetric case. We again assume the now real eigenvalues to be arranged as in (6.5). But now the Schur decomposition of A becomes its spectral decomposition,

Therefore, in (6.4) we have s = 0 and S2 = diag(λ2, . . . , λn). In (6.6) we have t = 0, and in (6.8) we have x(k) = λk1y(k), i.e., x(k) equals y(k), up to scaling. Therefore, the convergence analysis for y(k) holds for x(k) as well.

In contrast to the general case, in the Hermitian case we approximate the eigenvalue by the Rayleigh quotient of x(k),

102

100

10−2

10−4

10−6

10−8

10−10

Figure 6.4: Simple vector iteration with τI40 − T40

This is a surprisingly high reduction in the number of iteration steps. Figure 6.5 shows the convergence history of this calculation. Again the doted lines indicate the convergence

102

100

10−2

10−4

10−6

10−8

10−10

Figure 6.5: Simple vector iteration with τI40 − T40 and starting vector (1, 1, . . . , 1)T

rates that are to be expected. The actual convergence rates are evidently much better. How can that be?

The eigenvectors of Tn resemble the eigenfunctions sin kx of the continuous eigenvalue problem. Therefore the coe cients corresponding to eigenvectors corresponding to eigenfunctions antisymmetric with respect to the point π/2 vanish. In particular x2 = 0. Therefore the convergence rate is not q = (τ −λ2)/(τ −λ1) but qˆ = (τ −λ3)/(τ −λ1). This is verified by the numbers given in Fig. 6.6 where the assymptotic corrected convergence rates qˆ and qˆ2 are indicated.