## The probability that a numerical analysis problem is difficult

HTML articles powered by AMS MathViewer

- by James W. Demmel PDF
- Math. Comp.
**50**(1988), 449-480 Request permission

## 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

- V. I. Arnol′d,
*On matrices depending on parameters*, Uspehi Mat. Nauk**26**(1971), no. 2(158), 101–114 (Russian). MR**0301242**
E. H. Bareiss & J. L. Barlow, - James Weldon Demmel,
*On condition numbers and the distance to the nearest ill-posed problem*, Numer. Math.**51**(1987), no. 3, 251–289. MR**895087**, DOI 10.1007/BF01400115
C. Eckart & G. Young, "The approximation of one matrix by another of lower rank", - Herbert Federer,
*Geometric measure theory*, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York, Inc., New York, 1969. MR**0257325** - Gene H. Golub and Charles F. Van Loan,
*Matrix computations*, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR**733103** - Alfred Gray,
*An estimate for the volume of a tube about a complex hypersurface*, Tensor (N.S.)**39**(1982), 303–305. MR**836947** - Alfred Gray,
*Comparison theorems for the volumes of tubes as generalizations of the Weyl tube formula*, Topology**21**(1982), no. 2, 201–228. MR**642000**, DOI 10.1016/0040-9383(82)90005-2 - Phillip A. Griffiths,
*Complex differential and integral geometry and curvature integrals associated to singularities of complex analytic varieties*, Duke Math. J.**45**(1978), no. 3, 427–512. MR**507455** - R. W. Hamming,
*On the distribution of numbers*, Bell System Tech. J.**49**(1970), 1609–1625. MR**267809**, DOI 10.1002/j.1538-7305.1970.tb04281.x - Harold Hotelling,
*Tubes and Spheres in n-Spaces, and a Class of Statistical Problems*, Amer. J. Math.**61**(1939), no. 2, 440–460. MR**1507387**, DOI 10.2307/2371512
D. Hough, - Tosio Kato,
*Perturbation theory for linear operators*, Die Grundlehren der mathematischen Wissenschaften, Band 132, Springer-Verlag New York, Inc., New York, 1966. MR**0203473** - Keith Kendig,
*Elementary algebraic geometry*, Graduate Texts in Mathematics, No. 44, Springer-Verlag, New York-Berlin, 1977. MR**0447222** - Donald E. Knuth,
*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR**633878**
E. Kostlan, - P. Lelong,
*Fonctions plurisousharmoniques et formes différentielles positives*, Gordon & Breach, Paris-London-New York; distributed by Dunod Éditeur, Paris, 1968 (French). MR**0243112**
A. Ocneanu, - J. Renegar,
*On the efficiency of Newton’s method in approximating all zeros of a system of complex polynomials*, Math. Oper. Res.**12**(1987), no. 1, 121–148. MR**882846**, DOI 10.1287/moor.12.1.121 - John R. Rice,
*A theory of condition*, SIAM J. Numer. Anal.**3**(1966), 287–310. MR**211576**, DOI 10.1137/0703023 - Axel Ruhe,
*Properties of a matrix with a very ill-conditioned eigenproblem*, Numer. Math.**15**(1970), 57–60. MR**266416**, DOI 10.1007/BF02165660 - Luis A. Santaló,
*Integral geometry and geometric probability*, Encyclopedia of Mathematics and its Applications, Vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac. MR**0433364** - Steve Smale,
*The fundamental theorem of algebra and complexity theory*, Bull. Amer. Math. Soc. (N.S.)**4**(1981), no. 1, 1–36. MR**590817**, DOI 10.1090/S0273-0979-1981-14858-8 - Steve Smale,
*Algorithms for solving equations*, Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 172–195. MR**934223** - G. W. Stewart,
*Error and perturbation bounds for subspaces associated with certain eigenvalue problems*, SIAM Rev.**15**(1973), 727–764. MR**348988**, DOI 10.1137/1015095 - Gabriel Stolzenberg,
*Volumes, limits, and extensions of analytic varieties*, Lecture Notes in Mathematics, No. 19, Springer-Verlag, Berlin-New York, 1966. MR**0206337** - Paul R. Thie,
*The Lelong number of a point of a complex analytic set*, Math. Ann.**172**(1967), 269–312. MR**214812**, DOI 10.1007/BF01351593
B. L. Van Der Waerden, - Hermann Weyl,
*On the Volume of Tubes*, Amer. J. Math.**61**(1939), no. 2, 461–472. MR**1507388**, DOI 10.2307/2371513 - J. H. Wilkinson,
*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456** - J. H. Wilkinson,
*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422** - J. H. Wilkinson,
*Note on matrices with a very ill-conditioned eigenproblem*, Numer. Math.**19**(1972), 176–178. MR**311092**, DOI 10.1007/BF01402528 - J. H. Wilkinson,
*On neighbouring matrices with quadratic elementary divisors*, Numer. Math.**44**(1984), no. 1, 1–21. MR**745082**, DOI 10.1007/BF01389751 - J. H. Wilkinson,
*Sensitivity of eigenvalues*, Utilitas Math.**25**(1984), 5–76. MR**752846**

*Probabilistic Error Analysis of Floating Point and CRD Arithmetics*, Dept. of Electrical Engineering and Computer Science, Northwestern University, Report 81-02-NAM-01, 1981. J. W. Demmel,

*A Numerical Analyst’s Jordan Canonical Form*, Dissertation, Computer Science Division, University of California, Berkeley, 1983.

*Psychometrika*, v. 1, 1936, pp. 211-218.

*Explaining and Ameliorating the Ill Condition of Zeros of Polynomials*, Thesis, Mathematics Department, University of California, Berkeley, CA, 1977. W. Kahan, "Numerical linear algebra,"

*Canad. Math. Bull.*, v. 9, 1966, pp. 757-801. (Gastinel’s theorem appears here.) W. Kahan,

*Conserving Confluence Curbs Ill-Condition*, Technical Report 6, Computer Science Dept., University of California, Berkeley, August 4, 1972.

*Statistical Complexity of Numerical Linear Algebra*, Dissertation, Math. Dept., University of California, Berkeley, 1985.

*On the Volume of Tubes About a Real Variety*, unpublished report, Mathematical Sciences Research Institute, Berkeley, 1985. A. Ocneanu,

*On the Loss of Precision in Solving Large Linear Systems*, Technical Report, Mathematical Sciences Research Institute, Berkeley, 1985.

*Modern Algebra*, Vol. 1, Ungar, New York, 1953.

## Additional Information

- © Copyright 1988 American Mathematical Society
- Journal: Math. Comp.
**50**(1988), 449-480 - MSC: Primary 65G99; Secondary 15A12, 60D05
- DOI: https://doi.org/10.1090/S0025-5718-1988-0929546-7
- MathSciNet review: 929546