Asymptotic behavior of averaged and firmly nonexpansive mappings in geodesic spaces

arXiv:1210.2105v2 [math.FA] 2 Oct 2013 Asymptotic behavior of averaged and firmly nonexpansive mappings in geodesic spaces Adriana Nicolae Simion Stoilow Institute of Mathematics of the Romanian Academy, P.O. Box 1-764, 014700 Bucharest, Romania Department of Mathematics, Babe¸s-Bolyai University, Kog˘alniceanu 1, 400084, Cluj-Napoca, Romania E-mail: adri[email protected] Abstract We further study averaged and firmly nonexpansive mappings in the setting of geodesic spaces with a main focus on the asymptotic behavior of their Picard iterates. We use methods of proof mining to obtain an explicit quantitative version of a generalization to geodesic spaces of a result on the asymptotic behavior of Picard iterates for firmly nonexpansive mappings proved by Reich and Shafrir. From this result we obtain effective uniform bounds on the asymptotic regularity for firmly nonexpansive mappings. Besides this, we derive effective rates of asymptotic regularity for sequences generated by two algorithms used in the study of the convex feasibility problem in a nonlinear setting. Keywords: averaged mapping; firmly nonexpansive mapping; convex feasibility problem; geodesic space; asymptotic regularity; proof mining. 1 Introduction In Banach spaces, firmly nonexpansive and averaged mappings form special classes of nonexpansive mappings which possess interesting properties that are not common to all nonexpansive mappings. This paper is mainly motivated by a very recent work by Ariza-Ruiz, Leu¸stean and L´opez-Acedo [1] where firmly nonexpansive mappings are defined and studied in suitable classes of geodesic spaces. Firmly nonexpansive mappings were introduced by Bruck [10] in the following way: let Cbe a nonempty closed and convex subset of a real Banach space X. A mapping T:C→Xis firmly nonexpansive if for each x, y ∈Cand t≥0, kT x −T yk ≤ kt(x−y) + (1 −t)(T x −T y)k. An important example of a firmly nonexpansive mapping is the metric projection onto a closed convex subset of a Hilbert space. Firmly nonexpansive self-mappings have notable properties when defined in Banach spaces. For instance, if a firmly nonexpansive mapping has fixed points, then it is asymptotically regular and, in more particular settings, the Picard iterates converge weakly to a fixed point of the mapping [51]. Such results find natural counterparts in the Hilbert ball [51, 49, 34]. In [1], firmly nonexpansive mappings are studied in geodesic spaces with emphasis on fixed point results, on the asymptotic behavior of Picard iterates for such mappings and on applications thereof. Averaged mappings already implicitly appeared in Krasnoselski’s work [35], while the term “averaged” was coined in [4]. Having a nonempty convex subset Cof a normed space X, an averaged mapping Tλ:C→C has the form Tλ= (1 −λ)I+λT , where λ∈(0,1), Iis the identity mapping and Tis nonexpansive. The metric projection onto a closed convex subset of a Hilbert space is averaged. In fact, in Hilbert spaces, a mapping is firmly nonexpansive if and only if it is averaged with λ= 1/2. A well-known result concerning averaged mappings was proved by Ishikawa in [26] and states that in any Banach space, Tλis asymptotically regular whenever it has bounded orbits. Ishikawa’s result has been extended by Goebel and Kirk in [22] to the setting of hyperbolic spaces. In particular Banach spaces, the Picard iterates of averaged mappings converge weakly to a fixed point of the mapping provided the mapping is not fixed point free. The asymptotic 1 behavior of averaged mappings has been further studied in the context of Banach spaces by Baillon, Bruck and Reich [4] and in the Hilbert ball by Reich [48]. Averaged mappings have remarkable applications. Many iterative algorithms used for instance in signal processing and image reconstruction employ averaged mappings for particular choices of the nonexpansive mapping T. In the setting of Hilbert and Banach spaces, such algorithms have been intensively studied in the past decades (for a unified treatment of some of these algorithms see, for instance, [13]). Our first main goal is to further study averaged and firmly nonexpansive mappings in geodesic spaces. To this end we apply methods of proof mining to give effective results on the asymptotic behavior of averaged and firmly nonexpansive mappings. Proof mining deals with the analysis of mathematical proofs with the goal of extracting additional information from them. By analyzing proofs using methods from logic, one may be able to strengthen conclusions of results mostly by obtaining effective bounds and uniformities in the bounds. More details about proof mining techniques can be found in [31]. Thus, in Section 3 we study a betweenness property of metric spaces which is useful for relating periodic and fixed points for firmly nonexpansive and averaged mappings. We provide significant examples of metric spaces that satisfy this property. In Section 4 we gather results on the asymptotic behavior of averaged mappings and provide a quantitative version of a generalization to geodesic spaces of a very important result due to Reich and Shafrir [51] on the asymptotic behavior of Picard iterates of firmly nonexpansive mappings. As an immediate consequence we obtain an exponential rate of asymptotic regularity for the Picard iterates. We remark that in [1] another rate of asymptotic regularity was established for UCW-hyperbolic spaces which, in particular, is quadratic in the case of CAT(0) spaces. However, our exponential rate is the only known rate which holds even in the setting of normed spaces. The second main goal of the paper is to derive effective rates of asymptotic regularity for sequences obtained by two methods used in the study of the convex feasibility problem in a nonlinear context. These two schemes are different forms of a very general method introduced by Bauschke and Borwein in [5] to provide a unified treatment of various methods used in the study of the convex feasibility problem. The convex feasibility problem consists in finding a point in the intersection of finitely many sets if such a point exists. The first algorithm that we focus on is the well-known alternating projection method developed by von Neumann [56] (see also [33] for an elementary geometric proof). This method was studied in the Hilbert ball by Reich [50] and was recently extended to the setting of CAT(0) spaces by Baˇc´ak, Searston and Sims [2]. In fact, one obtains linear convergence of this method even in a nonlinear setting if additional assumptions are imposed on the sets [6, 2]. In the general case when no further conditions are assumed on the sets one can only obtain weak convergence of the method [25, 38]. For this case we give here a quadratic rate of asymptotic regularity for the sequence generated by the alternating projection method. Additionally, we focus on a parallel projection scheme (see [14] for more references on parallel projection methods) defined in terms of weighted averages of nonexpansive retractions which extends a method studied in Hilbert spaces by Crombez [15] and later generalized by Takahashi and Tamura [55] in the setting of uniformly convex Banach spaces. We show that this method finds a natural counterpart in the geodesic setting and give a rate of asymptotic regularity for UCW-hyperbolic spaces. In the particular setting of CAT(0) spaces, this rate is quadratic and it is polynomial for Lpspaces with 1 < p < ∞. At the same time we prove the ∆-convergence of this method, showing that it can be used in a nonlinear setting. To our knowledge, the quantitative results that we obtain are new even in the Hilbert setting. 2 Basic notions on geodesic spaces Let (X, d) be a metric space. A geodesic path from xto yis a mapping c: [0, l]→X, where [0, l]⊆R, such that c(0) = x, c(l) = yand d(c(t), c(t′)) = |t−t′|for every t, t′∈[0, l]. The image c([0, l]) of cforms a geodesic segment which joins xand y. Note that a geodesic segment from xto yis not necessarily unique. If no confusion arises, we use [x, y] to denote a geodesic segment joining xand y. (X, d) is a (uniquely) geodesic space if every two points x, y ∈Xcan be joined by a (unique) geodesic path. A point z∈X belongs to the geodesic segment [x, y] if and only if there exists t∈[0,1] such that d(z, x) = td(x, y) and 2 d(z, y) = (1 −t)d(x, y), and we write z= (1 −t)x+ty for simplicity. This, too, may not be unique. A subset Cof Xis convex if Ccontains any geodesic segment that joins every two points in C. For a comprehensive treatment of geodesic metric spaces one may see for example [9, 39]. The metric d:X×X→Ris said to be convex if for any x, y, z ∈Xone has d(x, (1 −t)y+tz)≤(1 −t)d(x, y) + td(x, z) for all t∈[0,1]. A geodesic space (X, d) is Busemann convex if given any pair of geodesic paths c1: [0, l1]→Xand c2: [0, l2]→Xone has d(c1(tl1), c2(tl2)) ≤(1 −t)d(c1(0), c2(0)) + td(c1(l1), c2(l2)) for all t∈[0,1]. Any Busemann convex space has convex metric. W-hyperbolic spaces are defined in [31] using the notion of convexity mapping. The triple (X, d, W) is a W-hyperbolic space if (X, d) is a metric space and W:X×X×[0,1] →Xis a convexity mapping such that for each x, y, z, w ∈Xand for any t, t′∈[0,1] we have (W1) d(z, W(x, y, t)) ≤(1 −t)d(z, x) + td(z, y), (W2) d(W(x, y, t), W(x, y, t′)) = |t−t′|d(x, y), (W3) W(x, y, t) = W(y, x, 1−t), (W4) d(W(x, z, t), W(y, w, t)) ≤(1 −t)d(x, y) + td(z, w). Notice that hyperbolic spaces are defined in different ways in the literature (see, for instance, [22, 23, 52]). Any W-hyperbolic space is a geodesic space and it is uniquely geodesic if and only if for every x, y ∈X, x6=yand each λ∈(0,1) there exists a unique z∈X(namely z=W(x, y, λ)) such that d(x, z) = λd(x, y) and d(y, z) = (1 −λ)d(x, y). Note also that a metric space is Busemann convex if and only if it is a uniquely geodesic W-hyperbolic space (see [1] for details). Ageodesic triangle ∆(x1, x2, x3) consists of three points x1, x2and x3in X(its vertices) and three geodesic segments corresponding to each pair of points (its edges). For the geodesic triangle ∆=∆(x1, x2, x3), acomparison triangle is a triangle ¯ ∆ = ∆(¯x1,¯x2,¯x3) in R2such that d(xi, xj) = dR2(¯xi,¯xj) for i, j ∈ {1,2,3}. Comparison triangles of geodesic triangles always exist and are unique up to isometry. A geodesic triangle ∆ satisfies the CAT(0) inequality if for every comparison triangle ¯ ∆ of ∆ and for every x, y ∈∆ we have d(x, y)≤dR2(¯x, ¯y), where ¯x, ¯y∈¯ ∆ are the corresponding points of xand y, i.e., if x= (1 −t)xi+txjthen ¯x= (1 −t)¯xi+t¯xj. ACAT(0) space (also known as a space of bounded curvature in the sense of Gromov) is a geodesic space for which every geodesic triangle satisfies the CAT(0) inequality. CAT(0) spaces have attracted the attention of a large number of researchers in the last few decades due to their rich geometry and relevance in different problems. The fact that a CAT(0) space is Busemann convex has a great impact on the geometry of the space, but being Busemann convex is a weaker property than being CAT(0). The following inequality is called the (CN) inequality and is equivalent to the CAT(0) condition. Let x, y1, y2be points in a CAT(0) space and let m= (1 −t)y1+ty2for some t∈[0,1]. Then, d(x, m)2≤(1 −t)d(x, y1)2+td(x, y2)2−t(1 −t)d(y1, y2)2. A geodesic space (X, d) is uniformly convex [23, 52] if for any r > 0 and ε∈(0,2] there exists δ∈(0,1] such that if a, x, y ∈Xwith d(x, a)≤r,d(y, a)≤rand d(x, y)≥εr then d1 2x+1 2y, a≤(1 −δ)r. 3 A mapping δ: (0,∞)×(0,2] →(0,1] providing such a δ=δ(r, ε) for a given r > 0 and ε∈(0,2] is called a modulus of uniform convexity. The mapping δis monotone if for every fixed εit decreases with respect to r. CAT(0) spaces are uniformly convex metric spaces admitting a modulus of uniform convexity which does not depend on the radius of the balls. In fact, uniform convexity was defined in the setting of W-hyperbolic spaces in [36] similarly to above. Uniformly convex W-hyperbolic spaces with a monotone modulus of uniform convexity were called UCWhyperbolic spaces. However, any uniformly convex W-hyperbolic space is Busemann convex so UCWhyperbolic spaces form a particular class of uniformly convex metric spaces with a monotone modulus of uniform convexity. If we drop in the above definition the uniformity conditions then we find the notion of strict convexity in metric spaces. Consequently, every uniformly convex geodesic space is strictly convex. Moreover, any Busemann convex space is strictly convex. Note that strictly convex metric spaces are uniquely geodesic. 3 Relating periodic points to fixed points through a betweenness property In this section we focus on the relation between periodic and fixed points for averaged and firmly nonexpansive mappings. We recall first a betweenness property which plays an essential role in proving fixed point results for these two classes of mappings in geodesic spaces. We say that a point yin a metric space lies between two distinct points xand zif yis distinct from xand zand d(x, z) = d(x, y) + d(y, z). In geodesic spaces, the fact that ylies between xand zis equivalent to the fact that the three points are pairwise distinct and ybelongs to a geodesic segment joining xand z. In any metric space (X, d) we have the following transitivity property for betweenness which we call in this work the weak betweenness property (see [39, Proposition 2.2.13]): if x, y, z, w are pairwise distinct points in X, then ylies between xand zand zlies between xand wif and only if ylies between xand wand z lies between yand w. We say that Xsatisfies the betweenness property if for every four pairwise distinct points x, y, z, w ∈X, if ylies between xand zand zlies between yand w, then yand zlie between xand w. Note that the betweenness property induces the following property: for n≥2 and x0, x1,...,xn∈X, if xklies between xk−1and xk+1 for each 1 ≤k≤n−1, then xklies between x0and xk+1 for each 1 ≤k≤n−1. Let (X, d) be a geodesic space, C⊆Xnonempty and convex, λ∈(0,1) and T:C→Cnonexpansive. The mapping Tλ:C→Cdefined by Tλx= (1 −λ)x+λT x is called averaged . Note that xand T x must not be joined by a unique geodesic segment, Tλxbeing assumed to belong to one such fixed segment (more precisely one can consider a convexity mapping which assigns to each two points exactly one geodesic segment joining them). It is immediate that Tλand Thave the same fixed point set. Also, if Xis Busemann convex, then any averaged mapping is nonexpansive. In general, we have that d(T2 λx, Tλx)≤d(Tλx, x) for each x∈C. Indeed, d(T2 λx, Tλx) = d((1 −λ)Tλx+λT (Tλx), Tλx) =λd(Tλx, T (Tλx)) ≤λ(d(Tλx, T x) + d(T x, T (Tλx))) ≤λ(d(Tλx, T x) + d(x, Tλx)) = λd(x, T x) = d(Tλx, x). Let Xbe a metric space and C⊆X. Recall that a mapping T:C→Cis said to be asymptotically regular at x∈Cif lim n→∞ d(Tnx, T n+1x) = 0 and it is asymptotically regular if it is asymptotically regular at each x∈C. This concept was introduced by Browder and Petryshyn for normed spaces in [8]. More generally, we say that a sequence (xn)⊆Xis asymptotically regular if lim n→∞ d(xn, xn+1) = 0. A rate of convergence of (d(xn, xn+1)) towards 0 will be called a rate of asymptotic regularity. In the case of averaged mappings, it follows from [22, Proposition 2] proved by Goebel and Kirk that in any geodesic space with convex metric, if (Tn λx) is bounded, then Tλis asymptotically regular at x∈C. 4 Thus, in such a context any periodic point of an averaged mapping is a fixed point. We focus next on the relation between periodic and fixed points for averaged mappings in geodesic spaces with the betweenness property. Proposition 3.1. Let Xbe a geodesic space with the betweenness property, Ca nonempty and convex subset of X. Suppose Tλ:C→Cis an averaged mapping. Then any periodic point of Tλis a fixed point of Tλ. Proof. Suppose xis a periodic point which is not fixed and take m≥1 minimal such that x=Tm+1 λx. Then, d(x, T m λx) = d(Tm+1 λx, T m λx)≤d(Tm λx, T m−1 λx)≤...≤d(Tλx, x) =d(Tm+2 λx, T m+1 λx)≤d(Tm+1 λx, T m λx) = d(x, T m λx), which yields d(Tλx, x) = d(T2 λx, Tλx) = ...=d(Tm λx, T m−1 λx) = d(x, T m λx) = γ > 0. Since Tλis averaged, for every 1 ≤k≤mwe have γ=d(Tk+1 λx, T k λx) = λd Tk λx, T (Tk λx)≤λdTk λx, T (Tk−1 λx)+dT(Tk−1 λx), T (Tk λx) ≤λdTk λx, T (Tk−1 λx)+dTk−1 λx, T k λx=λd Tk−1 λx, T (Tk−1 λx)=d(Tk λx, T k−1 λx) = γ. Thus, for each 1 ≤k≤m,dTk λx, T (Tk λx)=dTk λx, T (Tk−1 λx)+dT(Tk−1 λx), T (Tk λx). If for some k, 1≤k≤m,T(Tk−1 λx) = Tk λxor T(Tk−1 λx) = T(Tk λx), then we obtain that γ= 0, a contradiction. Indeed, if T(Tk−1 λx) = Tk λx, then Tk−1 λx=Tk λx, so γ= 0. If T(Tk−1 λx) = T(Tk λx), then γ λ=dTk λx, T (Tk λx)=dTk λx, T (Tk−1 λx)= (1 −λ)dTk−1 λx, T (Tk−1 λx)=1−λ λγ, which implies that γ= 0. Therefore, for each 1 ≤k≤m,T(Tk−1 λx) lies between Tk λxand T(Tk λx). If m= 1 then k= 1 so T(Tk−1 λx) = T x lies between T(Tλx) and Tλx. Since Tλxlies between xand T x we have by the betweenness property that Tλxlies between T(Tλx) and x. Thus, d(x, T (Tλx)) = d(x, Tλx) + d(Tλx, T (Tλx)) . Since T2 λx=xthis yields that d(x, T (Tλx)) = d(x, Tλx) + d(x, Tλx) + d(x, T (Tλx)) , which is impossible. Suppose now m≥2. Since Tk λxlies between Tk−1 λxand T(Tk−1 λx) and T(Tk−1 λx) lies between Tk λxand T(Tk λx) we apply again the betweenness property to get that Tk λxlies between Tk−1 λxand T(Tk λx). Knowing that Tk+1 λxlies between Tk λxand T(Tk λx), by applying the weak betweenness property, we obtain that Tk λx lies between Tk−1 λxand Tk+1 λxfor all k= 1,...,m. Finally we obtain by the betweenness property that Tm−1 λxlies between xand Tm λx, so γ=d(x, T m λx) = d(Tm−1 λx, T m λx) + d(Tm−1 λx, x) = γ+d(Tm−1 λx, x)> γ, a contradiction. We focus next on the connection between periodic and fixed points for firmly nonexpansive mappings. Let (X, d) be a geodesic space, C⊆Xand T:C→X. For λ∈(0,1), we say that the mapping Tis λ-firmly nonexpansive if Tis nonexpansive and for all x, y ∈C, d(T x, T y)≤d((1 −λ)x+λT x, (1 −λ)y+λT y).(1) 5 Note that in the above definition if the space is not uniquely geodesic one should fix beforehand for each z∈Ca geodesic segment joining zand T z. If Tis λ-firmly nonexpansive for every λ∈(0,1), where the choice of segments joining zto T z for z∈C does not depend on λ, then Tis called firmly nonexpansive. Note that in general (1) does not necessarily imply nonexpansivity. However, condition (1) implies that d(T2x, T x)≤d(T x, x) for each x∈C. Indeed, d(T2x, T x)≤d((1 −λ)T x +λT 2x, (1 −λ)x+λT x) ≤d((1 −λ)T x +λT 2x, T x) + d(T x, (1 −λ)x+λT x) =λd(T2x, T x) + (1 −λ)d(T x, x). If the space is Busemann convex then nonexpansivity is guaranteed by (1). Besides, in the context of Busemann convex spaces, we have even more for firmly nonexpansive mappings. Let x, y ∈Cand ϕx,y : [0,1] →R+be defined by ϕx,y(λ) = d((1 −λ)x+λT x, (1 −λ)y+λT y). Then ϕx,y is a convex function and, since by (1) ϕx,y(1) ≤ϕx,y(λ) for every λ∈[0,1], we have that ϕx,y is non-increasing. In [1, Proposition 4.3] it was proved that in the context of Busemann convex spaces, any periodic point of a λ-firmly nonexpansive mapping is also fixed. However, this result is immediate since by [1, Corollary 5.3], we know that the mapping is asymptotically regular because the orbit of a periodic point is bounded. Hence any periodic point is fixed. Note that this reasoning can also be applied in geodesic spaces where the metric is convex since this setting is enough for [1, Corollary 5.3] to hold. In fact it can be proved that in any geodesic space with the betweenness property, any periodic point of a mapping satisfying (1) is fixed. We omit the details of the proof since it can be obtained by following an argument similar to that in [1]. Proposition 3.2. Let Xbe a geodesic space with the betweenness property, C⊆Xnonempty and T:C→C a mapping that satisfies (1) for some λ∈(0,1). Then any periodic point of Tis a fixed point of T. 3.1 Some examples of metric spaces with the betweenness property A metric space (X, d) is called a Ptolemy metric space if d(x, z)d(y, w)≤d(x, y)d(z, w) + d(x, w)d(y, z) for every x, y, z, w ∈X. The above relation is known as the Ptolemy inequality. This inequality is significant in both the normed and the metric setting. It is known that a normed space is an inner product space if and only if it is a Ptolemy space [54]. CAT(0) spaces are Ptolemy spaces, but geodesic Ptolemy spaces are not necessarily CAT(0) [20]. The Ptolemy inequality proved to play an essential role in, for instance, the study of the boundary at infinity of CAT(−1) spaces [21]. Proposition 3.3. Every Ptolemy metric space satisfies the betweenness property. Proof. Let x, y, z, w be four pairwise distinct points in a Ptolemy metric space such that yis between xand zand zis between yand w. By the Ptolemy inequality we have d(x, z)d(y, w)≤d(x, y)d(z, w) + d(x, w)d(y, z). Thus, (d(x, y) + d(y, z)) (d(y, z) + d(z, w)) ≤d(x, y)d(z, w) + d(x, w)d(y, z), that is, d(x, y)d(y, z) + d(x, y)d(z, w) + d(y, z)2+d(y, z)d(z, w)≤d(x, y)d(z, w) + d(x, w)d(y, z), 6 so, d(x, y) + d(y, z) + d(z, w)≤d(x, w). From this we have on the one hand that d(x, z) + d(z, w) = d(x, w) and on the other that d(x, y) + d(y, w) = d(x, w). This means that yand zboth lie between xand w. The betweenness property holds in Busemann convex spaces (see [39, Proposition 8.2.4]). Note that geodesic Ptolemy spaces are not necessarily Busemann convex. In fact they are not even uniquely geodesic (see [20]) which shows that in the context of geodesic spaces, the betweenness property does not yield the uniqueness of geodesic segments. However, Busemann convexity implies the CAT(0) condition in the setting of Ptolemy spaces [20]. Other properties of geodesic Ptolemy spaces in connection to metric fixed point theory can be found in [18, 19]. We see below that the betweenness property holds in the more general context of geodesic spaces with convex metric. Proposition 3.4. Every geodesic space with convex metric satisfies the betweenness property. Proof. Let x, y, z, w be four pairwise distinct points such that yis between xand zand zis between yand w. Suppose z= (1 −r)y+rw, where r∈(0,1). Then, d(x, z)≤(1 −r)d(x, y) + rd(x, w), from where rd(x, w)≥d(x, z)−d(x, y) + rd(x, y) = d(y, z) + rd(x, y) = rd(y, w) + rd(x, y). Hence, d(x, y) + d(y, w)≤d(x, w), which implies that ylies between xand w. But then, d(x, w) = d(x, y) + d(y, w) = d(x, y) + d(y, z) + d(z, w) = d(x, z) + d(z, w), which yields that zalso lies between xand w. Let κ∈R. CAT(κ) spaces are defined in terms of comparisons with the model spaces M2 κsimilarly to CAT(0) spaces. We denote the diameter of M2 κby Dκ. More precisely, for κ > 0, Dκ=π/√κand for κ≤0, Dκ=∞. In any CAT(κ) space Xhaving x0∈X, the restriction of x7→ d(x, x0) to the open ball centered at x0and of radius Dκ/2 is convex. Therefore, on sets of diameter less than Dκ/2 the betweenness property is satisfied. For more details about these spaces and related topics one can consult Bridson and Haefliger [9]. We recall next some notions needed below. A geodesic path c: [0, l]→Xis extendable beyond the point c(l) if cis a restriction of a geodesic path c′: [0, l′]→Xwith l′> l. We say that two geodesics bifurcate if they have a common endpoint and coincide on an interval, but one is not an extension of the other. Alexandrov spaces of curvature bounded below cannot have bifurcating geodesics. We refer the reader to the paper of Burago, Gromov and Perelman [12] and to Plaut [42] for a detailed discussion on the geometry of Alexandrov spaces. Proposition 3.5. Let Xbe a geodesic space without bifurcating geodesics and assume that every geodesic path is extendable. Then Xsatisfies the betweenness property. Proof. Let x, y, z, w ∈Xbe pairwise distinct such that yis between xand zand zis between yand w. Denote by [x, z] a geodesic segment that joins xand zand contains yand by [y, w] a geodesic segment joining yand wand containing z. Since Xhas no bifurcating geodesics it follows that yand zare joined by a unique geodesic segment. Consider z′∈[z, w]⊆[y, w] such that d(x, z) + d(z, z′) = d(x, z′) and d(z, z′)∈[0, d(z, w)] is maximal. Suppose d(z, z′)< d(z, w). Let c: [0, l]→Xbe the geodesic path whose image is [x, z]∪[z, z′] with c(l) = z′. Then there exist ε > 0 and a geodesic path c′: [0, l +ε]→Xsuch that c′|[0,l]=c. Pick 0 < δ < min{ε, d(z′, w)}and zδ∈[z′, w] for which d(z′, zδ) = δ. Because the space has no bifurcating geodesics we have that [y, zδ] and c′([d(x, y), l +δ]) coincide and zδ=c′(l+δ), which contradicts the maximality of z′. Hence z′=wand we are done. Corollary 3.6. Every Alexandrov space of curvature bounded below for which all geodesic paths are extendable satisfies the betweenness property. 7 4 Effective results on the asymptotic behavior of Picard iterates 4.1 Averaged mappings In this section we gather some facts on averaged mappings in the context of geodesic spaces. We study next the asymptotic behavior of Picard iterates for averaged mappings in geodesic spaces giving analogues of the results obtained in Banach spaces by Baillon, Bruck and Reich [4] and in the Hilbert ball by Reich [48]. Lemma 4.1. Let Xbe a geodesic space with convex metric and C⊆Xnonempty and convex. Suppose that Tλ:C→Cis averaged. Then, for every x, y ∈C, d(Tλx, Tλy)≤(1 −λ)d(Tλx, y) + λ(1 −λ)d(x, Tλy) + (1 −λ)2d(y, Tλy) + λ2d(x, y). Proof. Let x, y ∈C. Then, d(Tλx, Tλy) = d(Tλx, (1 −λ)y+λT y)≤(1 −λ)d(Tλx, y) + λd(Tλx, T y) = (1 −λ)d(Tλx, y) + λd((1 −λ)x+λT x, T y) ≤(1 −λ)d(Tλx, y) + λ(1 −λ)d(x, T y) + λ2d(T x, T y) ≤(1 −λ)d(Tλx, y) + λ(1 −λ)d(x, Tλy) + λ(1 −λ)d(Tλy, T y) + λ2d(x, y) = (1 −λ)d(Tλx, y) + λ(1 −λ)d(x, Tλy) + (1 −λ)2d(y, Tλy) + λ2d(x, y). We already know by [22, Proposition 2] that if (Tn λx) is bounded then it is asymptotically regular at x∈C. Moreover, if Tλis also nonexpansive, then all orbits will be bounded and so Tλwill be asymptotically regular. Additionally, we have the following. Theorem 4.2. Let Xbe a geodesic space with convex metric and C⊆Xnonempty and convex. Suppose that Tλ:C→Cis averaged and nonexpansive. Then for every x∈Cand k∈N, lim n→∞ d(Tn+1 λx, T n λx) = 1 klim n→∞ d(Tn+k λx, T n λx) = lim n→∞ d(Tn λx, x) n=rC(Tλ), where rC(T) = inf{d(x, T x) : x∈C}is the minimal displacement of T. Proof. The result can be proved by applying Lemma 4.1 and [1, Lemma 5.4] using reasoning similar to that adopted in the case of firmly nonexpansive mappings which was discussed in [1]. A slightly different proof can be obtained by an immediate adaptation of the proof given in [48] for the Hilbert ball. The above result shows that if Tλis asymptotically regular at some point x∈Cthen Tλis asymptotically regular which in turn is equivalent to rC(Tλ) = 0. In Banach spaces, conditions for the convergence of the sequence (Tnx/n) when the mapping Tis nonexpansive are discussed in [40, 43, 44, 29, 45, 46, 41]. We focus next on rates of asymptotic regularity for averaged mappings. Let C⊆Xbe a nonempty and convex subset of a geodesic space and T:C→Cbe nonexpansive. The Krasnoselski iteration [35, 53] (xn) starting at x∈Cis defined as in the case of normed spaces by x0:= x, xn+1 := (1 −λ)xn+λT xn, where λ∈(0,1). Note that the Picard iteration (Tn λx) of the averaged mapping Tλ:C→C,Tλ(x) = (1 −λ)x+λT x is in fact the Krasnoselski iteration starting at x∈Cand dTn λx, T n+1 λx=λd (Tn λx, T (Tn λx)) = λd(xn, T xn). 8 This means that asymptotic regularity of the mapping Tλis equivalent to the fact that for each starting point x∈C, limn→∞ d(xn, T xn) = 0. Hence, the study of a rate of asymptotic regularity for the averaged mapping Tλreduces to computing a rate of asymptotic regularity for the Krasnoselski iteration of the nonexpansive mapping T. In the case of normed spaces, a uniform and quadratic rate was established by Baillon and Bruck in [3] using a difficult computer aided proof. Afterwards, for the case λ= 1/2 a simple proof was given in [11]. Rates of asymptotic regularity for the more general Krasnoselski-Mann iteration were computed using methods of proof mining in the setting of normed spaces by Kohlenbach [30] and in the setting of hyperbolic spaces by Kohlenbach and Leu¸stean [32] by analyzing a result of Borwein, Reich and Shafrir [7]. Although the main result in [32] was proved in hyperbolic spaces in the sense of [52], the proof goes through for the setting of geodesic spaces with convex metric. We include below a rate of asymptotic regularity for averaged mappings in geodesic spaces with convex metric which is an immediate consequence of [32, Corollary 3.18]. This rate only depends on ε, on an upper bound bon the diameter of the set Cand on λ. Theorem 4.3. Let (X, d)be a geodesic space with convex metric, C⊆Xnonempty convex and bounded with diameter dC≤b. Suppose Tλ:C→Cis averaged. Then, ∀x∈C, ∀ε > 0,∀n≥Φ(ε, b, λ), d Tn λx, T n+1 λx≤ε, where Φ(ε, b, λ) := KM l2beK(M+1)m, with K= max 1 λ,1 1−λ, M =λ(1 + 2b) ε. The above rate is exponential in 1/ε. Rates of asymptotic regularity for the Krasnoselski-Mann iteration were further studied in particular hyperbolic spaces (namely in UCW-hyperbolic spaces) by Leu¸stean [36]. Note that instead of UCW -hyperbolic spaces one can also consider the more general context of uniformly convex geodesic spaces with convex metric that admit a monotone modulus of uniform convexity since the proof carries over to this setting with no changes. In particular, the results proved in [36] guarantee a quadratic rate of asymptotic regularity (in 1/ε) for CAT(0) spaces which again only depends on ε, on an upper bound bon the diameter of the set Cand on λ. 4.2 Firmly nonexpansive mappings In this section we mainly focus on providing a rate of asymptotic regularity for firmly nonexpansive mappings in the setting of geodesic spaces with convex metric. Let (X, d) be a W-hyperbolic space, C⊆Xnonempty and suppose T:C→Cis λ-firmly nonexpansive. It was proved in [1] that for every x∈C, lim n→∞ dTnx, T n+1x=rC(T). In fact, this holds in the context of geodesic spaces with convex metric. This property is the counterpart in the geodesic setting of a very important result given by Reich and Shafrir [51] in Banach spaces. Using methods of proof mining, we give in the sequel a quantitative version of this result. Theorem 4.4. Let (X, d)be a geodesic space with convex metric, C⊆Xnonempty and T:C→C λ-firmly nonexpansive. Let x, y ∈Cand b≥max{d(x, y), d(x, T x)}. Then, ∀ε > 0,∀n≥Φ(ε, b, λ), d(Tnx, T n+1x)≤d(y, T y) + ε, where Φ(ε, b, λ) := M2b(1 + eKM ) ε,(2) 9 Remark 5.5. If, in addition, we have that δ(r, ε)≥ε·˜ δ(r, ε)such that ˜ δincreases with respect to εfor r fixed, then Φ(ε, b, δ, λ, α)can be replaced for ε < 2bwith ˜ Φ(ε, b, δ, λ, α) = b 2εK˜ δ(b, ε/b). Proof. Define rn:= d(Tnx, p) and N:= b 2εK˜ δ(b, ε/b). Like before, we have that d(Ti(Tnx), p)≤(1 −2λi(1 −λi)δ(rn, ε/rn)) rn≤rn−2rnλi(1 −λi)δ(b, ε/rn) =rn−2ελi(1 −λi)˜ δ(b, ε/rn)≤rn−2ελi(1 −λi)˜ δ(b, ε/b). The conclusion follows using the same reasoning as above. Since any CAT(0) space is a UCW-hyperbolic space for which δ(r, ε) = ε2/8 is a modulus of uniform convexity we obtain in this case a quadratic rate of asymptotic regularity in 1/ε: for ε < 2b, ˜ Φ(ε, b, λ, α) = 4b2 ε2K. Let (Ω,Σ, µ) be a measure space. Recall that for 1 < p < ∞,Lp(µ) is uniformly convex and (see, for instance, [24]), for ε∈[0,2], the modulus of uniform convexity is bounded by δLp(ε)≥     p−1 8ε2for 1 < p ≤2, 1 p2pεpfor 2 < p < ∞. Thus, for ε < 2b, we obtain the following expression for the rate of asymptotic regularity ˜ Φ(ε, b, λ, α) =      4b2 ε2K(p−1) for 1 < p ≤2, p2p−1bp εpKfor 2 < p < ∞. 5.1 ∆-convergence of the method In the sequel we briefly discuss the weak convergence of the above algorithm. More precisely, we generalize to a nonlinear setting weak convergence results proved by Crombez [15] in Hilbert spaces and Takahashi and Tamura [55] in uniformly convex Banach spaces (see also [47]). First we need to recall a concept of weak convergence in metric spaces. Let (X, d) be a metric space and (xn) a bounded sequence in X. The asymptotic radius of (xn) is given by r((xn)) = inf lim sup n→∞ d(x, xn) : x∈X, and the asymptotic center of (xn) is the possibly empty set A((xn)) = x∈X: lim sup n→∞ d(x, xn) = r((xn)). Note that an element of A((xn)) will also be referred to as an asymptotic center. In any complete uniformly convex metric space with a monotone modulus of uniform convexity, every bounded sequence has a unique asymptotic center [17]. 16 We give next a concept of convergence in metric spaces known as ∆-convergence which was introduced by Lim in [37] and further studied by Kirk and Panyanak in [28] where it was shown that in CAT(0) spaces this concept is somewhat similar to that of weak convergence in Banach spaces. Another concept involves projections on geodesic segments and was given by Jost [27]. This notion proved to be equivalent to ∆- convergence in the framework of CAT(0) spaces [16]. A bounded sequence (xn) in a metric space Xis said to ∆-converge to x∈Xif xis the unique asymptotic center of (un) for every subsequence (un) of (xn). Consider now the mapping Tas defined by (7). We adapt next to the setting of CAT(0) spaces a method studied by Crombez [15] in Hilbert spaces. Corollary 5.6. Let Xbe a complete CAT(0) space and for i= 2,...,r let Ci⊆Xbe nonempty closed and convex sets with r \ i=2 Ci6=∅. Define T1:X→X,T1:= Iand for i= 2,...,r,Ti:X→Xby Ti:= (1 −λi)I+λiPi, where λi∈(0,1) and Piis the metric projection of Xonto Ci. Then, for all x∈X, the Picard iterate (Tnx) ∆-converges to an element of r \ i=2 Ci. Proof. Since Tis in this case averaged and nonexpansive, and, by Lemma 5.3, Fix(T)6=∅, we know that T is asymptotically regular. Apply [1, Proposition 6.3] to obtain the conclusion. More generally, we have the following extension of [55, Theorem 3.3] in the geodesic setting. Corollary 5.7. Let Xbe a complete UCW-hyperbolic space and C⊆Xnonempty closed and convex. For i= 1,...,r, let Ci⊆Cwith r \ i=1 Ci6=∅and Pi:C→Cibe nonexpansive retractions. Define Ti:C→C by Ti= (1 −λi)I+λiPi, where λi∈(0,1),i= 1,...,r. Then, for all x∈X, the Picard iterate (Tnx) ∆-converges to an element of r \ i=1 Ci. Proof. Since by Theorem 5.4 it follows that Tis asymptotically regular, we only need to apply [1, Proposition 6.3] to obtain the conclusion. Acknowledgements I would like to thank Laurent¸iu Leu¸stean for fruitful discussions on this topic. This research was supported by a grant of the Romanian National Authority for Scientific Research, CNCS UEFISCDI, project number PN-II-ID-PCE-2011-3-0383. References [1] D. Ariza-Ruiz, L. Leu¸stean, G. L´opez-Acedo, Firmly nonexpansive mappings in classes of geodesic spaces, Trans. Amer. Math. Soc. (in press). [2] M. Baˇc´ak, I. Searston, B. Sims, Alternating projections in CAT(0) spaces, J. Math. Anal. Appl. 385 (2012), 599-607. [3] J. Baillon, R.E. Bruck, The rate of asymptotic regularity is O(1/√n), in: A.G. Kartsatos (Ed.), Theory and applications of nonlinear operators of accretive and monotone type, Lecture Notes in Pure and Appl. Math. 178, Dekker, New York, 1996, pp. 51-81. [4] J.B. Baillon, R.E. Bruck, S. Reich, On the asymptotic behavior of nonexpansive mappings and semigroups in Banach spaces, Houston J. Math. 4 (1978), 1-9. 17 [5] H.H. Bauschke, J.M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Review 38 (1996), 367-426. [6] H.H. Bauschke, J.M. Borwein, On the convergence of von Neumann’s alternating projection algorithm for two sets, Set-Valued Analysis 1 (1993), 185-212. [7] J. Borwein, S. Reich, I. Shafrir, Krasnoselski-Mann iterations in normed spaces, Canad. Math. Bull. 35 (1992), 21-28. [8] F.E. Browder, W.V. Petryshyn, The solution by iteration of nonlinear functional equations in Banach spaces, Bull. Amer. Math. Soc. 72 (1966), 571-575. [9] M.R. Bridson, A. Haefliger, Metric spaces of non-positive curvature, Springer-Verlag, Berlin, 1999. [10] R.E. Bruck, Nonexpansive projections on subsets of Banach spaces, Pacific J. Math. 47 (1973), 341-355. [11] R.E. Bruck, A simple proof that the rate of asymptotic regularity of (I+T)/2 is O(1/√n), in: T. Dom´ınguez Benavides (Ed.), Recent advances on metric fixed point theory, Ciencias 48, Univ. Sevilla, 1996, pp. 11-18. [12] Y. Burago, M. Gromov, G. Perelman, A. D. Alexandrov spaces with curvature bounded below, Russian Mathematical Surveys 47 (1992), 1-58. [13] C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Problems 20 (2004), 103-120. [14] P.L. Combettes, Hilbertian convex feasibility problem: convergence of projection methods, Appl. Math. Optim. 35 (1997), 311-330. [15] G. Crombez, Image recovery by convex combinations of projections, J. Math. Anal. Appl. 155 (1991), 413-419. [16] R. Esp´ınola, A. Fern´andez-Le´on, CAT(κ)-spaces, weak convergence and fixed points, J. Math. Anal. Appl. 353 (2009), 410-427. [17] R. Esp´ınola, A. Fern´andez-Le´on, B. Pi¸atek, Fixed points of singleand set-valued mappings in uniformly convex metric spaces with no metric convexity, Fixed Point Theory Appl. 2010 (2010), Article ID 169837 16 pages. [18] R. Esp´ınola, A. Nicolae, Geodesic Ptolemy spaces and fixed points, Nonlinear Anal. 74 (2011), 27-34. [19] R. Esp´ınola, A. Nicolae, Uniform convexity of geodesic Ptolemy spaces, J. Convex Anal. (in press). [20] T. Foertsch, A. Lytchak, V. Schroeder, Nonpositive curvature and the Ptolemy inequality, Int. Math. Res. Not. IMRN 2007 (2007), Article ID rnm100, 15 pages. [21] T. Foertsch, V. Schroeder, Hyperbolicity, CAT(-1)-spaces and the Ptolemy inequality, Math. Annalen 350 (2011), 339-356. [22] K. Goebel, W.A. Kirk, Iteration processes for nonexpansive mappings, Contemp. Math. 21 (1983), 115-123. [23] K. Goebel, S. Reich, Uniform convexity, hyperbolic geometry, and nonexpansive mappings, Marcel Dekker, Inc., New York and Basel, 1984. [24] O. Hanner, On the uniform convexity of Lpand lp, Ark. Mat. 3 (1956), 239-244. [25] H.S. Hundal, An alternating projection that does not converge in norm, Nonlinear Anal. 57 (2004), 35-61. 18 [26] S. Ishikawa, Fixed Points and Iteration of a Nonexpansive Mapping in a Banach Space, Proc. Amer. Math. Soc. 59 (1976), 65-71. [27] J. Jost, Equilibrium maps between metric spaces, Calc. Var. Partial Diff. Equations 2 (1994), 173-204. [28] W.A. Kirk, B. Panyanak, A concept of convergence in geodesic spaces, Nonlinear Anal. 68 (2008), 3689-3696. [29] E. Kohlberg, A. Neyman, Asymptotic behavior of nonexpansive mappings in normed linear spaces, Israel J. Math. 38 (1981), 269-275. [30] U. Kohlenbach, A quantitative version of a theorem due to Borwein-Reich-Shafrir, Numer. Funct. Anal. Optim. 22 (2001), 641-656. [31] U. Kohlenbach, Applied proof theory: Proof interpretations and their use in mathematics, Springer Monographs in Mathematics, Springer-Verlag, Berlin-Heidelberg, 2008. [32] U. Kohlenbach, L. Leu¸stean, Mann iterates of directionally nonexpansive mappings in hyperbolic spaces, Abstr. Appl. Anal. 2003 (2003), 449-477. [33] E. Kopeck´a, S. Reich, A note on the von Neumann alternating projections algorithm, J. Nonlinear Convex Anal. 5 (2004), 379-386. [34] E. Kopeck´a, S. Reich, Asymptotic behavior of resolvents of coaccretive operators in the Hilbert ball, Nonlinear Anal. 70 (2009), 3187-3194. [35] M.A. Krasnoselski, Two remarks on the method of successive approximation, Usp. Math. Nauk (N.S.) 10 (1955), 123-127 (in Russian). [36] L. Leu¸stean, A quadratic rate of asymptotic regularity for CAT(0) spaces, J. Math. Anal. Appl. 325 (2007), 386-399. [37] T.C. Lim, Remarks on some fixed point theorems, Proc. Amer. Math. Soc. 60 (1976), 179-182. [38] E. Matouˇskov´a, S. Reich, The Hundal example revisited, J. Nonlinear Convex Anal. 4 (2003), 411-427. [39] A. Papadopoulos, Metric Spaces, Convexity and Nonpositive Curvature, European Math. Soc., Z¨urich, 2005. [40] A. Pazy, Asymptotic behavior of contractions in Hilbert space, Israel J. Math. 9 (1971), 235-240. [41] A.T. Plant, S. Reich, The asymptotics of nonexpansive iterations, J. Funct. Anal. 54 (1983), 308-319. [42] C. Plaut, Metric spaces of curvature ≥k, in: R.J. Daverman, R.B. Sher (Eds.), Handbook of geometric topology, North-Holland, Amsterdam, 2002, pp 819-898. [43] S. Reich, Asymptotic behavior of contractions in Banach spaces, J. Math. Anal. Appl. 44 (1973), 57-70. [44] S. Reich, A solution to a problem on the asymptotic behavior of nonexpansive mappings and semigroups, Proc. Japan Acad. Ser. A Math. Sci. 56 (1980), 85-87. [45] S. Reich, On the asymptotic behavior of nonlinear semigroups and the range of accretive operators, J. Math. Anal. Appl. 79 (1981), 113-126. [46] S. Reich, On the asymptotic behavior of nonlinear semigroups and the range of accretive operators II, J. Math. Anal. Appl. 87 (1982), 134-146. [47] S. Reich, A limit theorem for projections, Linear Multilinear Algebra 13 (1983), 281-290. 19 [48] S. Reich, Averaged mappings in the Hilbert ball, J. Math. Anal. Appl. 109 (1985), 199-206. [49] S. Reich, Fixed point theory in the Hilbert ball, Contemp. Math. 72 (1988), 225-232. [50] S. Reich, The alternating algorithm of von Neumann in the Hilbert ball, Dynam. Systems Appl. 2 (1993), 21-25. [51] S. Reich, I. Shafrir, The asymptotic behavior of firmly nonexpansive mappings, Proc. Amer. Math. Soc. 101 (1987), 246-250. [52] S. Reich, I. Shafrir, Nonexpansive iterations in hyperbolic spaces, Nonlinear Anal. 15 (1990), 537-558. [53] H. Schaefer, ¨ Uber die Methode sukzessiver Approximationen, Jber. Deutsch. Math. Verein 59 (1957), 131-140. [54] I.J. Schoenberg, A remark on M.M. Day’s characterization of inner-product spaces and a conjecture of L.M. Blumenthal, Proc. Amer. Math. Soc. 3 (1952), 961-964. [55] W. Takahashi, T. Tamura, Image recovery by convex combinations of nonexpansive retractions in Banach spaces, RIMS Kˆokyˆuroku 939 (1996), 198-207. [56] J. von Neumann, Functional Operators, Vol. II. The Geometry of Orthogonal Spaces, Princeton University Press, Princeton, NJ, 1950. Ann. Math. Stud., Vol. 22. Reprint of mimeographed lecture notes first distributed in 1933. 20