Quantitative results on Fejér monotone sequences

arXiv:1412.5563v2 [math.LO] 23 Aug 2015 Quantitative results on Fej´er monotone sequences Ulrich Kohlenbach1, Laurent¸iu Leu¸stean2,3, Adriana Nicolae4,5 1Department of Mathematics, Technische Universit¨at Darmstadt, Schlossgartenstraße 7, 64289 Darmstadt, Germany 2Faculty of Mathematics and Computer Science, University of Bucharest, Academiei 14, P.O. Box 010014, Bucharest, Romania 3Simion Stoilow Institute of Mathematics of the Romanian Academy, P. O. Box 1-764, 014700 Bucharest, Romania 4Department of Mathematics, Babe¸s-Bolyai University, Kog˘alniceanu 1, 400084 Cluj-Napoca, Romania 5Simion Stoilow Institute of Mathematics of the Romanian Academy, Research group of the project PD-3-0152, P. O. Box 1-764, 014700 Bucharest, Romania E-mails: kohlenbac[email protected], Laurent[email protected], [email protected] Abstract We provide in a unified way quantitative forms of strong convergence results for numerous iterative procedures which satisfy a general type of Fej´er monotonicity where the convergence uses the compactness of the underlying set. These quantitative versions are in the form of explicit rates of so-called metastability in the sense of T. Tao. Our approach covers examples ranging from the proximal point algorithm for maximal monotone operators to various fixed point iterations (xn) for firmly nonexpansive, asymptotically nonexpansive, strictly pseudo-contractive and other types of mappings. Many of the results hold in a general metric setting with some convexity structure added (so-called W-hyperbolic spaces). Sometimes uniform convexity is assumed still covering the important class of CAT(0)-spaces due to Gromov. Keywords: Fej´er monotone sequences, quantitative convergence, metastability, proximal point algorithm, firmly nonexpansive mappings, strictly pseudo-contractive mappings, proof mining. 1 Introduction This paper provides in a unified way quantitative forms of strong convergence results for numerous iterative procedures which satisfy a general type of Fej´er monotonicity where the convergence uses the compactness of the underlying set. Fej´er monotonicity is a key notion employed in the study of many problems in convex optimization and programming, fixed point theory and the study of 1 (ill-posed) inverse problems (see e.g. [53,10]). These quantitative forms have been obtained using the logic-based proof mining approach (as developed e.g. in [26]) but the results are presented here in a way which avoids any explicit reference to notions or tools from logic. Our approach covers examples ranging from the proximal point algorithm for maximal monotone operators to various fixed point iterations (xn) for firmly nonexpansive, asymptotically nonexpansive, strictly pseudo-contractive and other types of mappings. Many of the results hold in a general metric setting with some convexity structure added (so-called W-hyperbolic spaces in the sense of [25]). Sometimes uniform convexity is assumed still covering Gromov’s CAT(0)-spaces. For reasons from computability theory, effective rates of convergence for (xn) in Xare usually ruled out even when the space Xin question and the map Tused in the iteration are effective: usually (xn) will converge to a fixed point of Tbut in general Twill not possess a computable fixed point and even when it does (e.g. when Xis Rnand the fixed point set is convex) the usual iterations will not converge to a computable point and hence will not converge with an effective rate of convergence (see [45] for details on all this). The Cauchy property of (xn) can, however, be reformulated in the equivalent form (∗)∀k∈N∀g:N→N∃N∈N∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1 and for this form, highly uniform computable bounds ∃N≤Φ(k, g) on ∃Ncan be obtained. (∗) is known in mathematical logic since 1930 as Herbrand normal form and bounds Φ have been studied in the so-called Kreisel no-counterexample interpretation (which in turn is a special case of the G¨odel functional interpretation) since the 50’s (see [26]). More recently, (∗) has been made popular under the name of ‘metastability’ by Terence Tao, who used the existence of uniform bounds on Nin the context of ergodic theory ([51,52]. Moreover, Walsh [54] used again metastability to show the L2-convergence of multiple polynomial ergodic averages arising from nilpotent groups of measurepreserving transformations. In nonlinear analysis, rates of metastability Φ for strong convergence results of nonlinear iterations have been first considered and extracted in [30,24] (and in many other cases since then). The point of departure of our investigation is [24] which uses Fej´er monotonicity and where some of the arguments of the present paper have first been used in a special context. Let F⊆Xbe a subset of Xand recall that (xn) is Fej´er monotone w.r.t. Fif (+) d(xn+1, p)≤d(xn, p),for all n∈Nand p∈F . We think of Fas being the intersection F=Tk∈NAFkof approximations AFk+1 ⊆AFk⊆Xto F, one prime example being F:= Fix(T) and AFk:= {p∈X|d(p, T p)≤1/(k+ 1)},where Fix(T) denotes the fixed point set of some selfmap T:X→X. The key notion in this paper is that of a modulus of uniform Fej´er monotonicity i.e. a bound ∃k≤χ(r, n, m) for the following uniform strengthening of ‘Fej´er monotone’ ∀r, n, m ∈N∃k∈N∀p∈Xp∈AFk→ ∀l≤md(xn+l, p)< d(xn, p) + 1 r+ 1. If Xis compact and Fsatisfies an appropriate closedness condition w.r.t. the sets AFk, then ‘Fej´er monotone’ and ‘uniform Fej´er monotone’ are equivalent. However, moduli χfor uniform Fej´er 2 monotonicity can be extracted (based on results from logic) also in the absence of compactness, provided that the proof of the Fej´er monotonicity is formalizable in a suitable context, and we provide such moduli χin all our applications. If Xis compact, Fsatisfies some explicit closedness condition w.r.t. AFk(Definition 3.3) and (xn) (in addition to being Fej´er monotone) possesses approximate F-points, i.e. (∗∗)∀k∈N∃n∈N(xn∈AFk), then (xn) converges to a point in F(see Proposition 4.3 and the remark thereafter). The main general quantitative theorem in our paper (Theorem 5.1) transforms (given k, g) any modulus of total boundedness γ(a quantitative way to express the total boundedness of X, see Section 2), any bound Φ on (∗∗) and any modulus χof uniform Fej´er monotonicity into a rate Ψ(k, g, Φ, χ, γ) of metastability (∗) of (xn).If, moreover, Fis uniformly closed w.r.t. AFk(Definition 3.4), which e.g. is the case when Fand AFkare, respectively, the fixed point and the 1/(k+ 1)- approximate fixed point set of a uniformly continuous mapping T, then one can also arrange that all the points in the interval of metastability [N, N +g(N)] belong to AFk(Theorem 5.3). Ψ is the P-times iterate of a slightly massaged (with χ, Φ) version of g, where Ponly depends on γ, k (but not on g). In particular, this yields that a rate of convergence for (xn) (while not being computable) is effectively learnable with at most P-many mind changes and a learning strategy which - essentially - is Φ ◦χ(see [32] for more on this). That a primitive recursive iteration of gis unavoidable follows from the fact that even for most simple cases of Fej´er monotone fixed point iterations (xn) in [0,1] the Cauchy property of (xn) implies the Cauchy property of monotone sequences in [0,1] (see [45]) which is equivalent to Σ0 1-induction ([23](Corollary 5.3)). See also the example at the end of section 5. A variant of Theorem 5.3 holds even without any closedness assumption, if (xn) not only possesses AFk-points for every kbut is asymptotic regular ∀k∈N∃n∈N∀m≥n(xm∈AFk) with a rate of metastability Φ+for this property instead of the approximate F-point bound Φ (Theorem 5.8). In all these results we actually permit a more general form of Fej´er-monotonicity, where instead of (+) one has (++) H(d(xn+m, p)) ≤G(d(xn, p)),for all n, m ∈Nand p∈F . and G, H :R+→R+are subject to very general conditions (this e.g. is used in the application to asymptotically nonexpansive mappings). As is typical for such quantitative ‘finitizations’ of noneffective convergence results, it is easy to incorporate a summable sequence (εn) of error terms in all the aforementioned results which covers the important concept of ‘quasi-Fej´er-monotonicity’ due to [12] (see Section 6). As a consequence of this, one can also incorporate such error terms in the iterations we are considering in this paper. However, for the sake of better readability we will not carry this out in this paper (but see [29] for an application of this to convex feasibility problems in CAT(κ)-spaces). The results mentioned so far hold for arbitrary sets F=TkAFkprovided that we have the various moduli as indicated. In the case where AFkcan be written as a purely universal formula and we have - sandwiched in between AFk+1 ⊆˜ AF k⊆AFkthe sets ˜ AFkwhich are given by a purely 3 existential formula (which is the case for AFk={p∈X|d(p, T p)≤1/(k+1)}with ˜ AFk={p∈X| d(p, T p)<1/(k+1)}), then the logical metatheorems from [25,15,26]guarantee the extractability of explicit and highly uniform moduli χfrom proofs of (generalized) Fej´er monotonicity, as well as approximate fixed point bounds or metastability rates for asymptotic regularity from proofs of the corresponding properties if these proofs can be carried out in suitable formal systems as in all our applications. The paper is organized as follows: in Section 2we discuss the background from mathematical logic, i.e. so-called logical metatheorems (due to the first author in [25], see also [15,26]) which provide tools for the extraction of highly uniform bounds from prima facie noneffective proofs of ∀∃-theorems (which covers the case of metastability statements). Since our present paper uses the context of totally bounded metric spaces we discuss this case in particular detail. Applying proof mining to a concrete proof results again in an ordinary proof in analysis and so one can read the proofs in this paper without any knowledge of logic which, however, was used by the authors to find these proofs. In Sections 3and 4we develop the basic definitions and facts about the sets F, AFk,the notions of explicit and uniform closedness as well as (uniform) generalized (G, H)-Fej´er monotone sequences. In Section 5we establish our main general quantitative theorems which then will be specialized in our various applications. Section 6generalizes these results to the case of (uniform) quasi-Fej´er monotone sequences. In Section 7we interpret our results in the case where Fis the fixed point set of a selfmap T(mostly of some convex subset of X) and provide numerous applications as mentioned above: in each of these cases we provide appropriate moduli of uniform (generalized) Fej´er monotonicity χand approximate fixed bounds bounds Φ (usually even rates of asymptotic regularity or metastable versions thereof) so that our general quantitative theorems can be applied resulting in explicit rates of metastability for (xn).In the case of CAT(0)-spaces (resp. Hilbert spaces), these Φ’s become quadratic in the error 1/(k+ 1).In Section 8we do the same for the case where Fis the set of zeros of a maximal monotone operator and provide the corresponding moduli for the proximal point algorithm. The results in this paper are based on compactness arguments. Without compactness one in general has only weak convergence for Fej´er monotone sequences but in important cases weakly convergent iterations can be modified to yield strong convergence even in the absence of compactness (see e.g. [3]). This phenomenon is known from fixed point theory where Halpern-type variants of the weakly convergent Mann iteration yield strong convergence ([7,20,55]). Even when only weak convergence holds one can apply the logical machinery to extract rates of metastability for the weak Cauchy property (see e.g. [28] where this is done in the case of Baillon’s nonlinear ergodic theorem). However, the bounds will be extremely complex. If, however, weak convergence is used only as an intermediate step towards strong convergence, one can often avoid the passage through weak convergence altogether and obtain much simpler rates of metastability (see e.g. [27] where this has been carried out in particular for Browder’s classical strong convergence theorem of the resolvent of a nonexpansive operator in Hilbert spaces, as well as [34]). We believe that it is an interesting future research project to adapt these techniques to the context of Fej´er monotone sequences. Notations: Nand N∗denote the set of natural numbers including 0 resp. without 0 and R+are the nonnegative reals. 4 2 Quantitative forms of compactness Let (X, d) be a metric space. We denote with B(x, r) (resp. B(x, r)) the open (resp. closed) ball with center x∈Xand radius r > 0. Let us recall that a nonempty subset A⊆Xis totally bounded if for every ε > 0 there exists an ε-net of A, i.e. there are n∈Nand a0, a1...,an∈Xsuch that A⊆Sn i=0 B(ai, ε). This is equivalent with the existence of a 1/(k+ 1)-net for every k∈N. Definition 2.1. Let ∅ 6=A⊆X. We call α:N→NaI-modulus of total boundedness for Aif for every k∈Nthere exist elements a0, a1,...,aα(k)∈Xsuch that ∀x∈A∃0≤i≤α(k)d(x, ai)≤1 k+ 1.(1) Thus, Ais totally bounded iff Ahas a I-modulus of total boundedness. In this case, we also say that Ais totally bounded with I-modulus α. One can easily see that any totally bounded set is bounded: given a I-modulus αand a0,...,aα(0) ∈Xsuch that (1) is satisfied for k= 0, b:= 2 + max{d(ai, aj)|0≤i, j ≤α(0)}is an upper bound on the diameter of A. We now give an alternative characterization of total boundedness used in the context of proof mining first in [14]: Definition 2.2. Let ∅ 6=A⊆X. We call γ:N→NaII-modulus of total boundedness for Aif for any k∈Nand for any sequence (xn)in A ∃0≤i < j ≤γ(k)d(xi, xj)≤1 k+ 1.(2) Remark 2.3. The logarithm of the smallest possible value for a I-modulus of total boundedness is also called the 1/(k+ 1)-entropy of Awhile the logarithm of the optimal II-modulus is called the 1/(k+ 1)-capacity of A(see e.g. [40]). Proposition 2.4. Let ∅ 6=A⊆X. (i) If αis a I-modulus of total boundedness for A, then γ(k) := α(2k+ 1) + 1 is a II-modulus of total boundedness for A. (ii) If γis a II-modulus of total boundedness for A, then α(k) := γ(k)−1is a I-modulus of total boundedness (so, in particular, Ais totally bounded). Proof. (i) Let a0,...,aα(2k+1) ∈Xbe such that (1) is satisfied, hence for all x∈Athere exists 0 ≤i≤α(2k+ 1) such that d(x, ai)≤1 2k+ 2. Applying the pigeonhole principle to x0, x1,...,xα(2k+1)+1, we get 0 ≤i < j ≤α(2k+ 1) + 1, such that xiand xjare in a ball of radius 1 2k+ 2 around the same alwith 0 ≤l≤α(2k+ 1). It follows that d(xi, xj)≤1 k+ 1, hence (2) holds. (ii) First, let us remark that γ(k)≥1 for all k, hence αis well-defined. Assume by contradiction that α(k) := γ(k)−1 is not a I-modulus of total boundedness, i.e. there exists k∈Nsuch that (∗)∀a0,...,aγ(k)−1∈X∃x∈A∀0≤i≤γ(k)−1d(x, ai)>1 k+ 1. 5 By induction on l≤γ(k) we show that (∗∗)∃β0,...,βl∈A∀0≤i < j ≤ld(βi, βj)>1 k+ 1, which, for l:= γ(k), contradicts the assumption that γis a II-modulus of total boundedness. l= 0: Choose β0∈Aarbitrary. l7→ l+ 1 ≤γ(k) : Let β0,...,βlbe as in (∗∗).By (∗) applied to ai:= (βiif i≤l βlif l < i ≤γ(k)−1 we get x∈Asuch that d(x, βi)>1 k+ 1 for all i≤l. Then β0,...,βl, βl+1 := xsatisfies (∗∗). Note that the existence of a 1/(k+ 1)-net in the proof of Proposition 2.4.(ii) is noneffective. In particular, there is no effective way to compute a bound on Afrom a II-modulus of total boundedness. This seemingly disadvantage actually will allow us to extract bounds of greater uniformity from proofs of statements which do not explicitly refer to such a bound (see below). 2.1 General logical metatheorems for totally bounded metric spaces In [25], the first author introduced so-called logical metatheorems for bounded metric structures (as well as for normed spaces and other classes of spaces).1Here systems Tωof arithmetic and analysis in the language of functionals of all finite types are extended by an abstract metric space Xwhose metric is supposed to be bounded by b∈Nresulting in a system Tω[X, d]. Consider now aTω[X, d]-proof of a theorem of the following form, where Pis some concrete complete separable metric space and Ka concrete compact metric space:2 (+) (∀u∈P∀v∈K∀x∈X∀y∈XN∀T:X→X (A∀(u, v, x, y, T )→ ∃n∈NB∃(u, v, x, y, T )), where A∀, B∃are purely universal resp. purely existential sentences (with some restrictions on the types of the quantified variables). Then from the proof one can extract (using a method from proof theory called monotone functional interpretation, due to the first author, see [26] for details on all this) a computable uniform bound ‘∃n≤Φ(fu, b)’ on ‘∃n∈N’ which only depends on some representation fuof uin Pand a bound bof the metric. In particular, Φ does not depend on v, x, y, T nor on the space X(except for the bound b). In most of our applications Pwill be Nor NN(with the discrete and the Baire metric, respectively) in which case u=fu.In the cases Ror C[0,1], however, fuis some concrete fast Cauchy sequence (say of Cauchy rate 2−n) of rationals representing u∈Rresp. a pair (f, ω) with f∈C[0,1] and some modulus of uniform continuity ω for fin the case of C[0,1]. fucan always be encoded into an element of NN. Φ has some restricted subrecursive complexity which reflects the strength of the mathematical axioms 1In this discussion we focus on the case of metric spaces. 2For simplicity, we only consider here some special case. For results in full generality see [25,15,26]. 6 from Tωused in the proof. In most applications, Φ is at most of so-called primitive recursive complexity. As discussed in [15] and [26, Application 18.16, p. 464], the formalization of the total boundedness of Xvia the existence of a I-modulus of total boundedness αcan be incorporated in this setting as follows: in order to simplify the logical structure of the axiom to be added it is convenient to combine all the individual ε-nets a0,...,aα(ε)into one single sequence (an) of elements in Xand to replace the quantification over ε > 0 by quantification over Nvia ε:= 1/(n+ 1) : The theory Tω[X, d, T OT I] of totally bounded metric spaces is obtained by adding to Tω[X, d] (i) two constants αN→Nand aN→Xdenoting a function N→Nand a sequence N→X, respectively, as well as (ii) one universal axiom:3 (T OT I)∀kN∀xX∃N≤Nα(k)dX(x, aN)≤R 1 k+ 1. It is obvious that (T OT I) implies that αis a I-modulus of total boundedness of Xas defined before. Conversely, suppose αis such a modulus. Then α′(n) := Pn i=0(α(i) + 1) satisfies (T OT I) for the sequence (an) obtained as the concatenation of the 1/(k+ 1)-nets ak 0,...,ak α(k),k= 0,1,.... Since (T OT I) is purely universal, its addition does not cause any problems and the only change caused by switching from Tω[X, d] to Tω[X, d, T OT I] is that the extracted bound Φ will additionally depend on α(see [26] for details). In [15], the results from [25] are extended to the case of unbounded metric spaces. Then the bound Φ depends, instead of b, on majorizing data x∗&p Xx, y∗&p N→Xy, T ∗&p X→XTfor x, y, T relative to some reference point p∈X(which usually will be identified with x). More precisely, the pmajorizability relation &pis defined (for the cases at hand which are special cases of a general inductive definition for all function types over N, X interpreted here over the full set-theoretic type structure, see [26]) as follows: n∗&p Nn:= n∗, n ∈N∧n∗≥n, α∗&p N→Nα:= α∗, α ∈NN∧∀n∗, n(n∗≥n→α∗(n∗)≥α∗(n), α(n)), x∗&p Xx:= x∗∈N, x ∈X∧x∗≥d(p, x), y∗&p N→Xy:= y∗∈NN, y ∈XN∧∀n∗, n ∈N(n∗≥n→y∗(n∗)≥d(p, y(n))), T∗&p X→XT:= T∗∈NN, T ∈XX∧ ∀n∈N∀x∈X(n≥d(p, x)→T∗(n)≥d(p, T (x)). Note that &p Nand &p N→Nactually do not depend on p, hence we shall denote them simply &Nand &N→N, respectively. Whereas a majorant y∗exists for any sequence yin X, it is a genuine restriction on Tto posses a majorant T∗. However, for large classes of mappings Tone can construct T∗, e.g. this is the case when Tis Lipschitz continuous (in the case of geodesic spaces also uniform continuity suffices) but also in general whenever Tmaps bounded sets to bounded sets. It is instructive to see what happens if we take the context of unbounded metric spaces, i.e. - using 3The bounded number quantifier can be easily eliminated by bounded collection. 7 the terminology from [15,26] - Tω[X, d]−band add constants α:N→Nand (an) : N→Xas before. Then we need to provide majorants α∗, a∗for these objects, which in the case of αcan be simply done by stipulating α∗(n) := max{α(i)|≤ n},whereas for (an) this requires - as above - a function a∗:N→Nsuch that a∗&p N→Xa. Then the bound Φ extractable from proofs of theorems of the form considered above will additionally also depend on α∗(i.e. on α) and a∗. From these data one can easily compute a bound bon X(e.g. we may take b:= 2 + 2a∗(α∗(0))) and, conversely, given such a bound bone can simply take a∗(n) := b. So, adding (T OT I) gives in both contexts the same results w.r.t. the extractability of bounds Φ and their uniformity. This situation, however, changes if we consider the axiomatization based on the II-modulus of total boundedness in the setting of unbounded metric structures: The theory Tω[X, d, T OT II]−bof totally bounded metric spaces is obtained by adding to Tω[X, d]−b (i) one constant γN→Nand (ii) one universal axiom: (T OT II)∀kN∀xN→X∃I, J ≤Nγ(k)I <NJ∧dX(xI, xJ)≤R 1 k+ 1. Due to the absence of the sequence (an) from this axiomatization, the extracted bounds will only depend on γinstead of α, a∗(or α, b). This results in a strictly greater uniformity of the bounds as the following example shows. Consider the sequence (X, dn) of metric spaces defined as follows: X:= {0,1}, dn(0,1) := dn(1,0) := n, dn(0,0) = dn(1,1) = 0. It is easy to see that γ(n) := 2 is a common II-modulus of total boundedness for all the spaces (X, dn) (since any sequence of 3 elements of Xhas to repeat some element), while the diameter of (X, dn) tends to infinity as ndoes. Hence our bounds Φ will be uniform for all the spaces (X, dn) which first might look impossible since, after all, (T OT II)does imply that Xis bounded, i.e. (++) ∃b∈N∀x, y ∈X(d(x, y)< b). However, (++) is of the form ∃∀, which is not allowed in statements of the form (+) considered above. Noneffectively, (++) can be equivalently reformulated as (++)′∀(xn),(yn)∈XN∃N∈N(d(xN, yN)< N), which is of the form (+), so that the aforementioned uniform bound extraction applies (given majorants x∗, y∗for (xn),(yn)). Indeed, define recursively n0:= 0, nk+1 := max i,j≤k{nk, d(xni, ynj), d(xni, xnj), d(yni, ynj)}+ 3, which can easily be effectively bounded using only dand x∗, y∗. Proposition 2.5. For any metric space Xwith II-modulus of total boundedness γwe have: ∃N≤nγ(0) (d(xN, yN)< N). 8 Proof. Suppose that ∀k≤γ(0)(d(xnk, ynk)≥nk).Then, for all k≤γ(0),one of the two cases (1) ∀i < k (d(xnk, xni), d(xnk, yni)>1) or (2) ∀i < k (d(ynk, xni), d(ynk, yni)>1) holds since, otherwise, d(xnk, ynk)≤nk−1+ 2 < nk. Define a sequence z0,...,zγ(0) as follows: for k≤γ(0) put zk:= xnk, if (1) holds, and zk:= ynk, otherwise (which implies that (2) holds). Then d(zi, zj)>1 whenever 0 ≤i < j ≤γ(0) which, however, contradicts the definition of γ. Hence ∃k≤γ(0) (d(xnk, ynk)< nk).Since nk≤nγ(0),the claim follows. Remark 2.6. As mentioned already, logical metatheorems of the form discussed above have also been established for more enriched structures such as W-hyperbolic spaces, uniformly convex Whyperbolic spaces, R-trees, δ-hyperbolic spaces (in the sense of Gromov) and CAT(0)-spaces as well normed spaces, uniformly convex normed spaces, complete versions of these spaces and Hilbert spaces. Most recently, also abstract Lpand C(K)-spaces have been covered ([19]). In the normed case, the reference point p∈Xused in the majorization relation will always be the zero vector 0X(see [15,25,26,36,37,19] for all this). In all these cases one can add the requirement of X(or of some bounded subset in the normed case) to be totally bounded with moduli of total boundedness in the form I or II as above. Thus the applications given in this paper can be viewed as instances of corresponding logical metatheorems. 2.2 Examples In this subsection we give simple examples of II-moduli of total boundedness that are computed explicitly. Although some of the proofs are straightforward we include them for completeness. Example 2.7. Let A= [0,1] be the unit interval in R. Then γ:N→N,γ(k) = k+1 is a II-modulus of total boundedness for A. Proof. Let k∈Nand (xn) be a sequence in A. Divide the interval [0,1] into k+ 1 subintervals of equal length 1/(k+1). Applying the pigeonhole principle we obtain that there exist 0 ≤i < j ≤k+1 such that |xi−xj| ≤ 1/(k+ 1). Example 2.8. Let Abe a bounded subset of Rnand b > 0be such that kak2≤bfor every a∈A. Then γ:N→N,γ(k) = 2(k+ 1)√nbnis a II-modulus of total boundedness for A. Proof. Let k∈Nand (xp)⊆A. Denote N=⌈2(k+ 1)√nb⌉. Clearly, Ais included in the cube [−b, b]n. Divide this cube into Nnsubcubes of equal side lengths 2b/N. The diameter of each subcube is 2b√n/N ≤1/(k+ 1). Applying the pigeonhole principle we obtain that there exist 0≤i < j ≤Nnsuch that kxi−xjk2≤1/(k+ 1). Example 2.9. Let (X, d)be a metric space and A⊆Xtotally bounded with II-modulus of total boundedness γ. Then the closure of Ais totally bounded with II-modulus of total boundedness γ. 9 Proof. Let k∈Nand g:N→N. For simplicity, let us denote with ϕthe mapping ϕFdefined by (6). Since both ϕand Φ are nondecreasing and Φ majorizes ϕ, an immediate induction gives us that Ψ0(n, k, g, ϕ, χ, βH)≤Ψ0(n+ 1, k, g, ϕ, χ, βH), Ψ0(n, k, g, Φ, χ, βH)≤Ψ0(n+ 1, k, g, Φ, χ, βH) and Ψ0(n, k, g, ϕ, χ, βH)≤Ψ0(n, k, g, Φ, χ, βH) for all n∈N. Define for every i∈N ni:= Ψ0(i, k, g, ϕ, χ, βH).(8) Claim 1: For all j≥1 and all 0 ≤i < j,xnjis a χg(ni,2βH(2k+ 1) + 1)-approximate F-point. Proof of claim: As j≥1 and nj= Ψ0(j, k, g, ϕ, χ, βH) = ϕχM g(Ψ0(j−1, k, g, ϕ, χ, βH),2βH(2k+ 1) + 1) =ϕχM g(nj−1,2βH(2k+ 1) + 1), xnjis a χM g(nj−1,2βH(2k+1)+1)-approximate F-point. Since 0 ≤i≤j−1, we have that ni≤nj−1. Apply now the fact that χM gis nondecreasing in the first argument to get that χg(ni,2βH(2k+ 1) + 1) ≤χM g(ni,2βH(2k+ 1) + 1) ≤χM g(nj−1,2βH(2k+ 1) + 1). Claim 2: There exist 0 ≤I < J ≤Psatisfying ∀l∈[nI, nI+g(nI)] d(xl, xnJ)≤1 2k+ 2. Proof of claim: By the property of γbeing a II-modulus of total boundedness for Xwe get that there exist 0 ≤I < J ≤Psuch that d(xnI, xnJ)≤1 αG(2βH(2k+ 1) + 1) + 1 and so, using that αGis a G-modulus, G(d(xnI, xnJ)) ≤1 2βH(2k+ 1) + 2.(9) By the first claim, we have that xnJis a χg(nI,2βH(2k+1)+1)-approximate F-point. Applying now the uniform (G, H)-F´ejer monotonicity of (xn) w.r.t. Fwith r:= 2βH(2k+1)+1, n := nI, m := g(nI) and p:= xnJ, we get that for all l≤g(nI), H(d(xnI+l, xnJ)) ≤G(d(xnI, xnJ)) + 1 2βH(2k+ 1) + 2 ≤1 βH(2k+ 1) + 1. Since βHis an H-modulus, ∀l≤g(nI)d(xnI+l, xnJ)≤1 2k+ 2. and so the claim is proved.  16 It follows that ∀k, l ∈[nI, nI+g(nI)] d(xk, xl)≤1 k+ 1. Since nI= Ψ0(I, k, g, ϕ, χ, βH)≤Ψ0(I, k, g, Φ, χ, βH) and I≤P, we get that nI≤Ψ0(P, k, g, Φ, χ, βH) = Ψ(k, g, Φ, χ, αG, βH, γ). The theorem holds with N:= nI. Corollary to the proof: One of the numbers n0,...,nP−1is a point of metastability. Theorem 5.1 remarkably implies the Cauchy property of (xn) in the absence of Xbeing complete (and hence compact) and of Fbeing explicitly closed which, as we remarked after Proposition 4.3, both were necessary if (xn) only was assumed to be (G, H)-Fej´er monotone rather than being uniformly (G, H)-Fej´er monotone. This is a qualitative improvement of Proposition 4.3 whose proof is based on our quantitative analysis of metastability although the result as such does not involve metastability at all: Corollary 5.2. Let Xbe totally bounded and (xn)be uniformly (G, H)-Fej´er monotone having approximate F-points. Then (xn)is Cauchy. The next theorem is a direct quantitative ‘finitization’ of Proposition 4.3 in the sense of Tao: Theorem 5.3. In addition to the assumptions of Theorem 5.1 we suppose that Fis uniformly closed with moduli δF, ωF.Then for all k∈Nand all g:N→N, ∃N≤˜ Ψ∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1 and xi∈AFk, where ˜ Ψ (k, g, Φ, χ, αG, βH, γ, δF, ωF) := Ψ(k0, g, Φ, χk,δF, αG, βH, γ), with Ψdefined as in Theorem 5.1 k0= max k, ωF(k)−1 2and χk,δF(n, m, r) := max{δF(k), χ(n, m, r)}. Proof. With χalso χk,δFis a modulus of (xn) being uniformly (G, H)-Fej´er monotone w.r.t. F. Applying Theorem 5.1 to (k0, χk,δF) we get that ∃N≤˜ Ψ∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k0+ 1 ≤1 k+ 1. From the proof of Theorem 5.1, it follows that there exists 0 ≤I < J ≤Psuch that N=nIand xnJis a (χk,δF)g(N, 2βH(2k0+ 1) + 1)-approximate F-point and ∀i∈[N, N +g(N)] d(xi, xnJ)≤1 2k0+ 2 ≤1 ωF(k) + 1. Since (χk,δF)g(N, 2βH(2k0+ 1) + 1) = χk,δF(N, g(N),2βH(2k0+ 1) + 1) ≥δF(k), it follows that xnIis a δF(k)-approximate F-point. Hence by the definition of ωF, we get that xi∈AFkfor all i∈[N, N +g(N)]. 17 Notation: In our applications δFwill be mostly δF(k) = 2k+ 1. In this case we simply write χk instead of χk,δFwhen applying Theorem 5.3. Remark 5.4. Theorems 5.1 and 5.3 hold for Xboundedly compact and (xn)bounded. In this case, the bounds will depend on a II-modulus of total boundedness for the closed ball B(a, b), where a∈X and b≥d(xn, a)for all n. Remark 5.5. Theorem 5.3 is a finitization of Proposition 4.3 in the sense of Tao since it only talks about a finite initial segment of (xn)but trivially implies back the infinitary Proposition 4.3 for uniformly closed Fand uniformly (G, H)-Fej´er monotone sequences. Proof. Noneffectively ∀k∈N∀g:N→N∃N∈N∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1 and xi∈AFk implies the Cauchy property of (xn). Since Xis complete, (xn) converges to a point bx∈X. It remains to prove that bx∈F. One can easily see, by taking gto be a constant function, that (xn) has the liminf property w.r.t. F. Apply now Lemma 3.5 to conclude that bx∈F. Assume that (xn) is asymptotically regular w.r.t. F. A mapping Φ+:N×NN→Nsatisfying ∀k∈N∀g:N→N∃N≤Φ+(k, g)∀m∈[N, N +g(N)] (xm∈AFk) is said to be a rate of metastability for the asymptotic regularity of (xn) w.r.t. F. A rate of asymptotic regularity of (xn) w.r.t. Fis a function Φ++ :N→Nwith ∀k∈N∃N≤Φ++(k)∀m≥N(xm∈AFk) Obviously, this is equivalent with the fact that Φ++ satisfies ∀k∈N∀n≥Φ++(k) (xn∈AFk). If instead of an approximate F-point bound Φ for (xn) one has a rate of metastability Φ+for the asymptotic regularity of (xn) w.r.t. F, then one can directly combine Ψ from Theorem 5.1 and such a Φ+into a bound Ψ′:= Ω(Ψ,Φ+) satisfying the claim of Theorem 5.3 without any uniform closedness assumption on Fand no need to use ωF. The transformation Ω gets particularly simple if instead of Φ+we even have a rate Φ++ of asymptotic regularity w.r.t. F. We first have to define one more case of the general majorization relation &: Definition 5.6. A functional Φ : N×NN→Nis majorized by Φ∗:N×NN→N(short Φ∗&Φ) if ∀k∈N∀g:N→N(k′≥kand g′&N→Ng→Φ∗(k′, g′)≥Φ∗(k, g),Φ(k, g)) . Φis called selfmajorizing if Φ&Φ. For any function f:N→Nwe shall denote fM:N→N, fM(n) := max{f(i)|i≤n}. Then, as remarked in Section 2.1,fM&N→Nf. In the sequel, k∈Nand g:N→N. We define the following functionals: 18 (i) g∗:N→N, g∗(n) = n+gM(n); (ii) for every l∈N, ˜gl:N→N,˜gl(m) := g∗(max{l, m}); (iii) for every δ:N×NN→N, hk,g,δ :N→N, hk,g,δ(n) := g∗(max{n, δ(k, ˜gn)}).(10) (iv) Ωk,g : (N×NN→N)×(N×NN→N)→N, defined for every δ, θ :N×NN→N, by Ωk,g(δ, θ) := max{δ(k, hk,g,θ), θ(k, ˜gδ(k,hk,g,θ ))}; (11) (v) for every l∈N,gl(n) : N→N, gl(n) := gM(n+l) + l; (vi) ˜ Ωk,g : (N×NN→N)×NN→N, defined for every δ:N×NN→N, f :N→N, by ˜ Ωk,g(δ, f) := δ(k, gf(k)) + f(k).(12) One can easily verify the following Lemma 5.7. (i) For all l, l∗∈N,l∗≥limplies ˜gl∗&˜gland gl∗&gl. (ii) For all δ, δ∗:N×NN→N,δ∗&δimplies hk,g,δ∗&hk,g,δ. (iii) For all δ, δ∗, θ, θ∗:N×NN→N, if δ∗&δand θ∗&θ, then Ωk,g(δ∗, θ∗)≥Ωk,g(δ, θ). (iv) For all δ, δ∗:N×NN→N,f, f∗:N→Nif δ∗&δand f∗&f, then ˜ Ωk,g(δ∗, f∗)≥˜ Ωk,g(δ, f). Theorem 5.8. Let (xn)be a Cauchy sequence with a selfmajorizing rate of metastability Ψ. (i) Assume that (xn)is asymptotically regular w.r.t. F, with Φ+being a selfmajorizing rate of metastability for the asymptotic regularity. Then for all k∈Nand all g:N→N, ∃N≤Ω∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1 and xi∈AFk, where Ω(k, g, Ψ,Φ+) := Ωk,g(Ψ,Φ+). (ii) Assume that (xn)is asymptotically regular w.r.t. F, with Φ++ being a rate of asymptotic regularity. Then for all k∈Nand all g:N→N, ∃N≤˜ Ω∀i, j ∈[N, N +g(N)] ∀m≥Nd(xi, xj)≤1 k+ 1 and xm∈AFk, where ˜ Ω(k, g, Ψ,Φ++) := ˜ Ωk,g(Ψ,(Φ++)M). Proof. (i) Let ψ, ϕ+:N×NN→Nbe the functionals which, given l∈Nand δ:N→N, search for the least actual point nof metastability upper bounded by Ψ(l, δ),Φ+(l, δ) respectively. Thus, we have that ψ(l, δ)≤Ψ(l, δ), ϕ+(l, δ)≤Φ+(l, δ), ∀i, j ∈[ψ(l, δ), ψ(l, δ) + δ(ψ(l, δ))] d(xi, xj)≤1 l+ 1(13) 19 and ∀i∈[ϕ+(l, δ), ϕ+(l, δ) + δ(ϕ+(l, δ))] (xi∈AFl).(14) Let us take N:= Ωk,g(ψ, ϕ+). Claim: ∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1 and xi∈AFk. Proof of claim: Let N0:= ψ(k, hk,g,ϕ+). Then N= max{N0, ϕ+(k, ˜gN0)}.Apply (13) with l:= kand δ:= hk,g,ϕ+and (14) to l:= kand δ:= ˜gN0to get that ∀i, j ∈[N0, N0+hk,g,ϕ+(N0)] d(xi, xj)≤1 k+ 1(15) and ∀i∈[ϕ+(k, ˜gN0), ϕ+(k, ˜gN0) + ˜gN0(ϕ+(k, ˜gN0))] (xi∈AFk).(16) Remark now that Nis an upper bound for both N0and ϕ+(k, ˜gN0) and, furthermore, that hk,g,ϕ+(N0) = ˜gN0(ϕ+(k, ˜gN0)) = g∗(Ωk,g(ψ, ϕ+)) ≥Ωk,g(ψ, ϕ+) + g(Ωk,g(ψ, ϕ+)) = N+g(N). The claim follows.  Since Ψ,Φ+are selfmajorizing and bounds for ψ, φ+they are majorants for ψ, φ+. Apply now Lemma 5.7.(iii) to conclude that N= Ωk,g(ψ, ϕ+)≤Ωk,g(˜ Ψ,Φ+)(g). (ii) Let ψ:N×NN→Nbe as in (i) and take N:= ˜ Ωk,g(ψ, Φ++). Apply (13) with l:= kand δ:= gΦ++(k)and denote N0:= ψ(k, gΦ++(k)) to get that ∀i, j ∈[N0, N0+gΦ++(k)(N0)] d(xi, xj)≤1 k+ 1 Remark that N0≤Nand that N0+gΦ++(k)(N0) = ˜ Ω(k, g, ψ, Φ++) + gM(˜ Ω(k, g, ψ, Φ++)) =N+gM(N)≥N+g(N). Furthermore, since N≥Φ++(k) and Φ++ is a rate of asymptotic regularity w.r.t. F, we get that xm∈AFkfor all m≥N. The fact that N≤˜ Ωk,g(Ψ,(Φ++)M) follows immediately, using Lemma 5.7.(iv). In fact, one may also swap the roles of Ψ and Φ+in the definition of Ω and, in practice, one has to check which one results in a better bound. Furthermore, the assumption that Ψ,Φ+are selfmajorizing can always been achieved for bounds Ψ,Φ+extracted via the proof-theoretic methods presented in Section 2. 20 Corollary 5.9. Let (xn)be a uniformly (G, H)-Fej´er monotone sequence with modulus χwhich is asymptotically regular with a selfmajorizing rate of metastability for the asymptotic regularity Φ+. For each, αG, βH, γ :N→Nand χ:N3→Ndefine the functional Ψ+(k, g) := Ψ(k, g, Φ, χM, αM G, βM H, γM), where Ψis the bound from Theorem 5.1,Φ(k) := Φ+(k, 0) and χM(n, m, k) := max{χ(˜n, ˜m, ˜ k)|˜n≤n, ˜m≤m, ˜ k≤k}). Then for all k∈N, g :N→N ∃N≤Ω(k, g, Ψ+,Φ+)∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1 and xi∈AFk. Similarly for ˜ Ωinstead of Ω(with Φ := (Φ++)M) where we then even have ∀m≥N(xm∈AFk). Proof. With χ, αG, βH, γ also χM, αM G, βM H, γMare a modulus of uniform (G, H)-Fej´er monotonicity, G, H-moduli and a II-modulus of total boundedness, respectively. Moreover, Φ is an approximate Fpoint bound for (xn).Hence, by Theorem 5.1, Ψ+is a rate of metastability for (xn) which, moreover, is selfmajorizing. The claim now follows from Theorem 5.8. We conclude this section with a trivial but instructive example for Theorem 5.1, namely that the well-known rate of metastability for the Cauchy property of monotone bounded sequences from [26, Proposition 2.27] can be recovered (modulo a constant) from this theorem: let X= [0,1] and (xn) be a nondecreasing sequence in X. Let us take F=\ k∈N ˜ Fk,where ˜ Fk:= {p∈X|xk≤p}. Then, clearly, (i) AFk=˜ Fk,(ii) Φ++ := id is a rate of asymptotic regularity and χ(n, m, r) := n+m is a modulus of the uniform Fej´er monotonicity of (xn) and we may take γ(k) = k+ 1 (see Example 2.7). For monotone g, Theorem 5.1 now gives Ψ(k, g) := ˜g4(k+1)(0) with ˜g(n) := n+g(n),while the direct proof in this case yields Ψ(k, g) := ˜gk(0). 6 Quasi-Fej´er monotone sequences As a common consequence of arriving at a finitary quantitative version of an originally non-quantitative theorem, one can easily incorporate error terms as has been considered under the name of quasi-Fej´er monotonicity (due to [12]). As pointed out in [11], quasi-Fej´er monotone sequences provide a framework for the analysis of numerous optimization algorithms in Hilbert spaces. Definition 6.1. A sequence (xn)in a metric space (X, d)is called quasi-Fej´er monotone (of order 0< P < ∞) w.r.t. some set ∅ 6=F⊆Xif ∀n∈N∀p∈Fd(xn+1, p)P≤d(xn, p)P+εn, where (εn)is some summable sequence in R+. 21 The appropriate generalization to general functions (G, H) then is: Definition 6.2. For G, H as in the definition of (G, H)-Fej´er monotonicity we say that (xn)is quasi-(G, H)-Fej´er monotone w.r.t. Fif ∀n, m ∈N∀p∈FH(d(xn+m, p)) ≤G(d(xn, p)) + n+m−1 X i=n εi. Note that for G(x) := H(x) := xPthis covers the notion of quasi-Fej´er monotonicity. The uniform version of this notion then is: Definition 6.3. (xn)is uniformly quasi-(G, H)-Fej´er monotone w.r.t. Fand a given representation of Fvia AFkas before if ∀r, n, m ∈N∃k∈N∀p∈Xp∈AFk→ ∀l≤m(H(d(xn+l, p)) < G(d(xn, p)) + Pn+m−1 i=nεi+1 r+1 ). Any function χ:N3→Nsuch that χ(r, n, m)provides such a kis called a modulus of (xn)being uniformly quasi-(G, H)-Fej´er monotone w.r.t. F. Let ξ:N→Nbe a Cauchy modulus of Pεi,i.e. ∞ P i=ξ(n) εi<1 n+1 for all n∈N. If (xn) has the lim inf-property w.r.t. Fwe can define bϕF(k, n) := min{m∈N|m≥n∧xm∈AFk}. Any monotone (in k, n) upper bound b Φ of bϕFis called a lim inf-bound w.r.t. F. Theorem 6.4. Assume that (i) (xn)is uniformly quasi-(G, H)-Fej´er monotone w.r.t. F, with modulus χ, and (εn)with Cauchy rate ξfor Pεi; (ii) (xn)has the lim inf-property w.r.t. F, with b Φbeing a lim inf-bound w.r.t. F. Then (xn)is Cauchy and, moreover, for all k∈Nand all g:N→N, ∃N≤b Ψ(k, g, Φ, χ, αG, βH, γ, ξ)∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1, where b Ψ(k, g, Φ, χ, αG, βH, γ, ξ) := b Ψ0(P, k, g, Φ, χ, βH, ξ), with χg(n, k) := χ(n, g(n), k), χM g(n, k) := max{χg(i, k)|i≤n}, P:= γ(αG(4βH(2k+ 1) + 3)) + 1 and     b Ψ0(0, k, g, Φ, χ, βH, ξ) := 0 b Ψ0(n+ 1, k, g, Φ, χ, βH, ξ) := b ΦχM g(Ψ0(n, k, g, Φ, χ, βH, ξ),4βH(2k+ 1) + 3) , ξ(4βH(2k+ 1) + 3). 22 Proof. The proof is the same as the one of Theorem 5.1 up to (9) which now holds with 1/(4βH(2k+ 1) + 4) instead of 1/(2βH(2k+ 1) + 2).We then use uniform quasi-(G, H)-Fej´er monotonicity as we did before without ‘quasi’ to now get that for all l≤g(nI) H(d(xnI+l, xnJ)) ≤G(d(xnI, xnJ)) + nI+l−1 X i=nI εi+1 4βH(2k+ 1) + 4. By construction of nIwe know that nI≥ξ(4βH(2k+ 1) + 3) (not that by the addition of ‘+1’ to the original definition of Pthat was used in the proof of Theorem 5.1 I, J can now be choosen so that 0 < I < J ≤Prather than only 0 ≤I < J ≤P) and so nI+l−1 X i=nI εi≤1 4βH(2k+ 1) + 4 and so we get in total H(d(xnI+l, xnJ)) ≤G(d(xnI, xnJ)) + 1 2βH(2k+ 1) + 2 from where we can finish the proof as before. As it is clear from the proof above, one actually does not need a Cauchy modulus ξof the error-sum but only a rate of metastability. With the new bound b Ψ from Theorem 6.4 instead of Ψ all the other results of the previous section extend in the obvious way to the ‘quasi’-case. As a consequence of this, we could incorporate also in the iterations considered in the rest of this paper error terms which we, however, will not carry out. 7 Application - Fis F ix(T) Let Xbe a metric space, C⊆Xa nonempty subset and T:C→Cbe a mapping. We assume that Thas fixed points and define Fas the nonempty fixed point set Fix(T) of T. One has F=\ k∈N ˜ Fk,where ˜ Fk=x∈C|d(x, T x)≤1 k+ 1. In this case, for all k∈Nwe have that that AFk=˜ Fkand the k-approximate F-points are precisely the 1/(k+ 1)-approximate fixed points of T. Let us recall that the mapping Tis uniformly continuous with modulus ωT:N→Nif for all k∈N and all p, q ∈C, d(p, q)≤1 ωT(k) + 1 →d(T p, T q)≤1 k+ 1. One can see easily that the following properties hold. Lemma 7.1. Let (xn)be a sequence in C. (i) (xn)has approximate F-points if and only if for all k∈Nthere exists N∈Nsuch that d(xN, T xN)≤1 k+ 1. If this is the case, we say also that (xn)has approximate fixed points. 23 (ii) (xn)has the liminf property w.r.t. Fif and only if lim inf n→∞ d(xn, T xn) = 0. (iii) (xn)is asymptotically regular w.r.t. Fif and only if lim n→∞d(xn, T xn) = 0. (iv) If Tis continuous, then Fis explicitly closed. (v) If Tis uniformly continuous with modulus ωT, then Fis uniformly closed with moduli ωF(k) = max{4k+ 3, ωT(4k+ 3)}and δF(k) = 2k+ 1. Remark 7.2. Uniform closedness can be viewed as a quantitative version of the special extensionality statement (∗)q∈F∧p=Xq→p∈F. Extensionality w.r.t. p=Xq:= kp−qkX= 0 is not included as an axiom in our formal framework (for reasons explained in [25]) and has to be derived (if needed) from appropriate uniform continuity assumptions (see item (v)in the lemma above). In the case of (∗), however, it suffices to have the moduli ωF, δTwhich (as we will see in Section 7.4) are also available for interesting classes of in general discontinuous mappings T(where, in particular, the model theoretic approach to metastability from [2] is not applicable as is stands). As a consequence of Proposition 4.3 and Remark 4.5, we get Proposition 7.3. Let Cbe a boundedly compact subset of a metric space Xand T:C→Cbe continuous with F=F ix(T)6=∅. Assume that (xn)is bounded and (G, H)-Fej´er monotone with respect to Fand that (xn)has approximate fixed points. Then (xn)converges to a fixed point of T. The continuity of Tcan be replaced by the weaker assumption that Fis explicitly closed (see Section 7.4 for a class of in general discontinuous functions for which Fix(T)is uniformly closed). If we weaken ‘boundedly compact’ to ‘totally bounded’ or drop the assumption that Tis continuous, one cannot even prove that (xn) is Cauchy, as the following examples show. Example 7.4. Let C:= (0,1] ∪ {2}with the metric d(x, y) := min{|x−y|,1}.Then Cis totally bounded and the mapping T:C→C, T (x) := x/2,if x∈(0,1], T (2) := 2 is continuous with F:= F ix(T) = {2}.Now let xn:= Tn(1), for even n, and xn:= 1 for odd n. Then (xn)has approximate fixed points and is Fej´er monotone w.r.t. Fbut clearly not Cauchy. If we drop the explicit closedness of F, we can slightly modify the above example to get a counterexample to the Cauchyness of (xn)even for compact C: just take C:= [0,1] ∪ {2}and define T(0) := 2. 7.1 Picard iteration for (firmly) nonexpansive mappings Assume that Tis nonexpansive. Then, obviously, Tis uniformly continuous with modulus ωT=idN. We consider in the sequel the Picard iteration starting from x∈C: xn:= Tnx. One can see by induction that for all n, m ∈Nand p∈C, d(xn+m, p)≤d(xn, p) + md(p, T p). As an immediate consequence, we get that (xn) is Fej´er monotone, hence, in particular, bounded. In fact, one can easily prove more: 24 Lemma 7.5. (xn)is uniformly Fej´er monotone w.r.t. Fwith modulus χ(n, m, r) = m(r+ 1). Applying Proposition 7.3, we get Corollary 7.6. Let Cbe a boundedly compact subset of a metric space Xand T:C→Cbe nonexpansive with F ix(T)6=∅. Assume that (xn)has approximate fixed points. Then (xn)converges to a fixed point of T. As (xn) is uniform Fej´er monotone w.r.t. Fand Fis uniformly closed, we can apply our quantitative Theorems 5.1 and 5.3 to get the following: Theorem 7.7. Assume that Cis totally bounded with II-modulus of total boundedness γ,T:C→C is nonexpansive with Fix(T)6=∅and that (xn)has approximate fixed points, with Φbeing an approximate fixed point bound. Then for all k∈Nand all g:N→N, (i) There exists N≤Σ(k, g, Φ, γ)such that ∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1, where Σ(k, g, Φ, γ) = Σ0(γ(4k+ 3), k, g, Φ), with Σ0(0, k, g, Φ) = 0 and Σ0(n+ 1, k, g, Φ) = Φ (4k+ 4)gM(Σ0(n, k, g, Φ)). (ii) There exists N≤˜ Σ(k, g, Φ, γ)such that ∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1 and d(xi, T xi)≤1 k+ 1, where ˜ Σ(k, g, Φ, γ) = ˜ Σ0(γ(8k+ 7), k, g, Φ), with ˜ Σ0(0, k, g, Φ) = 0 and ˜ Σ0(n+ 1, k, g, Φ) = Φ max n2k+ 1,(8k+ 8)gM(˜ Σ0(n, k, g, Φ))o. Proof. (i) With Ψ,Ψ0as in Theorem 5.1,αG=βH=idNand χas in Lemma 7.5, define Σ(k, g, Φ, γ) = Ψ(k, gM,Φ, χ, αG, βH, γ) and Σ0(l, k, g, Φ) = Ψ0(l, k0, gM,Φ, χ, βH). (ii) Apply Theorem 5.3 for gM, using that ωF(k) = 4k+ 3 and δF(k) = 2k+ 1, by Lemma 7.1.(v). It follows that k0= 2k+ 1 and (χk)M gM(n, r) = max{2k+ 1, gM(n)(r+ 1)}. If, moreover, (xn) is asymptotic regular and we can compute a rate of asymptotic regularity Φ++, then we can also apply Corollary 5.9. Theorem 7.8. Assume that Cis totally bounded with II-modulus of total boundedness γ,T:C→C is nonexpansive with Fix(T)6=∅and that (xn)is asymptotic regular with Φ++ being a rate of asymptotic regularity. Then for all k∈Nand all g:N→N, there exists N≤Θ(k, g, Φ++, γ)such that ∀i, j ∈[N, N +g(N)] ∀m≥Nd(xi, xj)≤1 k+ 1 and d(xm, T xm)≤1 k+ 1, 25 Then for every k∈N,g:N→N, ∃N≤Φ+(k, g, L, b, η),∀m∈[N, N +g(N)] d(xm, T xm)≤1 k+ 1, where Φ+=hM(0), h(n) = g(n) + n+ 1, M =⌈3(b+ 1)/θ⌉, θ=1 4(k+ 1)L2ηb+ 1,1 4(k+ 1)(b+ 1). If ηsatisfies the extra property from Lemma 7.14, then one can replace it by ˜ηin θ. Proof. Let k∈N,g:N→N. Then there exists p∈Csuch that d(x, p)≤band d(p, T p)≤ 2−Φ+−2/(3µ). Take n≤Φ+. Then d(p, T p)≤2−n−2/(3µ). By (28), d(xn+1, p)≤d(xn, p) + µ(1 −1/L)d(p, T p)≤d(xn, p) + 2−n−2/3. Denote an=d(xn, p), α0= 1/6 and αn=1−Pn−1 i=0 2−i−1/6 for n≥1. Apply [31, Proposition 6.4] with bn=βn=γn= 0, cn= 2−n−2/3, B1=B2=C2= 0, A1=b,A2= 1/6, C1= 1/6, ˜g(n) = g(n) + 1 to get that for all n≤Φ++ 1, d(xn, p)≤b+ 1/6 and that there exists N=hs(0) for some s < M such that ∀i, j ∈[N, N +g(N) + 1],|ai−aj| ≤ θ, |αi−αj| ≤ θ. We show that ∀m∈[N, N +g(N)], d(xm, T xm)≤1 k+ 1. Let m∈[N, N +g(N)]. Suppose d(xm, T xm)>1/(k+ 1). Since m, m + 1 ∈[N, N +g(N) + 1] we have that |d(xm+1, p)−d(xm, p)| ≤ θ, |αm+1 −αm|= 2−m−2/3≤θ. Assume that d(xm, p)≥1/(4(k+ 1)). Note that m≤N+g(N)< h(N) = hs+1(0) ≤hM(0) = Φ+. Hence, d(p, T p)≤2−Φ+−2/(3µ)<2−m−2/(3µ)≤1/(3µ). Apply (29) with α= 1/(4(k+ 1)), β=b+ 2/3, ν= 2−m−2/(3µ) and δ= 1/(3µ) to obtain that d(xm+1, p)< d(xm, p) + 2−m−2/3−2θ. This yields that 2θ < d(xm, p)−d(xm+1, p) + 2−m−2/3≤2θ, a contradiction. So, d(xm, p)< 1/(4(k+ 1)). Then d(xm, T xm)≤d(xm, p) + d(p, T xm)≤2d(xm, p) + µd(p, T p) ≤1 2(k+ 1) + 2−m−2/3≤1 2(k+ 1) +θ≤1 k+ 1. 32 In the particular case where in the above result the mapping g= 0, we obtain an approximate fixed point bound for (xn) in the context of UCW -hyperbolic spaces. In case of CAT(0) spaces this bound is quadratic in the error since in we then can take η(r, ε) := ε2/8 and so ˜η(r, ε) := ε/8. Having such an approximate fixed point bound Φ, because (xn) is additionally uniformly Fej´er monotone w.r.t. Fand Fis uniformly closed, we can apply Theorem 5.3 to obtain, for Cconvex and totally bounded with II-modulus of total boundedness γ, a result similar to Theorem 7.7.(ii) that yields a functional ˜ Σ := ˜ Σ(k, g, Φ, γ, µ, L) with the property that for all k∈Nand all g:N→N there exists N≤˜ Σ such that ∀i, j ∈[N, N +g(N)] d(xi, xj)≤1 k+ 1 and d(xi, T xi)≤1 k+ 1. 7.5 Mann iteration for asymptotically nonexpansive mappings Let Xbe a W-hyerbolic space, C⊆Xa convex subset and (kn) be a sequence in [0,∞) satisfying lim n→∞ kn= 0. A mapping T:C→Cis said to be asymptotically nonexpansive [16] with sequence (kn) if for all x, y ∈Cand for all n∈N, d(Tnx, T ny)≤(1 + kn)d(x, y). Let Tbe asymptotically nonexpansive with sequence (kn) in [0,∞). We assume furthermore that (kn) is bounded in sum by some K∈N, i.e. ∞ X n=0 kn≤K. As an immediate consequence, we get that Tis Lipschitz continuous with Lipschitz constant 1 + K, hence, as in the case of strict pseudo-contractions, it follows that Fis uniformly closed with moduli ωF(k) = (1 + K)(4k+ 4) and δF(k) = 2k+ 1. The Mann iteration starting with x∈Cis defined by x0:= x, xn+1 := (1 −λn)xn+λnTn(xn),(30) where (λn) is a sequence in 1 L,1−1 Lfor some L∈N, L ≥2. Lemma 7.16. (i) For all n, m ∈Nand all p∈C, d(xn+m, p)≤eKd(xn, p) + eKm(n+m+K)d(p, T p). (ii) (xn)is uniformly (G, H)-Fej´er monotone w.r.t. Fwith modulus χ(n, m, r) = m(n+m+K)⌈eK⌉(r+ 1), where G(a) = idR+and H=eKidR+. An H-modulus is given by βH(k) = ⌈eK⌉(k+ 1). Proof. (i) By [24, Lemma 4.4]. (ii) Apply (i). Effective rates of metastability (and, as a particular case, approximate fixed point bounds) for the Mann iteraton were obtained in [30] in the setting of uniformly convex Banach spaces and in [31] for the more general setting of UCW -hyperbolic spaces. Thus we can apply Theorems 5.1 and 5.3. The result of applying Theorem 5.1 gives essentially the rate of metastability that was first extracted in [24] in a more ad-hoc fashion and which now appears as an instance of a general schema for computing rates of metastability. In fact, [24] has been the point of departure of the present paper. 33 8 An application to the Proximal Point Algorithm The proximal point algorithm is a well-known and popular method employed in approximating a zero of a maximal monotone operator. There exists an extensive literature on this topic which stems from the works of Martinet [43] and Rockafellar [49]. The method consists in constructing a sequence using successive compositions of resolvents which, under appropriate conditions, converges weakly to a zero of the considered maximal monotone operator. If imposing additional assumptions, one can even prove strong convergence. Here we show that we can apply our results to obtain a quantitative version of this algorithm in finite dimensional Hilbert spaces. In the sequel His a real Hilbert space and A:H→2His a maximal monotone operator. We assume that the set zerAof zeros of Ais nonempty. For every γ > 0 let JγA = (Id +γA)−1be the resolvent of γA. Then JγA is a single-valued firmly nonexpansive mapping defined on Hand zerA=Fix(JγA) for every γ > 0. We refer to [3] for a comprehensive reference on maximal monotone operators. Let x0∈Hand (γn) be a sequence in (0,∞). The proximal point algorithm starting with x0∈H is defined as follows: xn+1 =JγnAxn. Let us take F:= zerA. One can easily see that F=\ k∈N ˜ Fk,where ˜ Fk=\ i≤kx∈H| kx−JγiAxk ≤ 1 k+ 1. and that AFk=˜ Fkfor every k∈N. Furthermore, Fis uniformly closed with moduli ωF(k) = 4k+ 3, δF(k) = 2k+ 1. Lemma 8.1. (i) For all n∈N, m ∈N∗and all p∈H, kxn+m−pk ≤ kxn−pk+ n+m−1 X i=nkp−JγiApk.(31) (ii) (xn)is uniformly Fej´er monotone w.r.t. Fwith modulus χ(n, m, r) = max{n+m−1, m(r+1)}. Proof. (i) Remark that kxn+1 −pk=kJγnAxn−pk ≤ kJγnAxn−JγnApk+kJγnAp−pk ≤ kxn−pk+kJγnAp−pk and use induction. (ii) Apply (31) and the fact that p∈AFχ(n,m,r)implies that for all m≥1 and all l≤m, n+l−1 X i=nkp−JγiApk ≤ n+m−1 X i=nkp−JγiApk ≤ m χ(n, m, r) + 1 <1 r+ 1. 34 In the following we consider for n∈N, un=xn−xn+1 γn . The next lemma is well-known. We refer, e.g., to the proof of [3, Theorem 23.41] and [3, Exercise 23.2, p. 349]. Lemma 8.2. (i) For every p∈zerAand every n, i ∈N, kxn+1 −pk2≤ kxn−pk2−kxn−xn+1k2(32) kJγnAxn−JγiAxnk ≤ |γn−γi|kxn−xn+1k γn (33) kxn−JγiAxnk ≤ kxn−xn+1k+|γn−γi|kxn−xn+1k γn .(34) (ii) The sequence (kunk)is nonincreasing. Lemma 8.3. Assume that ∞ X i=0 γ2 n=∞with a rate of divergence θand that b > 0is an upper bound on kx0−pkfor some p∈zerA. Then (i) lim inf n→∞ kxn−xn+1k= 0 with modulus of liminf ∆(k, L, b) := b2(k+ 1)2+L−1,i.e. for every k∈Nand L∈Nthere exists L≤N≤∆(k, L, b)such that kxn−xn+1k ≤ 1/(k+ 1). (ii) lim n→∞un= 0 with rate of convergence β(k, θ, b) := θb2(k+ 1)2. Proof. (i) Applying (32) repeatedly we get that ∞ X n=0 kxn−xn+1k2≤ kx0−pk2≤b2. Let k, L ∈Nand ∆ := ∆(k, L, b). Suppose that for every L≤n≤∆, kxn−xn+1k>1/(k+1). Then (∆ −L+ 1) 1 (k+ 1)2< ∆ X n=Lkxn−xn+1k2≤b2, which yields ∆ < b2(k+ 1)2+L−1, a contradiction. (ii) Let k∈Nand β:= β(k, θ, b). Since (kunk) is nonincreasing, it is enough to show that there exists 0 ≤N≤βsuch that kuNk ≤ 1/(k+ 1). Suppose that for every 0 ≤n≤β, kunk>1/(k+ 1). Then 1 (k+ 1)2b2(k+ 1)2≤1 (k+ 1)2 β X n=0 γ2 n< β X n=0 γ2 nkunk2 = β X n=0 kxn−xn+1k2≤b2. 35 We have obtained a contradiction. Theorem 8.4. Assume that ∞ X i=0 γ2 n=∞with a rate of divergence θ. Then (xn)has approximate F-points with an approximate F-point bound Φ(k, mk, θ, b) := θb2(Mk+ 1)2b2(Mk+ 1)2−1, where mk= max 0≤i≤kγiand Mk=⌈(k+ 1)(2 + mk)⌉−1and b > 0is such that b≥ kx0−pkfor some p∈zerA. Proof. Let k∈N. By Lemma 8.3.(i), there exists N1≤∆(Mk,0, b) such that kxN1−xN1+1k ≤ 1 Mk+ 1 ≤1 (k+ 1)(2 + mk). If γN1≥1, it follows by (34) that for all i≤k, kxN1−JγiAxN1k ≤ kxN1−xN1+1k+|γN1−γi|kxN1−xN1+1k γN1 ≤2 + γi γN1kxN1−xN1+1k ≤(2 + mk)1 (k+ 1)(2 + mk)=1 k+ 1. Assume that γN1<1. Apply again Lemma 8.3.(i) to get the existence of N2≤∆(Mk, N1+ 1, b) such that N2> N1and kxN2−xN2+1k ≤ 1 Mk+1 . If γN2≥1 we use again the above argument. If γN2<1, we apply once more the fact that ∆ is a modulus of liminf for kxn−xn+1k. Let us denote for simplicity β:= θb2(Mk+ 1)2. Applying this argument βtimes we get a finite sequence N1< N2< . . . < Nβsuch that either γNj≥1 for some jor γNj<1 for all j= 1,...,β. In the first case, we have as above that kxNj−JγiAxNjk ≤ 1 k+1 for all i≤k. In the second case, since Nβ≥β and (kunk) is nonincreasing, an application of Lemma 8.3.(ii) for Mkgives us kuNβk ≤ kuβk ≤ 1 Mk+ 1 ≤1 (k+ 1)(2 + mk). It follows then that for all i≤k, kxNβ−JγiAxNβk ≤ kxNβ−xNβ+1k+|γNβ−γi|kxNβ−xNβ+1k γNβ =γNβkuNβk+|γNβ−γi|kuNβk ≤ 2γNβ+γikuβk ≤(2 + mk)1 (k+ 1)(2 + mk)=1 k+ 1. Since N1≤∆(Mk,0, b) = b2(Mk+ 1)2−1 and for all j= 2,...,β, Nj≤∆(Mk, Nj−1+ 1, b) = b2(Mk+ 1)2+Nj−1 we get that Nβ≤βb2(Mk+ 1)2−1, which finishes the proof. 36 As an immediate consequence of Proposition 4.3 and Remark 4.5 we obtain the well-known fact that in Rn, under the hypothesis that ∞ X i=0 γ2 n=∞, the proximal point algorithm converges strongly to a zero of the maximal monotone operator A. Furthermore, since kxnk ≤ M:= b+kpk(where b, p are as above) and, by Example 2.8,B(0, M) is totally bounded with II-modulus γ(k) = ⌈2(k+ 1)√nM⌉n, we can apply the quantitative Theorem 5.3 to get rates of metastability for (xn). Acknowledgements: Ulrich Kohlenbach was supported by the German Science Foundation (DFG Project KO 1737/5-2). Laurent¸iu Leu¸stean was supported by a grant of the Romanian National Authority for Scientific Research, CNCS - UEFISCDI, project number PN-II-ID-PCE-2011-3-0383. Adriana Nicolae was supported by a grant of the Romanian Ministry of Education, CNCS - UEFISCDI, project number PN-II-RU-PD-2012-3-0152. References [1] D. Ariza-Ruiz, L. Leu¸stean, G. Lopez-Acedo, Firmly nonexpansive mappings in classes of geodesic spaces, Trans. Amer. Math. Soc. 366 (2014), 4299–4322. [2] J. Avigad, J. Iovino, Ultraproducts and metastability, New York J. Math. 19 (2013), 713–727. [3] H.H. Bauschke, P.L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, Springer, New York-Dordrecht-Heidelberg-London, 2010. [4] H.H. Bauschke, S.M. Moffat, X. Wang, Firmly nonexpansive mappings and maximally monotone operators: correspondence and duality, Set-Valued Var. Anal. 20 (2012), 131–153. [5] M. Bridson, A. Haefliger, Metric Spaces of Non-Positive Curvature, Springer, Berlin-Heidelberg, 1999. [6] F.E. Browder, Convergence theorems for sequences of nonlinear operators in Banach spaces, Math. Z. 100 (1967), 201–225. [7] F.E. Browder, Convergence of approximants to fixed points of nonexpansive nonlinear mappings in Banach spaces, Arch. Rat. Mech. Anal. 24 (1967), 82–90. [8] F.E. Browder, W.V. Petryshyn, Construction of fixed points of nonlinear mappings in Hilbert spaces, J. Math. Anal. Appl. 20 (1967), 197–228. [9] R.E. Bruck, Nonexpansive projections on subsets of Banach spaces, Pacific J. Math. 47 (1973), 341–355. [10] P.L. Combettes, Fej´er monotonicity in convex optimization, in: C.A. Floudas, P.M. Pardalos (eds.), Encyclopedia of Optimization. Second edition, Springer, 2009, 1016–1024. [11] P.L. Combettes, Quasi-Fej´erian analysis of some optimization algorithms, in: D. Butnariu, Y. Censor, S. Reich (eds.), Inherently Parallel Algorithms for Feasibility and Optimization, Elsevier, 2001, 115–152. [12] Yu.M. Ermol´ev, A.D. Tuniev, Random Fej´er and quasi-Fej´er sequences, Theory of Optimal Solutions, Akademiya Nauk Ukrainskoi SSR Kiev 2 (1968) 76-83; translated in: American Mathematical Society Selected Translations in Mathematical Statistics and Probability 13 (1973), 143–148. [13] J. Garc´ıa-Falset, E. Llorens-Fuster, T. Suzuki, Fixed point theory for a class of generalized nonexpansive mappings, J. Math. Anal. Appl. 375 (2011), 185–195. 37 [14] P. Gerhardy, Proof mining in topological dynamics, Notre Dame J. Form. Log. 49 (2008), 431– 446. [15] P. Gerhardy, U. Kohlenbach, General logical metatheorems for functional analysis, Trans. Amer. Math. Soc. 360 (2008), 2615–2660. [16] K. Goebel, W.A. Kirk, A fixed point theorem for asymptotically nonexpansive mappings, Proc. Amer. Math. Soc. 35 (1972), 171–174. [17] K. Goebel, S. Reich, Uniform Convexity, Hyperbolic Geometry, and Nonexpansive Mappings, Marcel Dekker, New York-Basel, 1984. [18] C.W. Groetsch, A note on segmenting Mann iterates, J. Math. Anal. Appl. 40 (1972), 369–372. [19] D. G¨unzel, U. Kohlenbach, Logical metatheorems of abstract spaces axiomatized in positive bounded logic, Preprint 2015, submitted. [20] B. Halpern, Fixed points of nonexpanding maps, Bull. Amer. Math. Soc. 73 (1967), 957–961. [21] S. Ishikawa, Fixed points by a new iteration method, Proc. Amer. Math. Soc. 44 (1974), 147– 150. [22] D. Ivan, L. Leu¸stean, A rate of asymptotic regularity for the Mann iteration of κ-strict pseudocontractions, Numer. Funct. Anal. Optimiz. 36 (2015), 792-798. [23] U. Kohlenbach, Things that can and things that cannot be done in PRA, Ann. Pure Appl. Logic 102 (2000), 223–245. [24] U. Kohlenbach, Some computational aspects of metric fixed point theory, Nonlinear Anal. 61 (2005), 823–837. [25] U. Kohlenbach, Some logical metatheorems with applications in functional analysis, Trans. Amer. Math. Soc. 357 (2005), 89–128. [26] U. Kohlenbach, Applied Proof Theory: Proof Interpretations and their Use in Mathematics, Springer Monographs in Mathematics, Springer, Berlin, 2008. [27] U. Kohlenbach, On quantitative versions of theorems due to F.E. Browder and R. Wittmann, Adv. Math. 226 (2011), 2764–2795. [28] U. Kohlenbach, A uniform quantitative form of sequential weak compactness and Baillon’s nonlinear ergodic theorem, Commun. Contemp. Math. 14 (2012), 20pp. [29] U. Kohlenbach, On the quantitative asymptotic behavior of strongly nonexpansive mappings in Banach and geodesic spaces, Preprint 2015, submitted. [30] U. Kohlenbach, B. Lambov, Bounds on iterations of asymptotically quasi-nonexpansive mappings, in: J. Garcia Falset, E. Llorens Fuster, B. Sims (eds.), International Conference on Fixed Point Theory and Applications. Proceedings of the conference held in Valencia, July 13–19, 2003, Yokohama Publ., 2004, 143–172. [31] U. Kohlenbach, L. Leu¸stean, Asymptotically nonexpansive mappings in uniformly convex hyperbolic spaces, J. Eur. Math. Soc. 12 (2010), 71–92. [32] U. Kohlenbach, P. Safarik, Fluctuations, effective learnability and metastability in analysis, Ann. Pure Appl. Logic 165 (2014), 266–304. [33] E. Kopeck´a, S. Reich, Asymptotic behavior of resolvents of coaccretive operators in the Hilbert ball, Nonlinear Anal. 70 (2009), 3187–3194. [34] D. K¨ornlein, U. Kohlenbach, Rate of metastability for Bruck’s iteration of pseudocontractive mappings in Hilbert space, Numer. Funct. Anal. Optim. 35 (2014), 20–31. [35] M.A. Krasnoselski, Two remarks on the method of successive approximation, Uspekhi Mat. Nauk 10 (1955), 123–127 (in Russian). [36] L. Leu¸stean, Proof mining in R-trees and hyperbolic spaces, Electron. Notes Theor. Comput. Sci. 165 (2006), 95–106. 38 [37] L. Leu¸stean, A quadratic rate of asymptotic regularity for CAT(0)-spaces, J. Math. Anal. Appl. 325 (2007), 386–399. [38] L. Leu¸stean, Nonexpansive iterations in uniformly convex W-hyperbolic spaces, in: A. Leizarowitz, B.S. Mordukhovich, I. Shafrir, A. Zaslavski (eds.), Nonlinear Analysis and Optimization I: Nonlinear Analysis, Cont. Math. 513, Amer. Math. Soc., 2010, 193–209. [39] L. Leu¸stean, An application of proof mining to nonlinear iterations, Ann. Pure Appl. Logic 165 (2014), 1484–1500. [40] G.G. Lorentz, Metric entropy and approximation, Bull. Amer. Math. Soc. 72 (1966), 903–937. [41] W.R. Mann, Mean value methods in iteration, Proc. Amer. Math. Soc. 4 (1953), 506–510. [42] G. Marino, H.-K. Xu, Weak and strong convergence theorem for strict pseudo-contractions in Hilbert spaces, J. Math. Anal. Appl. 329 (2007), 336–346. [43] B. Martinet, R´egularisation din´equations variationnelles par approximations successives, Rev. Fran¸caise Informat. Recherche Op´erationnelle 4 (1970), 154–158. [44] G.J. Minty, Monotone (nonlinear) operators in Hilbert space, Duke Math. J. 29 (1962), 341-346. [45] E. Neumann, Computational problems in metric fixed point theory and their Weihrauch degrees., arXiv:1506.05127 [math.LO]; to appear in: Logical Methods in Computer Science. [46] A. Nicolae, Asymptotic behavior of averaged and firmly nonexpansive mappings in geodesic spaces, Nonlinear Anal. 87 (2013) 102–115. [47] S. Reich, I. Shafrir, The asymptotic behavior of firmly nonexpansive mappings, Proc. Amer. Math. Soc. 101 (1987), 246–250. [48] S. Reich, I. Shafrir, Nonexpansive iterations in hyperbolic spaces, Nonlinear Anal. 15 (1990), 537–558. [49] T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976), 877–898. [50] T. Suzuki, Fixed point theorems and convergence theorems for some generalized nonexpansive mappings, J. Math. Anal. Appl. 340 (2008), 1088–1095. [51] T. Tao, Soft analysis, hard analysis, and the finite convergence principle, Essay posted May 23, 2007, appeared in: T. Tao, Structure and Randomness: Pages from Year One of a Mathematical Blog., Amer. Math. Soc., Providence, RI , 2008. [52] T. Tao, Norm convergence of multiple ergodic averages for commuting transformations, Ergodic Theory Dynam. Systems 28 (2008), 657–688. [53] V.V. Vasin, I.I. Eremin, Operators and Iterative Processes of Fej´er Type. Theory and Applications, Walter de Gruyter, Berlin-New York, 2009. [54] M. Walsh, Norm convergence of nilpotent ergodic averages, Ann. Math. 175 (2012), 1667–1688. [55] R. Wittmann, Approximation of fixed points of nonexpansive mappings, Arch. Math. 58 (1992), 486–491. 39