Rump, Siegfried M.Siegfried M.RumpJeannerod, Claude PierreClaude PierreJeannerod2020-10-262020-10-262014-05-27SIAM Journal on Matrix Analysis and Applications 2 (35): 684-698 (2014)http://hdl.handle.net/11420/7661Assuming 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.en1095-716220142684698SIAMBackward errorCholesky factorizationFloating-point summationLU factorizationRounding error analysisTriangular system solvingUnit in the first placeMathematikJournal Article10.1137/130927231Other