Multiplicative perturbation analysis  for QR factorizations

Xiao-Wen Chang; Ren-Cang Li

doi:10.3934/naco.2011.1.301

Article Contents

2011, Volume 1, Issue 2: 301-316. Doi: 10.3934/naco.2011.1.301

This issue Previous Article Proximal point nonlinear rescaling method for convex optimization Next Article Stability analysis of parametric variational systems

Multiplicative perturbation analysis for QR factorizations

Xiao-Wen Chang^1, and
Ren-Cang Li^2,

1.
School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A7
2.
Department of Mathematics, University of Texas at Arlington, Arlington, TX 76019-0408

Received: December 2010

Revised: May 2011

Published: June 2011

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 15A23; 65F35.

Citation:

Related Papers

Cited by

References

[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.