Skip to Main content Skip to Navigation
Journal articles

Improved backward error bounds for LU and Cholesky factorizations

Abstract : Assuming standard floating-point arithmetic (in base $\beta$, precision $p$) and barring underflow and overflow, classical rounding error analysis of the LU or Cholesky factorization of an $n\times n$ matrix $A$ provides backward error bounds of the form $|\Delta A| \le \gamma_n |\hat L| |\hat U|$ or $|\Delta A| \le \gamma_{n+1} |\hat R^T| |\hat R|$. Here, $\hat L$, $\hat U$, and $\hat R$ denote the computed factors, and $\gamma_n$ is the usual fraction $nu/(1-nu) = nu + {\mathcal O}(u^2)$ with $u$ the unit roundoff. Similarly, when solving an $n\times n$ triangular system $Tx = b$ by substitution, the computed solution $\hat x$ satisfies $(T+\Delta T)\hat x = b$ with $|\Delta T| \le \gamma_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 $\gamma_n$ and $\gamma_{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 $|\rho-s|$, where $s$ is the exact sum of a floating-point number and $n-1$ real numbers, and where $\rho$ is a real number approximating the computed sum $\hat s$. By instantiating this framework with suitable values of $\rho$, we obtain improved versions of the well-known Lemma~8.4 in Higham's ASNA~\cite[p.~142]{Hig02} (used for analyzing triangular system solving and LU factorization) and of its Cholesky variant~\cite[solution to Problem~10.3]{Hig02}. All our results hold for rounding to nearest with any tie-breaking strategy and no matter what the order of summation.
Complete list of metadata
Contributor : Claude-Pierre Jeannerod <>
Submitted on : Wednesday, April 23, 2014 - 12:56:19 PM
Last modification on : Thursday, January 9, 2020 - 3:16:02 PM
Long-term archiving on: : Wednesday, July 23, 2014 - 11:55:52 AM


Files produced by the author(s)




Siegfried M. Rump, Claude-Pierre Jeannerod. Improved backward error bounds for LU and Cholesky factorizations. SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2014, 35 (2), pp.684-698. ⟨10.1137/130927231⟩. ⟨hal-00841361v2⟩



Record views


Files downloads