Inexact Shift-and-Invert

Recall from §11.2.1 that with exact arithmetic and exact linear system solvers, the SI and the Cayley transform produce the same Krylov spaces and the same Ritz pairs. We have shown in the previous sections by theoretical arguments and numerical examples that the Cayley transform is a good choice when the linear systems are solved with a relative error tolerance $\tau$ smaller than 1.

When the Cayley transform is used, the linear system

$$(A -\mu B) w = (A - \theta B) x - s$$

is solved, where $\Vert s\Vert \leq \tau \Vert(A - \theta B) x\Vert$. This linear system can be written as

$$(A -\mu B) (w - x) = (\mu - \theta) B x - s \ .$$

So, with $z = (w- x)/(\mu-\theta)$ and $t = s/(\mu-\theta)$, we obtain the shift-and-invert linear system

$$(A -\mu B) z = B x - t,$$

where $\Vert t\Vert \leq \tau \Vert(A - \theta B) x\Vert/ (\mu-\theta)$. In other words, we can use the SI, but instead of a relative residual tolerance, we should use a tolerance that is proportional to the norm of the Ritz residual, $\Vert(A - \theta B) x\Vert$.