Remote Access Mathematics of Computation
Green Open Access

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

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

Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society