     Next: Computational Costs and Tradeoffs Up: Implicitly Restarted Arnoldi Method Previous: Convergence Properties   Contents   Index

## Numerical Stability

Robust implementations of a practical QR algorithm, such as are available in LAPACK , compute an approximate Schur form for a matrix that satisfies (128)

where is upper triangular, , and , where is machine precision (unit roundoff). The fact that is a direct result of the exclusive use of unitary transformations during the iteration. This is what makes the QR algorithm backward stable. In other words, the QR method computes the Schur form of a matrix that is near .

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  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 with . If we are successful in making then with . If is a Schur decomposition of then is an exact partial Schur decomposition of a nearby matrix .

It is more likely that convergence will be realized with a small last component of an eigenvector of ( ) at some stage. We still have with small relative to . If where is small ( , say), then (A + E) x = x , with and (assuming ). Thus, in any case, converged approximate eigenpairs are exact for a nearby matrix .

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 where is small relative to . A discussion of this is given in §7.6.6, and more detail is available in .     Next: Computational Costs and Tradeoffs Up: Implicitly Restarted Arnoldi Method Previous: Convergence Properties   Contents   Index
Susan Blackford 2000-11-20