# zbMATH — the first resource for mathematics

The probability that a numerical analysis problem is difficult. (English) Zbl 0657.65066
Author’s summary: 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 the 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 is its condition number with the respect to inversion. We show that the sets of ill-posed problems for matrix inversion, eigenproblems, and polynomials 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$$^{\prime}$$d, On matrices depending on parameters, Uspehi Mat. Nauk 26 (1971), no. 2(158), 101 – 114 (Russian). [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. · Zbl 0597.65036 · doi:10.1007/BF01400115 · doi.org [5] C. Eckart & G. Young, ”The approximation of one matrix by another of lower rank”, Psychometrika, v. 1, 1936, pp. 211-218. · JFM 62.1075.02 [6] Herbert Federer, Geometric measure theory, Die Grundlehren der mathematischen Wissenschaften, Band 153, Springer-Verlag New York Inc., New York, 1969. · Zbl 0176.00801 [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. · Zbl 0559.65011 [8] Alfred Gray, An estimate for the volume of a tube about a complex hypersurface, Tensor (N.S.) 39 (1982), 303 – 305. · Zbl 0513.53051 [9] Alfred Gray, Comparison theorems for the volumes of tubes as generalizations of the Weyl tube formula, Topology 21 (1982), no. 2, 201 – 228. · Zbl 0487.53035 · doi:10.1016/0040-9383(82)90005-2 · doi.org [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. · Zbl 0409.53048 [11] R. W. Hamming, On the distribution of numbers, Bell System Tech. J. 49 (1970), 1609 – 1625. · Zbl 0211.46701 · doi:10.1002/j.1538-7305.1970.tb04281.x · doi.org [12] Harold Hotelling, Tubes and Spheres in n-Spaces, and a Class of Statistical Problems, Amer. J. Math. 61 (1939), no. 2, 440 – 460. · JFM 65.0795.02 · doi:10.2307/2371512 · doi.org [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.) · Zbl 0236.65025 [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. · Zbl 0148.12601 [17] Keith Kendig, Elementary algebraic geometry, Springer-Verlag, New York-Berlin, 1977. Graduate Texts in Mathematics, No. 44. · Zbl 0364.14001 [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. · Zbl 0477.65002 [19] E. Kostlan, Statistical Complexity of Numerical Linear Algebra, Dissertation, Math. Dept., University of California, Berkeley, 1985. · Zbl 0645.65019 [20] P. Lelong, Fonctions plurisousharmoniques et formes différentielles positives, Gordon & Breach, Paris-London-New York (Distributed by Dunod éditeur, Paris), 1968 (French). · Zbl 0192.20103 [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. · Zbl 0608.46035 [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. · Zbl 0618.65038 · doi:10.1287/moor.12.1.121 · doi.org [24] John R. Rice, A theory of condition, SIAM J. Numer. Anal. 3 (1966), 287 – 310. · Zbl 0143.37101 · doi:10.1137/0703023 · doi.org [25] Axel Ruhe, Properties of a matrix with a very ill-conditioned eigenproblem, Numer. Math. 15 (1970), 57 – 60. · Zbl 0184.37704 · doi:10.1007/BF02165660 · doi.org [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. · Zbl 0342.53049 [27] Steve Smale, The fundamental theorem of algebra and complexity theory, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 1 – 36. · Zbl 0456.12012 [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. [29] G. W. Stewart, Error and perturbation bounds for subspaces associated with certain eigenvalue problems, SIAM Rev. 15 (1973), 727 – 764. · Zbl 0297.65030 · doi:10.1137/1015095 · doi.org [30] Gabriel Stolzenberg, Volumes, limits, and extensions of analytic varieties, Lecture Notes in Mathematics, No. 19, Springer-Verlag, Berlin-New York, 1966. · Zbl 0142.33801 [31] Paul R. Thie, The Lelong number of a point of a complex analytic set, Math. Ann. 172 (1967), 269 – 312. · Zbl 0158.32804 · doi:10.1007/BF01351593 · doi.org [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. · Zbl 0021.35503 · doi:10.2307/2371513 · doi.org [34] J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. · Zbl 1041.65502 [35] J. H. Wilkinson, The algebraic eigenvalue problem, Clarendon Press, Oxford, 1965. · Zbl 0258.65037 [36] J. H. Wilkinson, Note on matrices with a very ill-conditioned eigenproblem, Numer. Math. 19 (1972), 176 – 178. · Zbl 0252.65027 · doi:10.1007/BF01402528 · doi.org [37] J. H. Wilkinson, On neighbouring matrices with quadratic elementary divisors, Numer. Math. 44 (1984), no. 1, 1 – 21. · Zbl 0545.65025 · doi:10.1007/BF01389751 · doi.org [38] J. H. Wilkinson, Sensitivity of eigenvalues, Utilitas Math. 25 (1984), 5 – 76. · Zbl 0551.65018