Approximating fixed points of weakly contracting mappings (Q1974567)

The authors continue their previous works [cf. for example \textit{K. Sikorski, C. W. Tsay} and \textit{H. Wozniakowski}, J. Complexity 9, No. 1, 181-200 (1993; Zbl 0772.41033)] on the problem of approximating fixed points of contractive functions with contractive factor \(q\) close to 1. They present an inscribed ellipsoid (IE) algorithm that enjoys an \(O(n(\ln 1/\varepsilon)+ \ln (1/(1-q)))\) bound on the number of function evaluations to compute \(\varepsilon\)-approximations. Their analysis implies that (1) the dimensional deflation procedure in the circumscribed (CE) algorithm is not necessary and that the resulting ``plain'' CE algorithm enjoys an \(O(n^{2} \ln (1/\varepsilon)+ \ln (1/(1-q)))\) upper bound on the number of function evaluations; (2) the IE algorithm solves the problem in the residual sense, i.e. computes \(x\) such that \(\|f(x)-x\|\leq\delta,\) with \(O(n\ln(1/\delta))\) function evaluations for every \(q\leq 1\).