Videos

The Probability that a Slight Perturbation of a Numerical Analysis Problem is Difficult

Presenter
April 20, 2007
Keywords:
  • Iterative methods for linear systems
MSC:
  • 65F10
Abstract
The running time of many iterative numerical algorithms is dominated by the condition number of the input, a quantity measuring the sensitivity of the solution with regard to small perturbations of the input. Examples are iterative methods of linear algebra, interior-point methods of linear and convex optimization, as well as homotopy methods for solving systems of polynomial equations. Spielman and Teng introduced in 2001 the seminal concept of smoothed analysis, which arguably blends the best of both worst-case and average-case analysis of algorithms. This led to a much better understanding of the success of the simplex method in practice. We present 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 disk of radius σ. Besides ε and σ, this bound depends only the dimension of the sphere and on the degree of the defining equations. This is joint work with Felipe Cucker and Martin Lotz.