Article Contents
Article Contents

# Multiplicative perturbation analysis for QR factorizations

• This paper is concerned with how the QR factors change when a real matrix $A$ suffers from a left or right multiplicative perturbation, where $A$ is assumed to have full column rank. It is proved that for a left multiplicative perturbation the relative changes in the QR factors in norm are no bigger than a small constant multiple of the norm of the difference between the perturbation and the identity matrix. One of common cases for a left multiplicative perturbation case naturally arises from the computation of the QR factorization. The newly established bounds can be used to explain the accuracy in the computed QR factors. For a right multiplicative perturbation, the bounds on the relative changes in the QR factors are still dependent upon the condition number of the scaled $R$-factor, however. Some optimized'' bounds are also obtained by taking into account certain invariant properties in the factors.
Mathematics Subject Classification: 15A23; 65F35.

 Citation:

•  [1] R. Bhatia, Matrix factorizations and their perturbations, Linear Algebra Appl., 197/198 (1994), 245-276.doi: doi:10.1016/0024-3795(94)90490-1. [2] R. Bhatia, "Matrix Analysis," Graduate Texts in Mathematics, Vol. 169. Springer, New York, 1997. [3] R. Bhatia and K. Mukherjea, Variation of the unitary part of a matrix, SIAM J. Matrix Anal. Appl., 15 (1994), 1007-1014.doi: doi:10.1137/S0895479892243237. [4] Åke Björck, "Numerical Methods for Least Squares Problems," SIAM, Philadelphia, 1996. [5] X. W. Chang and C. C. Paige, Componentwise perturbation analyses for the QR factorization, Numer. Math., 88 (2001), 319-345.doi: doi:10.1007/PL00005447. [6] X. W. Chang, C. C. Paige and G. W. Stewart, Perturbation analyses for the QR factorization, SIAM J. Matrix Anal. Appl., 18 (1997), 775-791.doi: doi:10.1137/S0895479896297720. [7] X. W. Chang and D. Stehlé, Rigorous perturbation bounds of some matrix factorizations, SIAM J. Matrix Anal. Appl., 31 (2010), 2841-2859.doi: doi:10.1137/090778535. [8] X. W. Chang, D. Stehlé and G. Villard,  Perturbation Analysis of the QR Factor R in the Context of LLL Lattice Basis Reduction, 25 pages, submitted. [9] G. H. Golub and C. F. Van Loan, "Matrix Computations," Johns Hopkins University Press, Baltimore, Maryland, 3rd edition, 1996. [10] N. J. Higham, "Accuracy and Stability of Numerical Algorithms," SIAM, Philadephia, 2nd edition, 2002. [11] R. C. Li, Relative perturbation bounds for the unitary polar factor, BIT, 37 (1997), 67-75.doi: doi:10.1007/BF02510173. [12] R. C. Li, Relative perturbation theory: I. eigenvalue and singular value variations, SIAM J. Matrix Anal. Appl., 19 (1998), 956-982.doi: doi:10.1137/S089547989629849X. [13] R. C. Li, Relative perturbation theory: II. eigenspace and singular subspace variations, SIAM J. Matrix Anal. Appl., 20 (1999), 471-492.doi: doi:10.1137/S0895479896298506. [14] R. C. Li, Relative perturbation bounds for positive polar factors of graded matrices, SIAM J. Matrix Anal. Appl., 25 (2005), 424-433.doi: doi:10.1137/S0895479803437153. [15] R. C. Li and G. W. Stewart, A new relative perturbation theorem for singular subspaces, Linear Algebra Appl., 313 (2000), 41-51.doi: doi:10.1016/S0024-3795(00)00074-4. [16] G. W. Stewart, Perturbation bounds for the QR factorization of a matrix, SIAM J. Numer. Anal., 14 (1977), 509-518.doi: doi:10.1137/0714030. [17] G. W. Stewart, On the perturbation of LU, Cholesky and QR factorizations, SIAM J. Matrix Anal. Appl., 14 (1993), 1141-1146.doi: doi:10.1137/0614078. [18] G. W. Stewart and J. G. Sun, "Matrix Perturbation Theory," Academic Press, Boston, 1990. [19] J. G. Sun, Perturbation bounds for the Cholesky and QR factorizations, BIT, 31 (1991), 341-352.doi: doi:10.1007/BF01931293. [20] J. G. Sun, Componentwise perturbation bounds for some matrix decompositions, BIT, 32 (1992), 702-714.doi: doi:10.1007/BF01994852. [21] J. G. Sun, On perturbation bounds for the QR factorization, Linear Algebra Appl., 215 (1995), 95-112.doi: doi:10.1016/0024-3795(93)00077-D. [22] H. Zha, A componentwise perturbation analysis of the QR decomposition, SIAM J. Matrix Anal. Appl., 14 (1993), 1124-1131.doi: doi:10.1137/0614076.