A new approach to backward error analysis of LU factorization
type: Item
instance of: scholarly article
title: A new approach to backward error analysis of LU factorization
zbMATH Open document ID: 0944.65026
DOI: 10.1023/A:1022358300517
published in: BIT
publication date: 2000-09-24T00:00:00Z
review text: When performing the Gaussian algorithm for an \(n\times n\) linear system \(A{\mathbf x}={\mathbf f}\) on a computer one normally ends up with a vector \(\widetilde{\mathbf x}\) which by virtue of rounding errors does not equal the (unknown) exact solution \({\mathbf x}\) of the original system. In order to assess the quality of the approximation \(\widetilde{\mathbf x}\) compared with \({\mathbf x}\) one can interprete \(\widetilde{\mathbf x}\) as the exact solution of a modified linear system \((A+\Delta A)\widetilde{\mathbf x}={\mathbf f}\). This interpretation and estimations for some norm \(\|\Delta A\|\) of \(\Delta A\) are usually called backward error analysis for \(A{\mathbf x}={\mathbf f}\). \textit{J. H. Wilkinson} [The algebraic eigenvalue problem (1965; Zbl 0258.65037)] derived the inequality \[ \|\Delta A\|_\infty\leq 3n^3 \rho^W_n\|A\|_{\infty}u,\tag{1} \] where \(\|\cdot\|_\infty\) denotes the row sum norm for matrices, \(u\) is the roundoff unit, \(\rho^W_n:= \max_{j,i,k}|\widetilde a^{(j)}_{i,k}|/\) \(\max_{i,k}|a_{i,k}|\) is the growth factor and \(\widetilde a^{(j)}_{i,k}\) is the computed value in position \((i,k)\) after \(j\) steps of factorization. From (1) one can derive the forward error bound \[ {\|\widetilde{\mathbf x}-{\mathbf x}\|_\infty\over \|\widetilde{\mathbf x}\|_\infty}\leq 3n^3 \rho^W_n\kappa(A)u \] with the maximum norm \(\|\cdot\|_\infty\) for vectors and the condition number \(\kappa(A):=\|A\|_\infty\|A^{-1}\|_\infty\). Using a new backward error analysis for the LU-factorization the authors obtain the estimations \[ \|\Delta A\|_\infty\leq (\textstyle{{1\over 2}}n(n+ 1)+ 4(n- 1)) \rho_n\|A\|_\infty u \] and \[ {\|\widetilde{\mathbf x}-{\mathbf x}\|_\infty\over \|\widetilde{\mathbf x}\|_\infty}\leq (\textstyle{{1\over 2}} n(n+1)+ 4(n- 1)) \rho_n \kappa(A)u \] with the new growth factor \(\rho_n:= \max_j\|\widetilde A_j\|_\infty/\|A\|_\infty\). Here, \(\widetilde A_j\) denotes the computed \((n-j)\times (n-j)\) matrix obtained …
reviewed by: Günter Mayer
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65G50
zbMATH DE Number: 1354736
zbMATH Keywords: Gauss elimination
zbMATH Keywords: stability
zbMATH Keywords: lower triangular systems
zbMATH Keywords: band matrix
zbMATH Keywords: partial pivoting
zbMATH Keywords: numerical experiments
zbMATH Keywords: rounding errors
zbMATH Keywords: backward error analysis
zbMATH Keywords: growth factor
zbMATH Keywords: forward error bound
zbMATH Keywords: condition number
zbMATH Keywords: LU-factorization
author: Pierluigi Amodio
author: Francesca Mazzia
describes a project that uses: mctoolbox
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1354736