2019/06/25 by Ilse C. F. Ipsen, Hua Zhou, Ipsen, Ilse C. F. +1 · 5 citations
Computer Science · Decision Sciences · Mathematics · #60G42 #60G50 #65F30 #65G50 #Applied mathematics #Bounded function #Bounding overwatch #Computer science #FOS: Mathematics #Markov Chains and Monte Carlo Methods #Mathematical analysis #Mathematics #Numerical Analysis (math.NA) #Probabilistic analysis of algorithms #Probabilistic logic #Random variable #Risk and Portfolio Optimization #Statistics #Stochastic Gradient Optimization Techniques #Upper and lower bounds #cs.NA #math.NA #msc:60G42 #msc:60G50 #msc:65F30 #msc:65G50
paper · pdf · doi:10.48550/arxiv.1906.10465
published in arXiv (Cornell University) (Cornell University)
arxiv created 2019/06/25 · openalex publication_date 2019/06/25 · arxiv updated 2019/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
Probabilistic models are proposed for bounding the forward error in the numerically computed inner product (dot product, scalar product) between of two real n-vectors. We derive probabilistic perturbation bounds, as well as probabilistic roundoff error bounds for the sequential accumulation of the inner product. These bounds are non-asymptotic, explicit, and make minimal assumptions on perturbations and roundoffs. The perturbations are represented as independent, bounded, zero-mean random variables, and the probabilistic perturbation bound is based on Azuma's inequality. The roundoffs are also represented as bounded, zero-mean random variables. The first probabilistic bound assumes that the roundoffs are independent, while the second one does not. For the latter, we construct a Martingale that mirrors the sequential order of computations. Numerical experiments confirm that our bounds are more informative, often by several orders of magnitude, than traditional deterministic bounds -- even for small vector dimensions~n and very stringent success probabilities. In particular the probabilistic roundoff error bounds are functions of √(n) rather than~n, thus giving a quantitative confirmation of Wilkinson's intuition. The paper concludes with a critical assessment of the probabilistic approach.