Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The probability that a slightly perturbed numerical analysis problem is difficult

Authors: Peter Bürgisser, Felipe Cucker and Martin Lotz
Journal: Math. Comp. 77 (2008), 1559-1583
MSC (2000): Primary 65Y20; Secondary 65F35, 65H20.
Published electronically: January 30, 2008
MathSciNet review: 2398780
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We prove a general theorem providing smoothed analysis estimates for conic condition numbers of problems of numerical analysis. Our probability estimates depend only on geometric invariants of the corresponding sets of ill-posed inputs. Several applications to linear and polynomial equation solving show that the estimates obtained in this way are easy to derive and quite accurate. The main theorem is based on a volume estimate of $\varepsilon$-tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a spherical disk of radius $\sigma$. Besides $\varepsilon$ and $\sigma$, this bound depends only on the dimension of the sphere and on the degree of the defining equations.

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

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 65Y20, 65F35, 65H20.

Retrieve articles in all journals with MSC (2000): 65Y20, 65F35, 65H20.

Additional Information

Peter Bürgisser
Affiliation: Department of Mathematics, University of Paderborn, Germany
MR Author ID: 316251

Felipe Cucker
Affiliation: Department of Mathematics, City University of Hong Kong, Kowloon Tong, Hong Kong

Martin Lotz
Affiliation: Department of Mathematics, City University of Hong Kong, Kowloon Tong, Hong Kong

Keywords: Condition numbers, smooth analysis, tubular neighborhoods of algebraic surfaces.
Received by editor(s): September 28, 2006
Received by editor(s) in revised form: April 23, 2007
Published electronically: January 30, 2008
Additional Notes: Part of these results were announced in C.R. Acad. Sci. Paris, Ser. I 343 (2006) 145–150.
The first author was partially supported by DFG grant BU 1371.
The second and third authors were partially supported by CityU SRG grant 7001860.
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.