Some complexity results for zero finding for univariate functions

DOI10.1006/JCOM.1993.1003MaRDI QIDQ2365840zbMATH OpenOpenAlexFDO

Authors Klaus Ritter, Erich Novak

Publication date 29 June 1993

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

Full work available at URL https://doi.org/10.1006/jcom.1993.1003

zbMATH Keywords

average casebest possible orders of convergencecomplex polynomialserror boundsinformation based complexityreal number modelworst casezero finding

Mathematics Subject Classification ID

Zeros of polynomials, rational functions, and other analytic functions of one complex variable (e.g., zeros of functions with bounded Dirichlet integral) (30C15) Numerical computation of solutions to single equations (65H05) Complexity and performance of numerical algorithms (65Y20)

Review text

The paper gives a survey of information based complexity results for zero finding. One section presents worst case and probabilistic results for complex polynomials. Thereafter the emphasis is on zero finding for univariate, at least continuous functions with a change of sign on some interval. Asymptotic results on best possible orders of convergence are given. Then error bounds are discussed that hold for all functions in the given class \(F\) after a fixed number of steps in the worst case setting. Finally the average case setting is considered using an expected error and cost with respect to a probability measure on \(F\). In this setting methods are also studied which use a varying number of knots depending on the particular function in \(F\).

Recommendations

• Average errors for zero finding: Lower bounds for smooth or monotone functions
• Optimal solution of nonlinear equations
• Average-case results for zero finding
• Average errors for zero finding: Lower bounds
• scientific article; zbMATH DE number 953052

Cited in

(9)

• Average errors for zero finding: Lower bounds for smooth or monotone functions
• Topological complexity of zero finding with algebraic operations
• Randomly generated distributions
• Stochastic approximation of Banach-valued random variables with smooth distributions
• A modified Brent's method for finding zeros of functions
• scientific article; zbMATH DE number 4037051 (Why is no real title available?)
• Average-Case Optimality of a Hybrid Secant-Bisection Method
• Optimal approximation of stochastic differential equations by adaptive step-size control
• Average-case results for zero finding

This page was built for publication: Some complexity results for zero finding for univariate functions

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