Error Analysis of the Quasi-Gram--Schmidt Algorithm
G. W. Stewart · SIAM Journal on Matrix Analysis and Applications · 2005
Let the $n\,{\times}\,p$ $(n\geq p)$ matrix X have the QR factorization $X = QR$, where R is an upper triangular matrix of order p and Q is orthonormal. This widely used decomposition has the drawback that Q is not generally sparse even when X is. One cure is to discard Q, retaining only X and R. Products like $a = Q\trp y = R\itp X\trp y$ can then be formed by computing $b = X\trp y$ and solving the system $R\trp a = b$. This approach can be used to modify the Gram--Schmidt algorithm for computing Q and R to compute R without forming Q or altering X. Unfortunately, this quasi-Gram--Schmidt algorithm can produce inaccurate results. In this paper it is shown that with reorthogonalization the inaccuracies are bounded under certain natural conditions.