2011, 1(2): 301-316. doi: 10.3934/naco.2011.1.301

Multiplicative perturbation analysis for QR factorizations

1. 

School of Computer Science, McGill University, Montreal, Quebec, Canada H3A 2A7, Canada

2. 

Department of Mathematics, University of Texas at Arlington, Arlington, TX 76019-0408, United States

Received  December 2010 Revised  May 2011 Published  June 2011

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.
Citation: Xiao-Wen Chang, Ren-Cang Li. Multiplicative perturbation analysis for QR factorizations. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 301-316. doi: 10.3934/naco.2011.1.301
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.

show all references

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.

[1]

Ilona Gucwa, Peter Szmolyan. Geometric singular perturbation analysis of an autocatalator model. Discrete and Continuous Dynamical Systems - S, 2009, 2 (4) : 783-806. doi: 10.3934/dcdss.2009.2.783

[2]

Paolo Luzzini, Paolo Musolino. Perturbation analysis of the effective conductivity of a periodic composite. Networks and Heterogeneous Media, 2020, 15 (4) : 581-603. doi: 10.3934/nhm.2020015

[3]

Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial and Management Optimization, 2020, 16 (4) : 2029-2044. doi: 10.3934/jimo.2019041

[4]

Dongxi Li, Ni Zhang, Ming Yan, Yanya Xing. Survival analysis for tumor growth model with stochastic perturbation. Discrete and Continuous Dynamical Systems - B, 2021, 26 (10) : 5707-5722. doi: 10.3934/dcdsb.2021041

[5]

Houssem Haddar, Alexander Konschin. Factorization method for imaging a local perturbation in inhomogeneous periodic layers from far field measurements. Inverse Problems and Imaging, 2020, 14 (1) : 133-152. doi: 10.3934/ipi.2019067

[6]

Feifei Cheng, Ji Li. Geometric singular perturbation analysis of Degasperis-Procesi equation with distributed delay. Discrete and Continuous Dynamical Systems, 2021, 41 (2) : 967-985. doi: 10.3934/dcds.2020305

[7]

Ziran Yin, Liwei Zhang. Perturbation analysis of a class of conic programming problems under Jacobian uniqueness conditions. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1387-1397. doi: 10.3934/jimo.2018100

[8]

Marc Massot. Singular perturbation analysis for the reduction of complex chemistry in gaseous mixtures using the entropic structure. Discrete and Continuous Dynamical Systems - B, 2002, 2 (3) : 433-456. doi: 10.3934/dcdsb.2002.2.433

[9]

Horst R. Thieme. Remarks on resolvent positive operators and their perturbation. Discrete and Continuous Dynamical Systems, 1998, 4 (1) : 73-90. doi: 10.3934/dcds.1998.4.73

[10]

Eduard Marušić-Paloka, Igor Pažanin. Homogenization and singular perturbation in porous media. Communications on Pure and Applied Analysis, 2021, 20 (2) : 533-545. doi: 10.3934/cpaa.2020279

[11]

Heinz Schättler, Urszula Ledzewicz. Perturbation feedback control: A geometric interpretation. Numerical Algebra, Control and Optimization, 2012, 2 (3) : 631-654. doi: 10.3934/naco.2012.2.631

[12]

Enrico Bernardi, Alberto Lanconelli. Stochastic perturbation of a cubic anharmonic oscillator. Discrete and Continuous Dynamical Systems - B, 2022, 27 (5) : 2563-2585. doi: 10.3934/dcdsb.2021148

[13]

John Boyd. Strongly nonlinear perturbation theory for solitary waves and bions. Evolution Equations and Control Theory, 2019, 8 (1) : 1-29. doi: 10.3934/eect.2019001

[14]

Annie Millet, Svetlana Roudenko. Generalized KdV equation subject to a stochastic perturbation. Discrete and Continuous Dynamical Systems - B, 2018, 23 (3) : 1177-1198. doi: 10.3934/dcdsb.2018147

[15]

Roberta Fabbri, Carmen Núñez, Ana M. Sanz. A perturbation theorem for linear Hamiltonian systems with bounded orbits. Discrete and Continuous Dynamical Systems, 2005, 13 (3) : 623-635. doi: 10.3934/dcds.2005.13.623

[16]

Manuel del Pino. Supercritical elliptic problems from a perturbation viewpoint. Discrete and Continuous Dynamical Systems, 2008, 21 (1) : 69-89. doi: 10.3934/dcds.2008.21.69

[17]

Haifeng Ma, Xiaoshuang Gao. Further results on the perturbation estimations for the Drazin inverse. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 493-503. doi: 10.3934/naco.2018031

[18]

Sondes khabthani, Lassaad Elasmi, François Feuillebois. Perturbation solution of the coupled Stokes-Darcy problem. Discrete and Continuous Dynamical Systems - B, 2011, 15 (4) : 971-990. doi: 10.3934/dcdsb.2011.15.971

[19]

Timothy Blass, Rafael de la Llave. Perturbation and numerical methods for computing the minimal average energy. Networks and Heterogeneous Media, 2011, 6 (2) : 241-255. doi: 10.3934/nhm.2011.6.241

[20]

Yang Cao, Jingxue Yin. Small perturbation of a semilinear pseudo-parabolic equation. Discrete and Continuous Dynamical Systems, 2016, 36 (2) : 631-642. doi: 10.3934/dcds.2016.36.631

 Impact Factor: 

Metrics

  • PDF downloads (125)
  • HTML views (0)
  • Cited by (10)

Other articles
by authors

[Back to Top]