scientific article; zbMATH DE number 1786285
The authors investigate the backward error for a linear program \(P(A,b,c): \min c^Tx\) s.t. \(A^TX\leq b\) where \(A\) denotes the \(n\times p\) matrix, \(c\in\mathbb{R}^n\) and \(b\in\mathbb{R}^p\). A solution \((X,Y)\) of this program satisfies the conditions (C): \(A^TX\leq b\), \(Y\geq 0\), \(Y^T(A^TX-b)=0\) and \(Y^TA= c\). For practical situations, the authors state the desirability of obtaining an approximate solution \((X',Y')\) to \(P(A,b,c)\) where \((X',Y')\) is an exact solution of an approximate problem \(P'(A',b',c')\). For this the best approximation problem considered is \[ (\text{BE}):\inf_{(A',b',c')\in C}\bigl \|(A', b',c')-(A,b,c) \bigr\|^2 \] where \(\|(A',b',c')- (A,b,c)\|^2= \|A'-A \|^2_F+ \|b'-b\|^2 +\|c'-c\|^2\), \(\|\cdot \|_F\) is the Frobenius norm for \(n\times p\) matrices, and where \(C\), the set of constraints, is the set of \((A',b',c')\in \mathbb{R}^{np} \times\mathbb{R}^p \times\mathbb{R}^n\) such that \((A',b',c',X',Y')\) satisfies (C) above. The solution \((A^*,b^*,c^*)\) of \((\text{BE}) \) is computed explicitly together with the estimate of the distance \(\|A^*-A\|_F\). The backward error analysis viewpoint is known in the literature and in the context of linear programming is discussed by \textit{N. Megiddo} [Contemp. Math. 114, 35-50 (1990; Zbl 0747.90065)].
- Estimating the backward error for the least-squares problem with multiple right-hand sides
- Backward error bounds for constrained least squares problems
- scientific article; zbMATH DE number 19423
- On the accuracy of the Karlson-Waldén estimate of the backward error for linear least squares problems
- scientific article; zbMATH DE number 4049378
- Estimation of optimal backward perturbation bounds for the linear least squares problem
- Simple backward error bounds for linear least-squares problems
- On optimal backward perturbation bounds
- Linearization estimates of the backward errors for least squares problems.
- scientific article; zbMATH DE number 2077806
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4547593)
