Fast verification of solutions of matrix equations

\(LU\)-decomposition directed rounding fast algorithms floating point analysis Gaussian elimination linear systems nonsingularity preconditioning result verification rigorous error bounds underflow

Mathematics Subject Classification ID

Direct numerical methods for linear systems and matrix inversion (65F05) Numerical computation of matrix norms, conditioning, scaling (65F35) Algorithms with automatic result verification (65G20)

Review text

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.

Recommendations

Cited in

(32)

Describes a project that uses

Uses Software

This page was built for publication: Fast verification of solutions of matrix equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1348935)