Article
MSC:
15A09,
15A12,
15A48,
65G40,
65G50 | MR 2305868 | Zbl 1164.15310 | DOI: 10.1007/s10492-007-0005-6
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
nonsingularity; positive definiteness; positive invertibility; fixed-point rounding
nonsingularity; positive definiteness; positive invertibility; fixed-point rounding
Summary:
For a real square matrix $A$ and an integer $d\ge 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: $\bullet $ if $d>\alpha (d)$, then nonsingularity (positive definiteness, positive invertibility) of $A_{(d)}$ implies the same property for $A$; $\bullet $ if $d<\alpha (d)$ and $A_{(d)}$ is nonsingular (positive definite, positive invertible), then there exists a matrix $A^{\prime }$ with $A^{\prime }_{(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 computation of the NP-hard norm $\Vert \cdot \Vert _{\infty ,1}$; for positive invertibility $\alpha (d)$ is given by an easily computable formula. 0178.57901 1013.81007 0635.58034 1022.81062 0372.43005 1058.81037 0986.81031 0521.33001 0865.65009 0847.65010 0945.68077 0780.93027 0628.65027 0712.65029 0709.65036 0796.65065 0964.65049
References:
[1] G. H. Golub, C. F. van Loan: Matrix Computations. The Johns Hopkins University Press, Baltimore, 1996. MR 1417720
[2] N. J. Higham: Accuracy and Stability of Numerical Algorithms. SIAM, Philadelphia, 1996. MR 1368629 | 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. MR 1491092
[4] S. Poljak, J. Rohn: Checking robust nonsingularity is NP-hard. Math. Control Signals Syst. 6 (1993), 1–9. DOI 10.1007/BF01213466 | MR 1358057
[5] J. Rohn: Inverse-positive interval matrices. Z. Angew. Math. Mech. 67 (1987), T492–T493. MR 0907667 | Zbl 0628.65027
[6] J. Rohn: Systems of linear interval equations. Linear Algebra Appl. 126 (1989), 39–78. MR 1040771 | Zbl 0712.65029
[7] J. Rohn: Nonsingularity under data rounding. Linear Algebra Appl. 139 (1990), 171–174. MR 1071707 | Zbl 0709.65036
[8] J. Rohn: Positive definiteness and stability of interval matrices. SIAM J. Matrix Anal. Appl. 15 (1994), 175–184. DOI 10.1137/S0895479891219216 | MR 1257627 | Zbl 0796.65065
[9] J. Rohn: Computing the norm $\Vert {A}\Vert _{\infty ,1}$ is NP-hard. Linear Multilinear Algebra 47 (2000), 195–204. DOI 10.1080/03081080008818644 | MR 1785027
Search
Partner of
