Wilkinson’s Bus: Weak Condition Numbers, with an Application to Singular Polynomial Eigenproblems

Martin Lotz, Vanni Noferini*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

1 Citation (Scopus)
9 Downloads (Pure)

Abstract

We propose a new approach to the theory of conditioning for numerical analysis problems for which both classical and stochastic perturbation theories fail to predict the observed accuracy of computed solutions. To motivate our ideas, we present examples of problems that are discontinuous at a given input and even have infinite stochastic condition number, but where the solution is still computed to machine precision without relying on structured algorithms. Stimulated by the failure of classical and stochastic perturbation theory in capturing such phenomena, we define and analyse a weak worst-case and a weak stochastic condition number. This new theory is a more powerful predictor of the accuracy of computations than existing tools, especially when the worst-case and the expected sensitivity of a problem to perturbations of the input is not finite. We apply our analysis to the computation of simple eigenvalues of matrix polynomials, including the more difficult case of singular matrix polynomials. In addition, we show how the weak condition numbers can be estimated in practice.

Original languageEnglish
Pages (from-to)1439-1473
Number of pages35
JournalFOUNDATIONS OF COMPUTATIONAL MATHEMATICS
Volume20
Issue number6
Early online date2020
DOIs
Publication statusPublished - Dec 2020
MoE publication typeA1 Journal article-refereed

Keywords

  • Condition number
  • Polynomial eigenvalue problem
  • Singular matrix polynomial
  • Stochastic perturbation theory
  • Weak condition number

Fingerprint

Dive into the research topics of 'Wilkinson’s Bus: Weak Condition Numbers, with an Application to Singular Polynomial Eigenproblems'. Together they form a unique fingerprint.

Cite this