Options
Improved backward error bounds for LU and Cholesky factorizations
Publikationstyp
Journal Article
Date Issued
2014-05-27
Sprache
English
Author(s)
Institut
TORE-URI
Volume
35
Issue
2
Start Page
684
End Page
698
Citation
SIAM Journal on Matrix Analysis and Applications 2 (35): 684-698 (2014)
Publisher DOI
Scopus ID
Publisher
SIAM
Assuming standard floating-point arithmetic (in base β, precision p) and barring underflow and overflow, classical rounding error analysis of the LU or Cholesky factorization of an n×n matrix A provides backward error bounds of the form |ΔA| < γn|L̂||Û| or |ΔA| < γn+1|R̂T||R̂|. Here, L̂, Û, and R̂ denote the computed factors, and γn is the usual fraction nu/(1-nu) = nu+O(u2) with u the unit roundoff. Similarly, when solving an n×n triangular system Tx = b by substitution, the computed solution x̂ satisfies (T + ΔT)x̂ = b with |ΔT| < γn|T|. All these error bounds contain quadratic terms in u and limit n to satisfy either nu < 1 or (n + 1)u < 1. We show in this paper that the constants γn and γn+1 can be replaced by nu and (n + 1)u, respectively, and that the restrictions on n can be removed. To get these new bounds the main ingredient is a general framework for bounding expressions of the form |ρ - s|, where s is the exact sum of a floating-point number and n-1 real numbers and where ρ is a real number approximating the computed sum ŝ. By instantiating this framework with suitable values of ρ, we obtain improved versions of the well-known Lemma 8.4 from [N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd ed., SIAM, Philadelphia, 2002] (used for analyzing triangular system solving and LU factorization) and of its Cholesky variant. All our results hold for rounding to nearest with any tie-breaking strategy and whatever the order of summation.
Subjects
Backward error
Cholesky factorization
Floating-point summation
LU factorization
Rounding error analysis
Triangular system solving
Unit in the first place
DDC Class
510: Mathematik