Options
Verified error bounds for matrix decompositions
Publikationstyp
Journal Article
Date Issued
2024
Sprache
English
Volume
45
Issue
4
Start Page
2155
End Page
2183
Citation
SIAM Journal on Matrix Analysis and Applications 45 (4): 2155-2183 (2024)
Publisher DOI
Scopus ID
ISSN
08954798
In this note we consider common matrix factorizations such as LU decomposition of a square and rectangular matrix, Cholesky and QR decomposition, singular value decomposition for square and rectangular matrices, and eigen-, Schur, and Takagi decomposition. We first note that well-conditioned factors tend to be sensitive to perturbations of the input matrix, while ill-conditioned factors tend to be insensitive. It seems that this behavior has not been recognized in numerical analysis. We develop a formula for the relation between the condition number of the factor and its sensitivity with respect to input perturbations, and give reasons for that. Our main focus is to describe verification methods for the factors of the mentioned decompositions. That means proving existence of the factorization together with rigorous entrywise error bounds for the factors. Our goal is to develop algorithms requiring \scrO(Pp2) operations for an m \times n matrix with P := max(m,n) and p := min(m,n). Moreover, bounds of high quality are aimed for, often not far from maximal accuracy. A main tool to achieve that is accurate dot products based on error-free transformations. Since preconditioning based on approximate inverses is used, our methods are restricted to full matrices.
Subjects
Cholesky decomposition | eigendecomposition | error-free transformations | INTLAB | LU decomposition | polar decomposition | QR decomposition | Schur decomposition | sensitivity of matrix factors | singular value decomposition | Takagi decomposition | verified inclusions