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

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",*Russian Math. Surveys*, v. 26, 1971, pp. 29-43. MR**0301242 (46:400)****[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]**J. W. Demmel, "On condition numbers and the distance to the nearest ill-posed problem,"*Numer. Math.*, v. 51, 1987, pp. 251-289. MR**895087 (88i:15014)****[5]**C. Eckart & G. Young, "The approximation of one matrix by another of lower rank",*Psychometrika*, v. 1, 1936, pp. 211-218.**[6]**H. Federer,*Geometric Measure Theory*, Springer-Verlag, Berlin and New York, 1969. MR**0257325 (41:1976)****[7]**G. H. Golub & C. F. Van Loan,*Matrix Computations*, Johns Hopkins Univ. Press, Baltimore, MD, 1983. MR**733103 (85h:65063)****[8]**A. Gray, "An estimate for the volume of a tube about a complex hypersurface,"*Tensor*(N. S.), v. 39, 1982, pp. 303-305. MR**836947 (87c:53126)****[9]**A. Gray, "Comparison theorems for the volumes of tubes as generalizations of the Weyl tube formula,"*Topology*, v. 21, 1982, pp. 201-228. MR**642000 (83c:53064)****[10]**P. A. Griffiths, "Complex differential and integral geometry and curvature integrals associated to singularities of complex analytic varieties,"*Duke Math. J.*, v. 45, 1978, pp. 427-512. MR**507455 (80k:53101)****[11]**R. W. Hamming, "On the distribution of numbers,"*Bell System Tech. J.*, v. 49, 1970, pp. 1609-1625. MR**0267809 (42:2711)****[12]**H. Hotelling, "Tubes and spheres in*n*-spaces, and a class of statistical problems,"*Amer. J. Math.*, v. 61, 1939, pp. 440-460. MR**1507387****[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]**T. Kato,*Perturbation Theory for Linear Operators*, Springer-Verlag, Berlin and New York, 1966. MR**0203473 (34:3324)****[17]**K. Kendig,*Elementary Algebraic Geometry*, Springer-Verlag, Berlin and New York, 1977. MR**0447222 (56:5537)****[18]**D. E. Knuth,*The Art of Computer Programming*, Vol. 2, Addison-Wesley, Reading, Mass., 1969. MR**633878 (83i:68003)****[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 and Breach, Paris, 1968. MR**0243112 (39:4436)****[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 systems of complex polynomials,"*Math. Oper. Res.*, v. 12, 1987, pp. 121-148. MR**882846 (88j:65112)****[24]**J. R. Rice, "A theory of condition,"*SIAM J. Numer. Anal.*, v. 3, 1966, pp. 287-310. MR**0211576 (35:2454)****[25]**A. Ruhe, "Properties of a matrix with a very ill-conditioned eigenproblem,"*Numer. Math.*, v. 15, 1970, pp. 57-60. MR**0266416 (42:1322)****[26]**L. A. Santaló,*Integral Geometry and Geometric Probability*, Encyclopedia of Mathematics and Its Applications, Vol. 1, Addison-Wesley, Reading, Mass., 1976. MR**0433364 (55:6340)****[27]**S. Smale, "The fundamental theorem of algebra and complexity theory,"*Bull. Amer. Math. Soc.*(N. S.), v. 4, 1981, pp. 1-35. MR**590817 (83i:65044)****[28]**S. Smale, "Algorithms for solving equations," presented at the International Congress of Mathematicians, Berkeley, 1986. MR**934223 (89d:65060)****[29]**G. W. Stewart, "Error and perturbation bounds for subspaces associated with certain eigenvalue problems,"*SIAM Rev.*, v. 15, 1973, p. 752. MR**0348988 (50:1482)****[30]**G. Stolzenberg,*Volumes, Limits, and Extensions of Analytic Varieties*, Lecture Notes in Math., vol. 19, Springer-Verlag, Berlin and New York, 1966. MR**0206337 (34:6156)****[31]**P. R. Thie, "The Lelong number of a point of a complex analytic set,"*Math. Ann.*, v. 172, 1967, pp. 269-312. MR**0214812 (35:5661)****[32]**B. L. Van Der Waerden,*Modern Algebra*, Vol. 1, Ungar, New York, 1953.**[33]**H. Weyl, "On the volume of tubes,"*Amer. J. Math.*, v. 61, 1939, pp. 461-472. MR**1507388****[34]**J. H. Wilkinson,*Rounding Errors in Algebraic Processes*, Prentice-Hall, Englewood Cliffs, N.J., 1963. MR**0161456 (28:4661)****[35]**J. H. Wilkinson,*The Algebraic Eigenvalue Problem*, Oxford University Press, Oxford, 1965. MR**0184422 (32:1894)****[36]**J. H. Wilkinson, "Note on matrices with a very ill-conditioned eigenproblem,"*Numer. Math*, v. 19, 1972, pp. 176-178. MR**0311092 (46:10188)****[37]**J. H. Wilkinson, "On neighboring matrices with quadratic elementary divisors,"*Numer. Math.*, v. 44, 1984, pp. 1-21. MR**745082 (85h:65096)****[38]**J. H. Wilkinson, "Sensitivity of eigenvalues,"*Utilitas Math.*, v. 25, 1984, pp. 5-76. MR**752846 (85i:65051)**

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