×

zbMATH — the first resource for mathematics

Nonsingularity, positive definiteness, and positive invertibility under fixed-point data rounding. (English) Zbl 1164.15310
Summary: For a real square matrix  \(A\) and an integer \(d\geq 0\), let \(A_{(d)}\) denote the matrix formed from \(A\) by rounding off all its coefficients to  \(d\) decimal places. The main problem handled in this paper is the following: assuming that \(A_{(d)}\)  has some property, under what additional condition(s) can we be sure that the original matrix  \(A\) possesses the same property? Three properties are investigated: nonsingularity, positive definiteness, and positive invertibility. In all three cases it is shown that there exists a real number  \(\alpha (d)\), computed solely from  \(A_{(d)}\) (not from \(A\)), such that the following alternative holds:
if \(d>\alpha (d)\), then nonsingularity (positive definiteness, positive invertibility) of  \(A_{(d)}\) implies the same property for  \(A\);
if \(d<\alpha (d)\) and \(A_{(d)}\)  is nonsingular (positive definite, positive invertible), then there exists a matrix \(A'\) with \(A'_{(d)}=A_{(d)}\) which does not have the respective property.
For nonsingularity and positive definiteness the formula for  \(\alpha (d)\) is the same and involves the computation of the NP-hard norm \(\| \cdot \| _{\infty ,1}\); for positive invertibility  \(\alpha (d)\) is given by an easily computable formula.
MSC:
15A12 Conditioning of matrices
15B48 Positive matrices and their generalizations; cones of matrices
15A09 Theory of matrix inversion and generalized inverses
65G50 Roundoff error
Software:
mctoolbox
PDF BibTeX Cite
Full Text: DOI EuDML
References:
[1] G. H. Golub, C. F. van Loan: Matrix Computations. The Johns Hopkins University Press, Baltimore, 1996.
[2] N. J. Higham: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia, 1996. · Zbl 0847.65010
[3] V. Kreinovich, A. Lakeyev, J. Rohn, and P. Kahl: Computational Complexity and Feasibility of Data Processing and Interval Computations. Kluwer Academic Publishers, Dordrecht, 1998. · Zbl 0945.68077
[4] S. Poljak, J. Rohn: Checking robust nonsingularity is NP-hard. Math. Control Signals Syst. 6 (1993), 1–9. · Zbl 0780.93027
[5] J. Rohn: Inverse-positive interval matrices. Z. Angew. Math. Mech. 67 (1987), T492–T493. · Zbl 0628.65027
[6] J. Rohn: Systems of linear interval equations. Linear Algebra Appl. 126 (1989), 39–78. · Zbl 0712.65029
[7] J. Rohn: Nonsingularity under data rounding. Linear Algebra Appl. 139 (1990), 171–174. · Zbl 0709.65036
[8] J. Rohn: Positive definiteness and stability of interval matrices. SIAM J. Matrix Anal. Appl. 15 (1994), 175–184. · Zbl 0796.65065
[9] J. Rohn: Computing the norm ||A||1 is NP-hard. Linear Multilinear Algebra 47 (2000), 195–204. · Zbl 0964.65049
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.