Optimal solution of nonlinear equations (Q1086985)

The paper surveys some recent worst-case complexity results for the solution of a nonlinear equation \(f(x)=0\) and for the computation of the topological degree of f. Here f is assumed to be smooth on a real interval, the unit simplex, or the unit cube of \(R^ m\), and the information on f consists of n values of arbitrary functionals which are computed sequentially. As measure of the error of an approximation x(f) of a zero \(\alpha\) (f) of the equation the root criterion \(\| x(f)- \alpha (f)\| \leq \epsilon\) and the residual criterion \(\| f(x(f))\| \leq \epsilon\) are admitted. The paper ends with some comments about the worst case and average case analysis of iterative algorithms. A bibliography of 82 items is included.