# The probability that a slightly perturbed numerical analysis problem is difficult

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

## Author(s)

## Related Research Unit(s)

## Detail(s)

Original language | English |
---|---|

Pages (from-to) | 1559-1583 |

Journal / Publication | Mathematics of Computation |

Volume | 77 |

Issue number | 263 |

Publication status | Published - Jul 2008 |

## Link(s)

## 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 ε-tubular neighborhoods around a real algebraic subvariety of a sphere, intersected with a spherical disk of radius σ. Besides ε and σ, this bound depends only on the dimension of the sphere and on the degree of the defining equations. ©2008 American Mathematical Society.

## Research Area(s)

- Condition numbers, Smooth analysis, Tubular neighborhoods of alge-braic surfaces

## Citation Format(s)

**The probability that a slightly perturbed numerical analysis problem is difficult.**/ Bürgisser, Peter; Cucker, Felipe; Lotz, Martin.

In: Mathematics of Computation, Vol. 77, No. 263, 07.2008, p. 1559-1583.

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review