Geometric Methods in the Probabilistic Analysis of Condition Numbers

点击翻译按钮获取中文摘要

The running time of many iterative algorithms in numerical analysis and optimisation is dominated by the condition number of the input. The study of the probability distribution of condition numbers for random inputs thus leads to a probabilistic analysis of the running time of such algorithms. In many cases, the condition number of an input is proportional to the inverse distance of the given input to a set of ill-posed inputs. In these situations, results about the probability distribution of condition numbers for random inputs can be obtained from studying the geometry of the set of ill-posed inputs. The goal of this project is to explore the scope and limitations of this geometric approach, with a particular emphasis on developing methods for dealing with different input distributions, with structured condition numbers, and with condition numbers arising in the context of optimisation theory. Ultimately, the proposed research project is expected to contribute to a better understanding of the performance of numerical and optimisation algorithms as observed in practice.