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.
Type de document :
Article dans une revue
SIAM Journal on Matrix Analysis and Applications, Society for Industrial and Applied Mathematics, 2014, 35 (2), pp.684-698. 〈10.1137/130927231〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00841361
Contributeur : Claude-Pierre Jeannerod <>
Soumis le : mercredi 23 avril 2014 - 12:56:19
Dernière modification le : mardi 16 janvier 2018 - 16:10:21
Document(s) archivé(s) le : mercredi 23 juillet 2014 - 11:55:52

Fichier

RumpJeannerod14.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

376

Téléchargements de fichiers

148