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.

[2]

R. Bhatia, "Matrix Analysis,", Graduate Texts in Mathematics, (1997).

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

[4]

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

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

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

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

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

[9]

G. H. Golub and C. F. Van Loan, "Matrix Computations,", Johns Hopkins University Press, (1996).

[10]

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

[11]

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

[18]

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

[19]

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

[20]

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

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

[22]

H. Zha, A componentwise perturbation analysis of the QR decomposition,, SIAM J. Matrix Anal. Appl., 14 (1993), 1124. doi: doi:10.1137/0614076.

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.

[2]

R. Bhatia, "Matrix Analysis,", Graduate Texts in Mathematics, (1997).

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

[4]

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

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

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

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

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

[9]

G. H. Golub and C. F. Van Loan, "Matrix Computations,", Johns Hopkins University Press, (1996).

[10]

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

[11]

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

[18]

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

[19]

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

[20]

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

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

[22]

H. Zha, A componentwise perturbation analysis of the QR decomposition,, SIAM J. Matrix Anal. Appl., 14 (1993), 1124. doi: doi:10.1137/0614076.

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