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.