The probability that a numerical analysis problem is difficult

Demmel, James W.

doi:10.1090/S0025-5718-1988-0929546-7

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
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
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, Matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101–114 (Russian). 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] 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 (88i:15014), http://dx.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 (41 #1976)
[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 (85h:65063)
[8] Alfred Gray, An estimate for the volume of a tube about a complex hypersurface, Tensor (N.S.) 39 (1982), 303–305. MR 836947 (87c:53126)
[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 (83c:53064), http://dx.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 (80k:53101)
[11] R. W. Hamming, On the distribution of numbers, Bell System Tech. J. 49 (1970), 1609–1625. MR 0267809 (42 #2711)
[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, http://dx.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 (34 #3324)
[17] Keith Kendig, Elementary algebraic geometry, Springer-Verlag, New York, 1977. Graduate Texts in Mathematics, No. 44. MR 0447222 (56 #5537)
[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 (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 & Breach, Paris, 1968 (French). 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 a system of complex polynomials, Math. Oper. Res. 12 (1987), no. 1, 121–148. MR 882846 (88j:65112), http://dx.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 (35 #2454)
[25] Axel Ruhe, Properties of a matrix with a very ill-conditioned eigenproblem, Numer. Math. 15 (1970), 57–60. MR 0266416 (42 #1322)
[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 (55 #6340)
[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 (83i:65044), http://dx.doi.org/10.1090/S0273-0979-1981-14858-8
[28] Steve Smale, Algorithms for solving equations, (Berkeley, Calif., 1986) Amer. Math. Soc., Providence, RI, 1987, pp. 172–195. MR 934223 (89d:65060)
[29] G. W. Stewart, Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev. 15 (1973), 727–764. MR 0348988 (50 #1482)
[30] Gabriel Stolzenberg, Volumes, limits, and extensions of analytic varieties, Lecture Notes in Mathematics, No. 19, Springer-Verlag, Berlin, 1966. MR 0206337 (34 #6156)
[31] Paul R. Thie, The Lelong number of a point of a complex analytic set, Math. Ann. 172 (1967), 269–312. MR 0214812 (35 #5661)
[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, http://dx.doi.org/10.2307/2371513
[34] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall Inc., Englewood Cliffs, N.J., 1963. MR 0161456 (28 #4661)
[35] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. MR 0184422 (32 #1894)
[36] J. H. Wilkinson, Note on matrices with a very ill-conditioned eigenproblem, Numer. Math. 19 (1972), 176–178. MR 0311092 (46 #10188)
[37] J. H. Wilkinson, On neighbouring matrices with quadratic elementary divisors, Numer. Math. 44 (1984), no. 1, 1–21. MR 745082 (85h:65096), http://dx.doi.org/10.1007/BF01389751
[38] J. H. Wilkinson, Sensitivity of eigenvalues, Utilitas Math. 25 (1984), 5–76. MR 752846 (85i:65051)

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|