Abstract
We present a computational, simple and fast sufficient criterion to verify positive definiteness of a symmetric or Hermitian matrix. The criterion uses only standard floating-point operations in rounding to nearest, it is rigorous, it takes into account all possible computational and rounding errors, and is also valid in the presence of underflow. It is based on a floating-point Cholesky decomposition and improves a known result. Using the criterion an efficient algorithm to compute rigorous error bounds for the solution of linear systems with symmetric positive definite matrix follows. A computational criterion to verify that a given symmetric or Hermitian matrix is not positive definite is given as well. Computational examples demonstrate the effectiveness of our criteria.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R. P. Brent, C. Percival, and P. Zimmermann, Error Bounds on complex floating-point multiplication, to appear in Math. Comput.
L. Collatz, Einschließungssatz für die charakteristischen Zahlen von Matrizen, Math. Z., 48 (1942), pp. 221–226.
J. W. Demmel, On floating point errors in Cholesky, LAPACK Working Note 14 CS-89–87, Department of Computer Science, University of Tennessee, Knoxville, TN, USA, 1989.
I. S. Duff, R. G. Grimes, and J. G. Lewis, User’s guide for Harwell–Boeing sparse matrix test problems collection, Technical Report RAL-92-086, Computing and Information Systems Department, Rutherford Appleton Laboratory, Didcot, UK, 1992.
C. A. Floudas, Deterministic Global Optimization – Theory, Methods and Applications, Nonconvex Optimization and Its Applications, vol. 37, Kluwer Academic Publishers, Dordrecht, Boston, London, 2000.
N. J. Higham, Accuracy and Stability of Numerical Algorithms, 2nd edn, SIAM Publications, Philadelphia, 2002.
R. A. Horn and C. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 1985.
MATLAB User’s Guide, Version 7. The MathWorks Inc., 2004.
J. Rohn, Checking robust stability of symmetric interval matrices is NP-hard, Commentat. Math. Univ. Carol., 35 (1994), p. 795–797.
S. M. Rump, Verification methods for dense and sparse systems of equations, in Topics in Validated Computations – Studies in Computational Mathematics, J. Herzberger, ed., p. 63–136, Elsevier, Amsterdam, 1994.
S. M. Rump, INTLAB – INTerval LABoratory, in Developments in Reliable Computing, Tibor Csendes, ed., p. 77–104, Kluwer Academic Publishers, Dordrecht, 1999.
H. Rutishauser, Vorlesungen über numerische Mathematik. Band 1: Gleichungssysteme, Interpolation und Approximation. Band 2: Differentialgleichungen und Eigenwertprobleme, Mathematische Reihe, vol. 50/57, Birkhäuser, Basel–Stuttgart, 1976. English: Lectures on Numerical Analysis, Birkhäuser, Boston, 1990.
R. S. Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, N.J., 1962.
Author information
Authors and Affiliations
Corresponding author
Additional information
AMS subject classification (2000)
65G20, 15A18
Rights and permissions
About this article
Cite this article
Rump, S. Verification of Positive Definiteness. Bit Numer Math 46, 433–452 (2006). https://doi.org/10.1007/s10543-006-0056-1
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10543-006-0056-1