Fast verification of solutions of matrix equations (Q1348935): Difference between revisions

The authors consider linear systems \(Ax= b\) with a real \(n\times n\) matrix \(A\) and \(n\)-vectors \(x\), \(b\). They present fast algorithms for proving nonsingularity of \(A\) and for computing rigorous bounds for \(\|A^{-1}b-\widetilde x\|_\infty\) where \(\|\cdot\|_\infty\) denotes the usual maximum norm and \(\widetilde x\) is an approximate solution of \(Ax= b\). Section 1 introduces into the subject, Section 2 recalls the basic facts of a floating point system including underflow and directed rounding. Involving such roundings it provides computed bounds for the defect \(A\widetilde x-b\). Section 3 is devoted to the verification of results. Together with their flops-rates it presents algorithms for computing bounds for \(RA-I\), \(\|A^{-1}\|_\infty\), \(\|A^{-1}b-\widetilde x\|_\infty\), \(\|X_U X_LPA- I\|_\infty\), \(\|X_UX_LP(A\widetilde x-b)\|_\infty\). Here, \(R\) is any preconditioning matrix, \(P\) is an appropriate permutation matrix such that \(PA\) has an \(LU\)-decomposition, \(X_L\), \(X_U\) are approximate inverses of the factors \(L\) and \(U\), respectively, for which \(PA\approx LU\) holds. Section 4 is based on the Gaussian elimination. Taking into account the possibility of underflow it contains matrix estimations for \(|PA- LU|\) and \(|XT-I|\) where \(T\) is a nonsingular triangular matrix and \(X\) is some approximate inverse of \(T\). A second bound for \(\|X_UX_LPA- I\|_\infty\) is derived which can be computed in \(O(n^2)\) flops. Section 5 uses the preceding algorithms and estimates and provides three ways to verify the nonsingularity of \(A\) and to estimate \(\|A^{-1}b-\widetilde x\|_\infty\). The corresponding calculations are performed in Matlab for several examples. The paper ends with conclusions and an appendix in which a rather technical floating point analysis for Section 4 is added.