Probabilistic Rounding Error Analysis of Modified Gram–Schmidt
Qinmeng Zou · SIAM Journal on Matrix Analysis and Applications · 2024
Abstract. Building on probabilistic approaches, we study the finite precision behavior of modified Gram–Schmidt (MGS). Based on concentration inequalities and the Sheffield structure, we provide a rigorous probabilistic analysis of MGS in terms of residual, a form of backward error, and loss of orthogonality. In particular, when the QR factorization of a full column rank matrix [Formula: see text] is computed by MGS, the best-known worst-case bound in terms of loss of orthogonality is of order [Formula: see text] for unit roundoff [Formula: see text] and condition number [Formula: see text]. We show that this bound can be improved to [Formula: see text] with high probability.