×

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.
Reviewer: O.Hadžić

MSC:
65J05 General theory of numerical analysis in abstract spaces
15A12 Conditioning of matrices
60D05 Geometric probability and stochastic geometry
53C65 Integral geometry
65Fxx Numerical linear algebra
65H05 Numerical computation of solutions to single equations
PDF BibTeX XML Cite
Full Text: DOI
References:
[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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.