The probability that a slightly perturbed numerical analysis problem is difficult

DOI10.1090/S0025-5718-08-02060-7MaRDI QIDQ3577011zbMATH OpenOpenAlexWikidataFDO

Authors Peter Bürgisser, Felipe Cucker, Martin Lotz

Publication date 3 August 2010

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0610270

condition numbers polynomial equation smooth analysis tubular neighborhoods of algebraic surfaces

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18) Global methods, including homotopy approaches to the numerical solution of nonlinear equations (65H20) Complexity and performance of numerical algorithms (65Y20)

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 epsilon-tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a disk of radius sigma. Besides epsilon and sigma, this bound depends only the dimension of the sphere and on the degree of the defining equations.

Recommendations

Cites work

Cited in

(21)

This page was built for publication: The probability that a slightly perturbed numerical analysis problem is difficult

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3577011)