When Modified Gram-Schmidt Generates a Well-Conditioned Set of Vectors

L. Giraud and J. Langou

42 Avenue Gaspard Coriolis
31057 Toulouse Cedex 1, France.


Orthogonalization methods play a key role in many iterative methods. In this paper, we establish new properties for the modified Gram-Schmidt algorithm. We show why the modified Gram-Schmidt algorithm generates a well-conditioned set of vectors. This result holds under the assumption that the initial matrix is not "too ill-conditioned" in a way that is quantified. As a consequence we show that if two iterations of the algorithm are performed, the resulting algorithm produces a matrix whose columns are orthogonal up to machine precision. Finally we illustrate through a numerical experiment the sharpness of our result.