Harmonic Ritz Values.

Our introduction of the Ritz values, in relation with Krylov subspaces, suggests that they tend to approximate exterior eigenvalues better than interior ones. This is supported by theory as well as borne out by experience. Ritz values that are located in the interior part of the spectrum can usually be considered as bad approximations for some exterior eigenvalues, and the corresponding Ritz vectors often have a small component in the eigenvector direction corresponding to the eigenvalue in the vicinity of which the Ritz value lies. One may say that this Ritz value is on its way to converging towards an exterior eigenvalue. This means that the Ritz vectors corresponding to interior eigenvalues are also often not suitable for restarting purposes if one is interested in interior eigenpairs. These restarts are necessary, in particular for interior eigenpairs, in order to avoid high-dimensional bases for $V$ and $W$.

An interesting particular case of oblique projection methods is the situation in which $\LL$ is chosen as $\LL = A \KK$. Similar to previous notation, let $V$ be a basis of $\KK$. Assuming that $A$ is nonsingular, we can take as a basis of $\LL$ the system of vectors $W = A V$. The approximate eigenvector $\tlu$ to be extracted from the subspace $\KK$ can be expressed in the form

$$\tlu = V y,$$

where $y$ is an $m$-dimensional vector. The approximate eigenvalue $\tla$ is obtained from the Petrov-Galerkin condition, which yields

$$(A V)^{\ast} (A - \tla I) V y = 0$$

or V^ A^ A V y = V^ A^ V y . This gives a generalized eigenvalue problem of size $m$ for which the left-hand-side matrix is Hermitian positive definite. A standard eigenvalue problem can be obtained by requiring that $AV$ be an orthonormal system. In this case, eq:HarmGen becomes V^ A^ V y = W^A^-1 W y =1 y . Since the matrix $W$ is orthonormal, this leads to the interesting observation that the method is mathematically equivalent to using an orthogonal projection process for computing eigenvalues of $A\inv$. The subspace of approximants in this case is $A \KK$. For this reason the approximate eigenvalues $\tla$ are referred to as harmonic Ritz values. Note that one does not have to invert $A$, but if one maintains the formal relation $W = A V$ by carrying out the orthogonal transformations on $W$ also on $V$, then one can use the left-hand side of (3.10) for the computation of the reduced matrix. Since the harmonic Ritz values are Ritz values for $A^{-1}$ (although with respect to a subspace that is generated for $A$), they tend to be increasingly better approximations for interior eigenvalues (those closest to the origin). One can show, for Hermitian $A$, that the harmonic Ritz vectors maximize Rayleigh quotients for $A^{-1}$ so that they can be interpreted as the best information that one has for the smallest (in absolute value) eigenvalues. This makes the harmonic Ritz vectors suitable for restarts and this was proposed, for symmetric matrices, by Morgan [331].

The formal introduction of harmonic Ritz values and vectors was given in [349], along with interesting relations between the Ritz pairs and the harmonic Ritz pairs. It was shown that the computation of the projected matrix $W^\ast A^{-1} W$ can be obtained as a rank-one update of the matrix $V^\ast A V$, in the case of Krylov subspaces, so that the harmonic Ritz pairs can be generated as cheap side-products of the regular Krylov processes. The generalization of the harmonic Ritz values for more general subspaces was published in [411].

Since the projection of $A^{-1}$ is carried out on a subspace that is generated for $A$, one should not expect this method to do as well as a projection on a Krylov subspace that has been generated with $A^{-1}$. In fact, the harmonic Ritz values are increasingly better approximations for interior eigenvalues, but the improvement for increasing subspace can be very marginal (although steady). Therefore, they are in general no alternative for shift-and-invert techniques, unless one succeeds in constructing suitable subspaces, for instance by using cheap approximate shift-and-invert techniques, as in the (Jacobi-) Davidson methods.

We will discuss the behavior of harmonic Ritz values and Ritz value in more detail for the Hermitian case $A^\ast =A$. Assume that the eigenvalues of $A$ are ordered by magnitude:

$$\la_1 \le \la_2 \le \cdots \le \la_n.$$

A similar labeling is assumed for the approximations $\tla_i$.

As has been mentioned before, the Ritz values approximate eigenvalues of a Hermitian matrix $A$ ``inside out,'' in the sense that the rightmost eigenvalues are approximated from below and the leftmost ones are approximated from above, as is illustrated in the following diagram.

This principle can be applied to harmonic Ritz values: since these are the result of an orthogonal projection method applied to $A\inv$, it follows that the harmonic Ritz eigenvalues $1/\tla_i$ obtained from the process will approximate corresponding eigenvalues $1/\la_i$ of $A$ in an inside-out fashion. For positive eigenvalues we have,

$$\tla_i\inv \le \la_i \inv; \quad i=1,2, \ldots \qquad \longrightarrow \qquad \tla_i \ge \la_i; \quad i=1,2, \ldots.$$

Observe that the largest positive eigenvalues are now approximated from above, in contrast with the standard orthogonal projection methods. These types of techniques were popular a few decades ago as a strategy for obtaining intervals that were certain to contain a given eigenvalue. In fact, as was shown in [349], the Ritz values together with the harmonic Ritz values form the so-called Lehmann intervals, which have nice inclusion properties for eigenvalues of $A$. In a sense, they provide the optimal information for eigenvalues of $A$ that one can derive from a given Krylov subspace. For example, a lower and upper bound to the (algebraically) largest positive eigenvalue can be obtained by using an orthogonal projection method and a harmonic projection method, respectively.

We conclude our discussion on harmonic Ritz values with the observation that they can be computed also for the shifted matrix $A-\sigma I$, so that one can force the approximations to improve for eigenvalues close to $\sigma$.

We must be cautious when applying this principle for negative eigenvalues that the order is reversed. Therefore, we label positive and negative eigenvalues separately. The above inequalities must be reversed for the negative eigenvalues, labeled from the (algebraically) smallest to the largest negative eigenvalues ( $\la_1^{-} \le \la_2^{-} \le ...$). The result is summarized in the following diagram.

Assume for simplicity that $A$ is SPD and define:

$$\KK\sup{i} = \{ x \ \in \KK\quad \vert \quad A x \perp A \tlu_1, A \tlu_2, \ldots A \tlu_{i-1} \}$$

with $\KK\sup{0} \bydef K$. Then the Courant characterization becomes,

$$\tla_i\inv = \max_{x \ \in \ \KK\sup{i}} \ \frac{ (A x , x ) }{ (A x,A x) }$$