Perturbation of systems of linear algebraic equations^∗ (Q4487064)

Consider two problems which are extensions of a classical perturbation problem for nonsingular systems of linear algebraic equations (LAEs): a) \(Ax=b\), \(A\in\mathbb{R}^{m\times n}\), \(b\in\mathbb{R}^m\) with real elements perturbed to \((A+E)y=b+e\); b) the least squares problem (LSP) \(\|Ax-b\|=\min_{z\in\mathbb{R}^n}\|Az-b\|\) with Euclidean norm perturbed to \(\|(A+E)y-(b+e)\|=\min_{z\in\mathbb{R}^n}\|(A+E)z- (b+e)\|\). The following results are proved for these problems: i) Suppose \(b\in R(A)\) and \(b+e\in R(A+E).\) If \(\|A^{\dag}\|<1\), then for any solution \(y\) of the perturbed LAEs, there is a solution \(x\) of the LAEs such that \({\|y-x\|\over\|x\|}\leq{\|A\|\|A^{\dag}\|\over 1-\|A^{\dag}E\|} ({\|e\|\over\|b\|}+{\|E\|\over\|A\|})\), where \(R(A)\) is the range of \(A\) and \(A^{\dag}\) is the generalized inverse of \(A\). ii) If \(\|A^{\dag}E\|<1\), then for any solution \(y\) of the perturbed LSP, there is a solution \(x\) of the LSP such that \({\|y-x\|\over\|x\|}\leq{\|A\|\|A^{\dag}\|\over 1-\|A^{\dag}E\|} [{\|EA^{\dag}\|\|r\|\over \|A\|\|x_{LS}\|}+(\|EA^{\dag}\|+1) ({\|e\|\over\|A\|\|x_{LS}\|}+{\|E\|\over\|A\|})]\). Moreover, this inequality gives an upper bound on the distance of \(y\) to the solution set of the LSP. \(A^{\dag}\) denotes in this case the Moore-Penrose generalized inverse, \(x_{LS}=A^{\dag}b\) is the minimal norm solution of the LSP and \(r=b-Ax_{LS}\).