Robust implementations of a practical QR algorithm, such as are
available in LAPACK [12], compute an approximate Schur form for a
matrix that satisfies
Backward stability is a very reassuring quality for any numerical
algorithm, but it is important to keep in mind that backward stability alone
does not imply accurate answers. The accuracy of the computed eigenvalues and
eigenvectors depends upon the sensitivity (conditioning) of the
eigensystem of . A backward stable algorithm produces accurate answers
for well-conditioned problems.
The reader is referred to §7.13
for a more detailed discussion of this issue.
As explained in the last section, the IRAM is a truncated QR
iteration. In most implementations of the QR method, Householder
transformations are used to obtain the initial reduction to Hessenberg form.
The Arnoldi procedure,
if extended to steps, is simply another way to obtain
this reduction. The introduction of the orthogonal correction [96]
allows the Arnoldi procedure to produce a reduction of the same numerical
quality as the Householder reduction but it is more suitable to the
large scale setting. With this correction, the computed Arnoldi vectors
are unitary to within machine precision
,
and since the restarting mechanism involves the same unitary transformations
used in the QR mechanism, the IRAM is also backward stable.
At any stage of the IRAM iteration, we have
It is more likely that convergence will be realized with
a small last component of an eigenvector of (
)
at some stage. We still have
Through the use of the deflation techniques that we shall present here in
§7.6.6, it is possible to use unitary transformations to
obtain a backward stability statement with respect to
a partial Schur decomposition for a set of converged eigenvalues.
If there are
eigenvalues of
that have converged, it is
possible to construct a unitary matrix
such that the
leading
submatrix
of
is upper triangular
and