Inexact Rational Krylov Method

In this section, we combine the ideas of the inexact Cayley transformation, the (Jacobi) Davidson method, and the rational Krylov method. Roughly speaking, we still have the same method as the inexact Cayley transform Arnoldi method or the preconditioned Lanczos method, with the only difference that the zero and the pole may be updated on each iteration. As with the preconditioned Lanczos method, the Ritz vectors are computed from the Hessenberg matrices. In addition, the Ritz values are also computed from the recurrence relation.

We now discuss the method in detail, using the algorithm of the rational Krylov method, designed for the inexact Cayley transforms, given below.

Let us analyze this algorithm step by step.
The solution of the linear system leads to the relations
(11.2) where is a Ritz vector
and is the associated Ritz value from the
previous
iteration, such that
the right-hand side is the residual
.
Since
, we can also write
, where
is called the continuation vector.
After the Gram-Schmidt orthogonalization, we have
, so we can rewrite (11.2) as

Collecting all equations for we have

which is another way of writing (11.3). Note that when is omitted from this equation, we obtain the usual rational Krylov subspace (RKS) recurrence relation. Also in this case, and are upper Hessenberg matrices and has full rank. Let denote the generalized Moore-Penrose inverse of . With , we can also write

which corresponds to (11.4). In other words, the RKS coefficient matrices and and the vectors can be considered as having been computed by the exact rational Krylov method applied to the perturbed problem . Similar to the term ``inexact'' Cayley transform, we talk about ``inexact'' rational Krylov method.

Before we continue, we must give some properties of the exact rational
Krylov method.
The following lemma explains how to compute Ritz values in the rational
Krylov method.

As with the (Jacobi) Davidson method, the RKS method applies an inexact Cayley transform to a vector. The difference lies in the way the Ritz pairs are computed. In the (Jacobi) Davidson method, the Ritz pairs result from a Galerkin projection of on the subspace. In the RKS method, the Ritz pairs are computed from the recurrence relation using Lemma 11.1, assuming that .

With the inexact Cayley transform, the transformation can be a large perturbation of the exact Cayley transform, but can still be used to compute one eigenpair, when is well chosen. The same is true here. The inexact rational Krylov method delivers an (or ) that is not random but small in the direction of the desired eigenpair, as long as the various parameters are properly set.

A Ritz pair computed by Algorithm 11.4 produces residual

defined by Lemma 11.1. The residual related to the original problem can be written as

or, following (11.6),

In order to have small residuals, must tend to zero. Mathematical arguments for the convergence of the inexact rational Krylov

method have been given by Lehoucq and Meerbergen [291] and De Samblanx [109]. We just give a summary of the theory and some numerical results. In [291] and [109], mathematical and heuristical arguments are given that such that, with (see §11.2.2), the residual satisfies the recurrence relation

When the term is dominant to for , then the convergence is dominated by the convergence of the exact rational Krylov process: . When the second term is dominant, we have ; i.e., converges towards zero with convergence ratio .

- If the underlying exact rational Krylov method converges linearly
with
a convergence ratio such that
and
if
a relative residual tolerance is used for the solution of the
linear
systems, the effective convergence ratio is approximately
.
Linear and superlinear convergence are obtained when is constant
for all
.
- When
on each iteration as in the Davidson or
Jacobi-Davidson method and
(see §11.2.5), then the convergence is quadratic.
The term converges quadratically to zero, whereas the second term
converges linearly, when does not depend on .
Typically, the convergence has a quadratic behavior until
becomes the dominant term in . From then on, the
convergence becomes linear with convergence ratio .
In practice, it is advised to pick proportional to in
order
to preserve the quadratic convergence.
With
, we obtain that

which shows quadratic convergence of the second term.