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

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

Let the eigenvalue decomposition of be denoted as:

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:

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:

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

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.