Fast verification of solutions of matrix equations
type: Item
instance of: scholarly article
title: Fast verification of solutions of matrix equations
zbMATH Open document ID: 0999.65015
published in: Numerische Mathematik
publication date: 2002-05-21T00:00:00Z
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.
reviewed by: Günter Mayer
Mathematics Subject Classification ID: 65F05
Mathematics Subject Classification ID: 65G20
Mathematics Subject Classification ID: 65F35
zbMATH DE Number: 1742796
zbMATH Keywords: rigorous error bounds
zbMATH Keywords: result verification
zbMATH Keywords: linear systems
zbMATH Keywords: fast algorithms
zbMATH Keywords: directed rounding
zbMATH Keywords: preconditioning
zbMATH Keywords: \(LU\)-decomposition
zbMATH Keywords: Gaussian elimination
zbMATH Keywords: underflow
zbMATH Keywords: nonsingularity
zbMATH Keywords: floating point analysis
author: Shin'ichi Oishi
author: Siegfried M. Rump
describes a project that uses: BLAS
describes a project that uses: Matlab
describes a project that uses: mctoolbox
MaRDI profile type: Publication
full work available at URL: s002110100310
OpenAlex ID: W2077793630
DOI: 10.1007/S002110100310
description: scientific article; zbMATH DE number 1742796