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


References [Enhancements On Off] (What's this?)

  • [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)

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

DOI: https://doi.org/10.1090/S0025-5718-1988-0929546-7
Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society