Fast enclosure for solutions in underdetermined systems (Q989149)

To solve an underdetermined system \(Ax=b\) with \(A\in{\mathbb R}^{m\times n}\) of full rank, but \(m<n\), with minimal norm for \(x\) (all norms are 2-norms here), one may use the QR factorization of \(A^T\), solve \(Ry=b\), and set \(x=Qy\). If \(x^*\) is the exact solution and numerically computed values are indicated with a tilde, then this paper provides a method to estimate \(\|\tilde{x}-x^*\|\). The bound is given in terms of quantities that can be computed from the numerically obtained \(\tilde{Q}\) (its loss of orthogonality measured by \(\|\tilde{Q}^T\tilde{Q}-I\|\)), \(\tilde{R}\) (featuring in \(\|{\tilde{S}}(\tilde{R}^T\tilde{Q}^T-A)\|\) where \(\tilde{S}\) is a computed inverse of \(\tilde{R}\)), \(\tilde{w}\) with \(w=(R^TR)^{-1}b\) (appearing in \(\|\tilde{x}-A^T\tilde{w}\|\)), and \(\tilde{x}\) (e.g., via \(\|\tilde{S}(b-A\tilde{x})\|\)), and of course the rounding error unit and underflow unit. Upper bounds are relaxed by replacing numbers by their absolute values. It is assumed that errors are small enough so that the rank of the matrices is maintained. A further simplification of the computational procedure for the bound is proposed which gives an upper bound at the cost of \(m(m^2/3+mn+n^2)\) flops. This bound can be refined by an iterative procedure. The iterative procedure needs to store the residuals \(b-A\tilde{x}\) and \(\tilde{x}-A^T\tilde{w}\) in extended precision.