Computational Complexity of One-Point and Multipoint Iteration

摘要

Let phi be an iteration for approximating the solution of a problem f. A new efficiency measure e(phi,f) is defined. For a given problem f, the authors define the optimal efficiency E(f) and establish lower and upper bounds for E(f) with respect to different families of iterations. An upper bound on E(f) is conjectured for any iteration without memory. (Author)