Average-case results for zero finding

DOI10.1016/0885-064X(89)90022-8MaRDI QIDQ582817zbMATH OpenFDO

Authors Erich Novak

Publication date 1989

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0885-064X(89)90022-8

zbMATH Keywords

average-case resultsbisection methodBrownian bridgeprobability measures

Mathematics Subject Classification ID

Numerical computation of solutions to single equations (65H05)

Review text

Let (*) f:[0,1]\(\to {\mathbb{R}}\) be a continuous function, \(f(0)<0\), \(f(1)>0\). As further information on f let \(n\in {\mathbb{N}}\) evaluations of f(x) be available which are computed sequentially. The author surveys recent average-case results for the approximate solution of the nonlinear equation \(f(x)=0\) and proves a new result of this type. He shows that the bisection method is not optimal (as in the worst case) for a number of classes of functions (*). As a central means of proof different suitable probability measures are used. No examples.

Recommendations

• scientific article; zbMATH DE number 4070191
• Average errors for zero finding: Lower bounds
• Average-Case Optimality of a Hybrid Secant-Bisection Method
• scientific article; zbMATH DE number 89008
• Some complexity results for zero finding for univariate functions

Cites work

• Bisection is not optimal on the average
• Bisection is optimal
• Deterministic and stochastic error bounds in numerical analysis
• scientific article; zbMATH DE number 3673243 (Why is no real title available?)
• scientific article; zbMATH DE number 3740677 (Why is no real title available?)
• scientific article; zbMATH DE number 44104 (Why is no real title available?)
• scientific article; zbMATH DE number 3476451 (Why is no real title available?)
• scientific article; zbMATH DE number 3537171 (Why is no real title available?)
• On the worst-case arithmetic complexity of approximating zeros of polynomials
• Optimal search for the roots of a function satisfying a lipschitz condition
• Optimal solution of nonlinear equations
• Random homeomorphisms

Cited in

(9)

• Average errors for zero finding: Lower bounds
• Constructing prior distributions with trees of exchangeable processes
• Average errors for zero finding: Lower bounds for smooth or monotone functions
• Randomly generated distributions
• Some complexity results for zero finding for univariate functions
• scientific article; zbMATH DE number 4070191 (Why is no real title available?)
• scientific article; zbMATH DE number 89008 (Why is no real title available?)
• scientific article; zbMATH DE number 1206072 (Why is no real title available?)
• Determining zeroes of increasing Lipschitz functions

This page was built for publication: Average-case results for zero finding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582817)