Projection onto Krylov Subspaces

The approach outlined in the introduction needs two ingredients: a useful subspace generated by matrix-vector products and a small eigenvalue problem that represents the action of \(A\) on that space.

Throughout this section, \(A\in\mathbb R^{n\times n}\). For complex matrices, replace transpose by conjugate transpose.

Why Keep Several Directions?

Starting from a unit vector \(q_1\), the power method repeatedly applies \(A\) and normalizes the result. It keeps one current direction. Instead, we can retain the space generated by all the products obtained so far:

\[ \boxed{ \mathcal K_k(A,q_1) =\operatorname{span}\{q_1,Aq_1,\ldots,A^{k-1}q_1\}. } \]

This is the Krylov subspace. It contains every linear combination of these vectors, giving us more freedom to approximate eigenvectors than the latest power iterate alone.

Each new product can add another direction, so the spaces are nested:

\[ \mathcal K_1\subseteq\mathcal K_2\subseteq\cdots. \]

The starting vector matters: if all these products remain in a particular invariant subspace, they cannot reveal eigenvectors outside it.

We generate these vectors by successive matrix-vector products, without forming powers of \(A\) as matrices.

Constructing the Small Problem

Suppose \(\mathcal K_k\) has dimension \(k\), with \(k\ll n\), and let

\[ Q_k=[q_1,\ldots,q_k], \qquad Q_k^TQ_k=I_k \]

be an orthonormal basis. If the space stops growing earlier, we use a basis of that smaller dimension.

Every vector in the subspace has the form \(u=Q_ky\), where \(y\) contains its \(k\) coordinates. Multiplication by \(A\) may take \(u\) outside the subspace. To describe its action using only these coordinates, we project \(Au\) back into the subspace:

\[ Q_kQ_k^TAu =Q_k(Q_k^TAQ_k)y. \]

Thus the small matrix

\[ \boxed{H_k=Q_k^TAQ_k} \]

represents multiplication by \(A\) followed by orthogonal projection. This construction is called Rayleigh–Ritz projection. It is well-defined even when \(A\) does not preserve the chosen subspace.

Once the basis is available, we can compute the eigenvalues of the small matrix \(H_k\) using the QR methods from the preceding chapter. We then need to interpret these eigenvalues as approximations for the original problem.

What Do Its Eigenpairs Tell Us?

Let \(H_ky=\theta y\), with \(\|y\|_2=1\), and set \(u=Q_ky\). The scalar \(\theta\) is a Ritz value, and the unit vector \(u\) is its Ritz vector. They are candidates for an eigenvalue and eigenvector of \(A\).

These pairs satisfy the eigenvector equation after projection onto the subspace. If the subspace is invariant under \(A\), they are exact eigenpairs of \(A\). Otherwise, their accuracy must be checked; solving the small problem alone does not make them exact.

The Connection to Arnoldi

Projection defines the small problem, but we still need an efficient way to construct \(Q_k\) and \(H_k\). Arnoldi builds the basis one orthonormal direction at a time and collects the projection coefficients during that construction.

The next section derives the algorithm and the matrix relation it produces. The following convergence section uses that relation to check Ritz residuals and explain the accuracy of the approximations.