Solution of augmented linear systems using orthogonal factorizations (Q1343038)

The paper deals with solving \(x+ Ay= b\) and \(A^ T x= c\) for given vectors \(b\), \(c\) and an \(m\times n\) matrix \(A\) of rank \(n\). This system is called the augmented system formulation since it represents the necessary and sufficient conditions for the solution of the following two optimization problems: \(\min_ x\| b- x\|_ 2\) subject to \(A^ T x= c\) and \(\min_ y \{\| b- Ay\|^ 2_ 2+ 2c^ T y\}\). It is shown that the augmented system formulation can be effectively handled by various \(QR\)-factorizations of \(A\), where \(Q\) is orthogonal and \(R\) upper triangular. It is further shown that there exist backward stable algorithms where the \(QR\)-factorization is based on Householder transformations, rotations, or the modified Gram-Schmidt algorithm. When no part of \(Q\) is available, it is shown that the standard methods are not stable for the general augmented system formulation problem. Some iterative refinements are proposed to improve this.