Next: Convergence properties of the Up: Convergence properties of the Previous: subspace iteration in the   Contents   Index

The interaction between the subspace iteration and the Lanczos-Ritz values

Taking a look at the numerical examples in Chapter 6, sometimes it seems that there is no sign of the convergence of the subspace iteration. The proofs stated above are correct, but there is an interaction with the Lanczos behavior of the algorithm, which will sometimes lead to a slower subspace iteration convergence than expected. This can only happen when, all the vectors have a small component in one or more directions of the eigenspace connected to the dominant eigenvalues. Before we show by examples, that this happens in practice, we first give a condition under which we are sure that the subspace iteration lets the matrix converge to one having a diagonal block containing the dominant eigenvalues. As soon as some of the Ritz values approximate all of the dominant eigenvalues, this convergence behavior appears. To show this we assume that the initial matrix has two clusters of eigenvalues, and , with and . Suppose also that there is a gap between cluster and cluster , . Using the following notations and , we can write the matrix in the following way:

 (5.7)

with , , , and . From equation (5.7), we have the following equation for

Let the eigenvalue decomposition of be denoted as:
 (5.8)

where we assume that some of the eigenvalues of (in fact the Ritz values) approximate already the dominant eigenvalues . Let us denote with a set of eigenvalues , then we assume that

subspace iteration needs weak conditions before convergence can occur: has full rank and is far from being not of full rank. This corresponds to the demand that the last vectors projected on the invariant subspace connected to the dominant eigenvalues have a large component in every direction of this subspace.

Via an Householder transformation we can transform equation (5.7) into

Then we can substitute by its eigenvalue decomposition (5.8):

Note that is of full rank, if and only if is of full rank. We get

where is the projection matrix of size where is the identity matrix of size , with the dimension of . This means that:

 (5.9)

Note that is a square matrix.

Because there is a gap between the eigenvalues and , there will be a comparable gap between and . Hence the matrix at the left-hand side of equation (5.9) is far from singular. Therefore this is also true for the right-hand side, and is of full rank. Hence, has full rank.

In this paragraph, a brief explanation is given, why in certain situations the subspace iteration does not work immediately from the start. Suppose the size of the block is . We can write the matrix in decomposed form:

 (5.10)

Note that equals . Applying already the Householder transformation on the matrix gives us the following decomposition:
 (5.11)

The Ritz values are the eigenvalues of the two by two matrix:

In fact, to complete the previous step a Givens transformation should still be performed on the matrix , to make the last two rows and columns dependent, and thereby transforming the matrix into . Note that this last Givens transformation does not change the eigenvalues of the bottom right submatrix.

We show now that the weak assumptions to let the subspace iteration converge, are not satisfied. We prove that

does not have two large linearly independent components in the span of

We can write as a linear combination of the eigenvectors:

The coordinates of with respect to the dominant eigenvectors, are the following:

Using equation (5.10) and (5.11), we get that

Hence,

Because of the Householder transformation we know that , hence

Therefore,

This means that if lies almost in the same direction as then is almost singular. If the two largest eigenvalues this is the case. Note however that when , the subspace iteration will work immediately, because they are both extreme and immediately located by the Lanczos procedure.

Briefly spoken we have the following interaction between the Lanczos-Ritz value behavior, and the subspace iteration: the subspace iteration, will start converging as soon as the Lanczos-Ritz values have converged close enough to the dominant eigenvalues.

Next: Convergence properties of the Up: Convergence properties of the Previous: subspace iteration in the   Contents   Index
Raf Vandebril 2004-05-03