Fast verification of solutions of matrix equations (Q1348935): Difference between revisions
From MaRDI portal
Removed claims |
Set OpenAlex properties. |
||
(5 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Shin'ichi Oishi / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Siegfried Michael Rump / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: BLAS / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: Matlab / rank | |||
Normal rank | |||
Property / describes a project that uses | |||
Property / describes a project that uses: mctoolbox / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s002110100310 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2077793630 / rank | |||
Normal rank |
Revision as of 18:53, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast verification of solutions of matrix equations |
scientific article |
Statements
Fast verification of solutions of matrix equations (English)
0 references
21 May 2002
0 references
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.
0 references
rigorous error bounds
0 references
result verification
0 references
linear systems
0 references
fast algorithms
0 references
directed rounding
0 references
preconditioning
0 references
\(LU\)-decomposition
0 references
Gaussian elimination
0 references
underflow
0 references
nonsingularity
0 references
floating point analysis
0 references