American Institute of Mathematical Sciences

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

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, 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.
Keywords: perturbation analysis, multiplicative perturbation., QR factorization.
Mathematics Subject Classification: 15A23; 65F3.
Citation: Xiao-Wen Chang, Ren-Cang Li. Multiplicative perturbation analysis for QR factorizations. Numerical Algebra, Control & 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.  Google Scholar

[2]

R. Bhatia, "Matrix Analysis," Graduate Texts in Mathematics, Vol. 169. Springer, New York, 1997.  Google Scholar

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

[4]

Åke Björck, "Numerical Methods for Least Squares Problems," SIAM, Philadelphia, 1996.  Google Scholar

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

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

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

[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, ().   Google Scholar

[9]

G. H. Golub and C. F. Van Loan, "Matrix Computations," Johns Hopkins University Press, Baltimore, Maryland, 3rd edition, 1996.  Google Scholar

[10]

N. J. Higham, "Accuracy and Stability of Numerical Algorithms," SIAM, Philadephia, 2nd edition, 2002.  Google Scholar

[11]

R. C. Li, Relative perturbation bounds for the unitary polar factor, BIT, 37 (1997), 67-75. doi: doi:10.1007/BF02510173.  Google Scholar

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

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

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

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

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

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

[18]

G. W. Stewart and J. G. Sun, "Matrix Perturbation Theory," Academic Press, Boston, 1990.  Google Scholar

[19]

J. G. Sun, Perturbation bounds for the Cholesky and QR factorizations, BIT, 31 (1991), 341-352. doi: doi:10.1007/BF01931293.  Google Scholar

[20]

J. G. Sun, Componentwise perturbation bounds for some matrix decompositions, BIT, 32 (1992), 702-714. doi: doi:10.1007/BF01994852.  Google Scholar

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

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

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.  Google Scholar

[2]

R. Bhatia, "Matrix Analysis," Graduate Texts in Mathematics, Vol. 169. Springer, New York, 1997.  Google Scholar

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

[4]

Åke Björck, "Numerical Methods for Least Squares Problems," SIAM, Philadelphia, 1996.  Google Scholar

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

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

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

[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, ().   Google Scholar

[9]

G. H. Golub and C. F. Van Loan, "Matrix Computations," Johns Hopkins University Press, Baltimore, Maryland, 3rd edition, 1996.  Google Scholar

[10]

N. J. Higham, "Accuracy and Stability of Numerical Algorithms," SIAM, Philadephia, 2nd edition, 2002.  Google Scholar

[11]

R. C. Li, Relative perturbation bounds for the unitary polar factor, BIT, 37 (1997), 67-75. doi: doi:10.1007/BF02510173.  Google Scholar

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

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

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

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

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

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

[18]

G. W. Stewart and J. G. Sun, "Matrix Perturbation Theory," Academic Press, Boston, 1990.  Google Scholar

[19]

J. G. Sun, Perturbation bounds for the Cholesky and QR factorizations, BIT, 31 (1991), 341-352. doi: doi:10.1007/BF01931293.  Google Scholar

[20]

J. G. Sun, Componentwise perturbation bounds for some matrix decompositions, BIT, 32 (1992), 702-714. doi: doi:10.1007/BF01994852.  Google Scholar

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

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

[1]

Ilona Gucwa, Peter Szmolyan. Geometric singular perturbation analysis of an autocatalator model. Discrete & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021148
[13]

Alexander Tolstonogov. BV solutions of a convex sweeping process with a composed perturbation. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021012
[14]

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

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

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

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

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

Manxue You, Shengjie Li. Perturbation of Image and conjugate duality for vector optimization. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020176
[20]

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

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy