Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

The probability that a numerical analysis problem is difficult


Author: James W. Demmel
Journal: Math. Comp. 50 (1988), 449-480
MSC: Primary 65G99; Secondary 15A12, 60D05
MathSciNet review: 929546
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Numerous problems in numerical analysis, including matrix inversion, eigenvalue calculations and polynomial zerofinding, share the following property: The difficulty of solving a given problem is large when the distance from that problem to the nearest "ill-posed" one is small. For example, the closer a matrix is to the set of non-invertible matrices, the larger its condition number with respect to inversion. We show that the sets of ill-posed problems for matrix inversion, eigenproblems, and polynomial zerofinding all have a common algebraic and geometric structure which lets us compute the probability distribution of the distance from a "random" problem to the set. From this probability distribution we derive, for example, the distribution of the condition number of a random matrix. We examine the relevance of this theory to the analysis and construction of numerical algorithms destined to be run in finite precision arithmetic.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65G99, 15A12, 60D05

Retrieve articles in all journals with MSC: 65G99, 15A12, 60D05


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1988-0929546-7
PII: S 0025-5718(1988)0929546-7
Article copyright: © Copyright 1988 American Mathematical Society