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 & 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. doi: doi:10.1016/0024-3795(94)90490-1. Google Scholar

[2]

R. Bhatia, "Matrix Analysis,", Graduate Texts in Mathematics, (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. doi: doi:10.1137/S0895479892243237. Google Scholar

[4]

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

[5]

X. W. Chang and C. C. Paige, Componentwise perturbation analyses for the QR factorization,, Numer. Math., 88 (2001), 319. 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. 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. 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, (1996). Google Scholar

[10]

N. J. Higham, "Accuracy and Stability of Numerical Algorithms,", SIAM, (2002). Google Scholar

[11]

R. C. Li, Relative perturbation bounds for the unitary polar factor,, BIT, 37 (1997), 67. 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. 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. 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. 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. 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. 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. doi: doi:10.1137/0614078. Google Scholar

[18]

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

[19]

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

[20]

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

[21]

J. G. Sun, On perturbation bounds for the QR factorization,, Linear Algebra Appl., 215 (1995), 95. 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. 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. doi: doi:10.1016/0024-3795(94)90490-1. Google Scholar

[2]

R. Bhatia, "Matrix Analysis,", Graduate Texts in Mathematics, (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. doi: doi:10.1137/S0895479892243237. Google Scholar

[4]

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

[5]

X. W. Chang and C. C. Paige, Componentwise perturbation analyses for the QR factorization,, Numer. Math., 88 (2001), 319. 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. 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. 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, (1996). Google Scholar

[10]

N. J. Higham, "Accuracy and Stability of Numerical Algorithms,", SIAM, (2002). Google Scholar

[11]

R. C. Li, Relative perturbation bounds for the unitary polar factor,, BIT, 37 (1997), 67. 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. 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. 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. 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. 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. 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. doi: doi:10.1137/0614078. Google Scholar

[18]

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

[19]

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

[20]

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

[21]

J. G. Sun, On perturbation bounds for the QR factorization,, Linear Algebra Appl., 215 (1995), 95. 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. 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]

Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019041

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

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

[11]

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

[12]

Qingshan Yang, Xuerong Mao. Stochastic dynamics of SIRS epidemic models with random perturbation. Mathematical Biosciences & Engineering, 2014, 11 (4) : 1003-1025. doi: 10.3934/mbe.2014.11.1003

[13]

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

[14]

Roberto Garrappa, Eleonora Messina, Antonia Vecchio. Effect of perturbation in the numerical solution of fractional differential equations. Discrete & Continuous Dynamical Systems - B, 2018, 23 (7) : 2679-2694. doi: 10.3934/dcdsb.2017188

[15]

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

[16]

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

[17]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881

[18]

Zhaoli Liu, Jiabao Su. Solutions of some nonlinear elliptic problems with perturbation terms of arbitrary growth. Discrete & Continuous Dynamical Systems - A, 2004, 10 (3) : 617-634. doi: 10.3934/dcds.2004.10.617

[19]

Fabio Camilli, Annalisa Cesaroni. A note on singular perturbation problems via Aubry-Mather theory. Discrete & Continuous Dynamical Systems - A, 2007, 17 (4) : 807-819. doi: 10.3934/dcds.2007.17.807

[20]

Óscar Vega-Amaya, Joaquín López-Borbón. A perturbation approach to a class of discounted approximate value iteration algorithms with borel spaces. Journal of Dynamics & Games, 2016, 3 (3) : 261-278. doi: 10.3934/jdg.2016014

 Impact Factor: 

Metrics

  • PDF downloads (4)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]