The Probability That a Numerical Analysis Problem is Difficult

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 noninvertible 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.