Analyzing Vector Orthogonalization Algorithms

.Computer implementations of vector orthogonalization algorithms produce a sequence of supposedly orthogonal vectors, but rounding-errors can cause loss of orthogonality and rank. Nevertheless these computational algorithms can be very effective as parts of various methods. We develop a general theory based on the augmented orthogonal matrix developed in [SIAM J. Matrix Anal. Appl., 31 (2009), pp. 565–583] that can be applied to any such algorithm. This can be combined with a rounding-error analysis of the algorithm to analyze its finite-precision behavior. We apply this combination to prove that a particular Lanczos tridiagonalization of a Hermitian matrix always computes components for which backward-stable solutions to \(Ax\!=\!b\), \(A\!=\!A^H\), exist. If an appropriate rounding-error analysis is available, the approach can apparently be applied to any computation producing a sequence of supposedly orthogonal \(n\)-vectors, where a linear combination of these vectors is intended to approximate some quantity.Keywordsvector orthogonalizationfinite-precision computationsloss of orthogonalityLanczos processthe method of conjugate gradients (CG)Krylov subspace methodsconvergence of iterative solution of equationslarge sparse matricesMSC codes65F1065F2565F3065F5065G5015A2315A57