Back to Search
Start Over
PROBABILISTIC ROUNDING ERROR ANALYSIS OF HOUSEHOLDER QR FACTORIZATION.
- Source :
-
SIAM Journal on Matrix Analysis & Applications . 2023, Vol. 44 Issue 3, p1146-1163. 18p. - Publication Year :
- 2023
-
Abstract
- The standard worst-case normwise backward error bound for Householder QR factorization of an m x n matrix is proportional to mnu, where u is the unit roundoff. We prove that the bound can be replaced by one proportional to √mnu that holds with high probability if the rounding errors are mean independent and of mean zero and if the normwise backward errors in applying a sequence of m x m Householder matrices to a vector satisfy bounds proportional to √mu with probability 1. The proof makes use of a matrix concentration inequality. The same square rooting of the error constant applies to two-sided transformations by Householder matrices and hence to standard QR-type algorithms for computing eigenvalues and singular values. It also applies to Givens QR factorization. These results complement recent probabilistic rounding error analysis results for inner product-based algorithms and show that the square rooting effect is widespread in numerical linear algebra. Our numerical experiments, which make use of a new backward error formula for QR factorization, show that the probabilistic bounds give a much better indicator of the actual backward errors and their rate of growth than the worst-case bounds. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954798
- Volume :
- 44
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Matrix Analysis & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 173209239
- Full Text :
- https://doi.org/10.1137/22M1514817