A new approach to backward error analysis of LU factorization (Q1307235)

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 after \(j\) steps of factorization. Numerical experiments show that \(\rho_n\) is often of order \(\log_2n\) whereas \(\rho^W_n\) has order \(n\) or \(\sqrt n\). For particular, classes of matrices upper bounds for \(\rho_n\) are given.