Perturbation Analyses for the QR Factorization

This paper gives perturbation analyses for Q₁ and R in the QR factorization A=Q₁R, Q₁TQ₁=I for a given real m× n matrix A of rank n and general perturbations in A which are sufficiently small in norm. The analyses more accurately reflect the sensitivity of the problem than previous such results. The condition numbers here are altered by any column pivoting used in AP=Q₁R, and the condition number for R is bounded for a fixed n when the standard column pivoting strategy is used. This strategy also tends to improve the condition of Q₁, so the computed Q₁ and R will probably both have greatest accuracy when we use the standard column pivoting strategy. First-order perturbation analyses are given for both Q₁ and R. It is seen that the analysis for R may be approached in two ways---a detailed "matrix--vector equation" analysis which provides a tight bound and corresponding condition number, which unfortunately is costly to compute and not very intuitive, and a simpler "matrix equation" analysis which provides results that are usually weaker but easier to interpret and which allows the efficient computation of satisfactory estimates for the actual condition number. These approaches are powerful general tools and appear to be applicable to the perturbation analysis of any matrix factorization.