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

From MaRDI portal
RedirectionBot (talk | contribs)
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
    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
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references