The probability that a slightly perturbed
numerical analysis problem is difficult
Professor Felipe
Cucker
Department of
Mathematics
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 e-tubular
neighborhoods around a real algebraic subvariety of a
sphere, intersected with a disk of radius s. Besides e and s, this bound
depends only the dimension of the sphere and on the degree of the defining
equations.
|
Date: |
|
|
Time: |
|
|
Place: |
Room 517, Meng Wah Complex, HKU |
|
|
All
are welcome |
|