Some complexity results for zero finding for univariate functions (Q2365840)

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\).