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

DOI:
https://doi.org/10.1090/S0025-5718-1988-0929546-7

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.

**[1]**V. I. Arnol′d,*On matrices depending on parameters*, Uspehi Mat. Nauk**26**(1971), no. 2(158), 101–114 (Russian). MR**0301242****[2]**E. H. Bareiss & J. L. Barlow,*Probabilistic Error Analysis of Floating Point and CRD Arithmetics*, Dept. of Electrical Engineering and Computer Science, Northwestern University, Report 81-02-NAM-01, 1981.**[3]**J. W. Demmel,*A Numerical Analyst's Jordan Canonical Form*, Dissertation, Computer Science Division, University of California, Berkeley, 1983.**[4]**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**, https://doi.org/10.1007/BF01400115**[5]**C. Eckart & G. Young, "The approximation of one matrix by another of lower rank",*Psychometrika*, v. 1, 1936, pp. 211-218.**[6]**Herbert Federer,*Geometric measure theory*, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969. MR**0257325****[7]**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****[8]**Alfred Gray,*An estimate for the volume of a tube about a complex hypersurface*, Tensor (N.S.)**39**(1982), 303–305. MR**836947****[9]**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**, https://doi.org/10.1016/0040-9383(82)90005-2**[10]**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****[11]**R. W. Hamming,*On the distribution of numbers*, Bell System Tech. J.**49**(1970), 1609–1625. MR**0267809**, https://doi.org/10.1002/j.1538-7305.1970.tb04281.x**[12]**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**, https://doi.org/10.2307/2371512**[13]**D. Hough,*Explaining and Ameliorating the Ill Condition of Zeros of Polynomials*, Thesis, Mathematics Department, University of California, Berkeley, CA, 1977.**[14]**W. Kahan, "Numerical linear algebra,"*Canad. Math. Bull.*, v. 9, 1966, pp. 757-801. (Gastinel's theorem appears here.)**[15]**W. Kahan,*Conserving Confluence Curbs Ill-Condition*, Technical Report 6, Computer Science Dept., University of California, Berkeley, August 4, 1972.**[16]**Tosio Kato,*Perturbation theory for linear operators*, Die Grundlehren der mathematischen Wissenschaften, Band 132, Springer-Verlag New York, Inc., New York, 1966. MR**0203473****[17]**Keith Kendig,*Elementary algebraic geometry*, Springer-Verlag, New York-Berlin, 1977. Graduate Texts in Mathematics, No. 44. MR**0447222****[18]**Donald E. Knuth,*The art of computer programming. Vol. 2*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**633878****[19]**E. Kostlan,*Statistical Complexity of Numerical Linear Algebra*, Dissertation, Math. Dept., University of California, Berkeley, 1985.**[20]**P. Lelong,*Fonctions plurisousharmoniques et formes différentielles positives*, Gordon & Breach, Paris-London-New York (Distributed by Dunod éditeur, Paris), 1968 (French). MR**0243112****[21]**A. Ocneanu,*On the Volume of Tubes About a Real Variety*, unpublished report, Mathematical Sciences Research Institute, Berkeley, 1985.**[22]**A. Ocneanu,*On the Loss of Precision in Solving Large Linear Systems*, Technical Report, Mathematical Sciences Research Institute, Berkeley, 1985.**[23]**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**, https://doi.org/10.1287/moor.12.1.121**[24]**John R. Rice,*A theory of condition*, SIAM J. Numer. Anal.**3**(1966), 287–310. MR**0211576**, https://doi.org/10.1137/0703023**[25]**Axel Ruhe,*Properties of a matrix with a very ill-conditioned eigenproblem*, Numer. Math.**15**(1970), 57–60. MR**0266416**, https://doi.org/10.1007/BF02165660**[26]**Luis A. Santaló,*Integral geometry and geometric probability*, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac; Encyclopedia of Mathematics and its Applications, Vol. 1. MR**0433364****[27]**Steve Smale,*The fundamental theorem of algebra and complexity theory*, Bull. Amer. Math. Soc. (N.S.)**4**(1981), no. 1, 1–36. MR**590817**, https://doi.org/10.1090/S0273-0979-1981-14858-8**[28]**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****[29]**G. W. Stewart,*Error and perturbation bounds for subspaces associated with certain eigenvalue problems*, SIAM Rev.**15**(1973), 727–764. MR**0348988**, https://doi.org/10.1137/1015095**[30]**Gabriel Stolzenberg,*Volumes, limits, and extensions of analytic varieties*, Lecture Notes in Mathematics, No. 19, Springer-Verlag, Berlin-New York, 1966. MR**0206337****[31]**Paul R. Thie,*The Lelong number of a point of a complex analytic set*, Math. Ann.**172**(1967), 269–312. MR**0214812**, https://doi.org/10.1007/BF01351593**[32]**B. L. Van Der Waerden,*Modern Algebra*, Vol. 1, Ungar, New York, 1953.**[33]**Hermann Weyl,*On the Volume of Tubes*, Amer. J. Math.**61**(1939), no. 2, 461–472. MR**1507388**, https://doi.org/10.2307/2371513**[34]**J. H. Wilkinson,*Rounding errors in algebraic processes*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR**0161456****[35]**J. H. Wilkinson,*The algebraic eigenvalue problem*, Clarendon Press, Oxford, 1965. MR**0184422****[36]**J. H. Wilkinson,*Note on matrices with a very ill-conditioned eigenproblem*, Numer. Math.**19**(1972), 176–178. MR**0311092**, https://doi.org/10.1007/BF01402528**[37]**J. H. Wilkinson,*On neighbouring matrices with quadratic elementary divisors*, Numer. Math.**44**(1984), no. 1, 1–21. MR**745082**, https://doi.org/10.1007/BF01389751**[38]**J. H. Wilkinson,*Sensitivity of eigenvalues*, Utilitas Math.**25**(1984), 5–76. MR**752846**

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

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

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1988-0929546-7

Article copyright:
© Copyright 1988
American Mathematical Society