Effective results on compositions of nonexpansive mappings

Effective results on compositions of nonexpansive mappings Laurent¸iu Leu¸stean1, Adriana Nicolae2,3 1Simion Stoilow Institute of Mathematics of the Romanian Academy, Research unit 5, P. O. Box 1-764, RO-014700 Bucharest, Romania 2Department of Mathematics, Babe¸s-Bolyai University, Kog˘alniceanu 1, 400084 Cluj-Napoca, Romania 3Simion Stoilow Institute of Mathematics of the Romanian Academy, Research group of the project PD-3-0152, P. O. Box 1-764, RO-014700 Bucharest, Romania E-mails: Lauren[email protected], [email protected]cluj.ro September 17, 2013 Abstract This paper provides uniform bounds on the asymptotic regularity for iterations associated to a finite family of nonexpansive mappings. We obtain our quantitative results in the setting of (r, δ)-convex spaces, a class of geodesic spaces which generalizes metric spaces with a convex geodesic bicombing. MSC: 47J25; 47H09; 53C23; 03F10. Keywords: Effective rates of asymptotic regularity; Proof mining; Families of nonexpansive mappings; Halpern iteration; Convex geodesic bicombing. 1 Introduction Let Xbe a Hilbert space, C⊆Xa closed convex subset, T1, . . . , TN:C→C (where N∈Z+) a finite family of nonexpansive mappings and (λn) a sequence in [0,1]. Given u∈C, one can define an iteration starting from uby x0=u, xn+1 =λn+1u+ (1 −λn+1)Tn+1xn,(1) where Tn=Tnmod Nand the mod Nfunction takes values in 1, . . . , N. For the special case N= 1, this iteration coincides with the well-known Halpern iteration [8], whose strong convergence was proved by Wittmann [22] under 1 arXiv:1306.5307v2 [math.FA] 14 Sep 2013 suitable conditions on (λn), which are satisfied by the natural candidate λn= 1 n+1 . The general iteration defined by (1) was first studied in Hilbert spaces by Lions [18], who assumed different hypotheses on (λn), with the drawback that λn=1 n+1 does not satisfy them. Bauschke [2] proved that the iteration (xn) given by (1) converges strongly to the common fixed point of the mappings T1, . . . , TNwhich is nearest to u, under the assumptions that F:= N \ i=1 Fix(Ti) is nonempty, F= Fix(TNTN−1···T1) = . . . = Fix(T1TN···T2) = Fix(TN−1···T1TN) and that (λn) satisfies lim n→∞ λn= 0, ∞ X n=1 |λn+N−λn|<∞and ∞ X n=1 λn=∞.(2) Bauschke’s result is a generalization of Wittmanns’s theorem to a finite family of mappings, since for N= 1 conditions (2) coincide with the ones used by Wittmann. Another iteration that will be considered in this paper is the following one associated to any nonexpansive mapping T:C→C, xn+1 =T(λn+1u+ (1 −λn+1)xn).(3) This iteration, studied by Xu [23], is a discrete version of the approximating curve zt=T(tu + (1 −t)zt), t ∈(0,1), analyzed by Combettes and Hirstoaga [7]. Strong convergence of the iteration (3) was established by Xu in the setting of uniformly smooth Banach spaces under appropriate assumptions on (λn), including those given by (2). The strong convergence results of Xu and Combettes and Hirstoaga were extended in [6] to more general approximating curves and iterations. As above, one can define for the iteration (3) a cyclic algorithm associated to the finite family of nonexpansive mappings T1, . . . , TN:C→C, x0=u, xn+1 =Tn+1(λn+1u+ (1 −λn+1)xn).(4) A very important concept in the study of the asymptotic behavior of nonlinear iterations is the so-called asymptotic regularity, introduced by Browder and Petryshyn [4] in their study of solutions of nonlinear functional equations using Picard iterations: T:C→Cis asymptotically regular if lim n→∞ kTnx−Tn+1xk= 0 for all x∈C. More generally, an iteration (xn) associated to a mapping Tis said to be asymptotically regular if lim n→∞ kxn−Txnk= 0 for all starting points in C. A natural question is to compute rates of asymptotic regularity for the iteration (xn), i.e. rates of convergence of (kxn−Txnk) towards 0. For the Halpern iteration this was done in a series of papers [15,16,13,14,17], corresponding to different classes of spaces. For the iteration given by (3), such rates were obtained in [6]. 2 The notion of asymptotic regularity can be extended to sequences (xn) associated to a family of mappings T1, . . . , TN:C→C, as it is the case in this paper. Thus, we say that (xn) is asymptotically regular if lim n→∞ kxn− Tn+N···Tn+1xnk= 0 for all starting points in C. The following asymptotic regularity result is contained in Bauschke’s strong convergence proof for the iteration (1). Theorem 1.1. Let Xbe a Hilbert space, C⊆Xconvex, T1, . . . , TN:C→C nonexpansive mappings and (λn)a sequence in [0,1] satisfying (2). Let (xn)be given by (1)and assume that (xn)is bounded. Then, lim n→∞ kxn−Tn+N···Tn+1xnk= 0. The main result of this paper is a quantitative version of Theorem 1.1 for both iterations (1) and (4). In order to get this result we apply methods of proof mining developed by Kohlenbach [12] with the aim of obtaining effective and uniform bounds from proofs where such information is not readily available. As a consequence, we provide for the first time effective and uniform rates of asymptotic regularity for the iterations (1) and (4). Actually, we obtain our quantitative results in a setting more general than the one of normed space. More precisely, we introduce (r, δ)-convex spaces, a class of metric spaces which also includes Busemann spaces (and, hence, CAT(0) spaces), hyperconvex spaces, CAT(κ) spaces with κ > 0, as well as the so-called W-hyperbolic spaces (see [11]). Consequently, even when N= 1 and so (1) reduces in fact to the Halpern iteration, our results generalize ones obtained previously by the authors for CAT(κ) spaces with κ > 0 [17] and by the first author for normed [15] or W-hyperbolic spaces [16]. 2(r, δ)-convex spaces Let (X, d) be a metric space. We recall first basic facts in geodesic geometry. Given x, y ∈X, a constant speed geodesic from xto yis a mapping γ: [0,1] →X such that γ(0) = x,γ(1) = yand d(γ(s), γ(t)) = |s−t|d(x, y) for all s, t ∈[0,1]. The image γ([0,1]) of γis a geodesic segment which joins xand y. Note that a geodesic segment from xto yis not necessarily unique. Given r∈(0,∞], we say that (X, d) is a (uniquely) r-geodesic space if every two points x, y ∈Xwith d(x, y)≤rcan be joined by a (unique) geodesic segment. For r=∞, we say simply that Xis a (uniquely) geodesic space. Let r∈(0,∞] and Xbe an r-geodesic space. We consider an r-geodesic bicombing Γ on X, that is, a choice of a constant speed geodesic γx,y joining x and yfor each pair of points x, y ∈Xwith d(x, y)≤r. When r=∞, Γ is called a geodesic bicombing on X. If Xis uniquely r-geodesic, then clearly one can define an r-geodesic bicombing in a unique way. For γx,y ∈Γ, we denote by [x, y] the geodesic segment γx,y([0,1]). A subset Cof Xis r-convex if [x, y]∈Cfor all x, y ∈Cwith d(x, y)≤r. Given t∈[0,1], we use the notation (1 −t)x+ty for 3 γx,y(t). Then, d(x, (1−t)x+ty) = td(x, y) and d(y, (1−t)x+ty) = (1−t)d(x, y). The r-geodesic bicombing is convex if it satisfies d((1 −t)x+ty, (1 −t)x+tz)≤td(y, z) (5) for all x, y, z ∈Xwith d(x, y), d(x, z), d(z, y)≤rand all t∈[0,1]. Normed spaces are obviously geodesic spaces with a convex geodesic bicombing. Another natural example are Busemann spaces, which were used for the first time by Busemann [5] to give a definition of nonpositive curvature in geodesic spaces. Thus, geodesic spaces with the property that each point has a convex neighborhood which is a Busemann space are ‘nonpositively curved’ spaces in the sense of Busemann, who called them G-spaces. We refer to [20] for a nice exposition of this very important class of geodesic spaces. It turns out that Busemann spaces are uniquely geodesic spaces with a (unique) convex geodesic bicombing. A related example of metric spaces with a convex geodesic bicombing are the so-called W-hyperbolic spaces, defined in [11] as metric spaces together with a convexity mapping W:X×X×[0,1] →Xsatisfying suitable properties. As it was remarked in [1], Busemann spaces are exactly the uniquely geodesic W-hyperbolic spaces. It is well-known that a hyperconvex space Xalso admits a convex geodesic bicombing obtained by embedding Xisometrically into `∞(X) and using the existence of a nonexpansive retraction from `∞(X) into Xto define the geodesic bicombing through the convex linear geodesic bicombing on `∞(X) (for more details see, for instance, Chapter 13 in [10]). In the following we define a natural generalization of metric spaces with a convex r-geodesic bicombing. Definition 2.1. Let r∈(0,∞]and δ∈[0,1]. A metric space (X, d)with an r-geodesic bicombing is said to be (r, δ)-convex if for all x, y, z ∈Xwith d(x, y), d(x, z), d(z, y)≤rand all t∈[0,1], d((1 −t)x+ty, (1 −t)x+tz)≤(t+δ(1 −t))d(y, z). If r=∞, we say that Xis δ-convex. An example of such spaces are CAT(κ) spaces with κ > 0. CAT(κ) spaces are defined in terms of comparisons with the model spaces M2 κ(see [3] for more details). Denote Dκ=π/√κ. Proposition 2.2. A CAT(κ)space Xis µDκ 2,1−cos µπ 2-convex for any µ∈(0,1]. Proof. Let x, y, z ∈Xwith d(x, y), d(x, z), d(z, y)≤µDκ 2and t∈[0,1]. By [21, Lemma 3.3] (see also [17, Lemma 4.1]) we have that d((1−t)x+ty, (1−t)x+tz)≤ 4 sin tµπ 2 sin µπ 2 d(y, z).Note that 1−sin tµπ 2 sin µπ 2 =2 cos (1+t)µπ 4sin (1−t)µπ 4 sin µπ 2≥2 cos µπ 2sin (1−t)µπ 4 sin µπ 2 ≥(1 −t) cos µπ 2,since sin (1 −t)µπ 4≥1−t 2sin µπ 2. Hence, sin tµπ 2 sin µπ 2≤1−(1 −t) cos µπ 2=t+1−cos µπ 2(1 −t). We point out that CAT(κ) spaces with κ > 0 do not have in general a convex r-geodesic bicombing for r < Dκ(to see this it suffices to consider the spherical space S2). Let us recall another notion of convexity for metric spaces, introduced by Ohta [19]. Given L1, L2∈[0,∞), a geodesic space Xis said to be L-convex for (L1, L2) if for any x, y, z ∈X, any constant speed geodesics γ, ξ : [0,1] →X with γ(0) = ξ(0) = x,γ(1) = y,ξ(1) = zand for every t∈[0,1], d(γ(t), ξ(t)) ≤1 + L1 min{d(x, y) + d(x, z),2L2} 2td(y, z). An additional related notion says that an r-geodesic bicombing on a metric space Xis weakly convex if there exists a constant C≥1 such that d((1 −t)x+ty, (1 −t)x+tz)≤Ctd(y, z), for all t∈[0,1] and all x, y, z ∈Xas in Definition 2.1. One can easily see that an L-convex space for (L1, L2) has a weakly convex r-geodesic bicombing, where r∈(0,∞] and C:= 1 + L1min{r, L2}. Remark 2.3. We remark that we could have defined an even more general notion: given r > 0and η: [0,1] →[0,∞), a metric space with an r-geodesic bicombing is (r, η)-convex if d((1 −t)x+ty, (1 −t)x+tz)≤(t+η(t))d(y, z), for all t∈[0,1] and all x, y, z ∈Xas in Definition 2.1. This very general definition has the advantage that it covers the case of metric spaces with a weakly convex r-geodesic bicombing and, thus, of L-convex spaces. However, we use in this paper Definition 2.1, as this is the notion which allows us to get the effective results from the next section. 5 3 Effective rates of asymptotic regularity Let r∈(0,∞], δ ∈[0,1), Xbe an (r, δ)-convex space, C⊆Xa convex subset and T1, . . . , TN:C→Cbe nonexpansive mappings, where N∈Z+. If (λn) is a sequence in [0,1] and u∈C, one can, obviously, define the iterations (1) and (4) starting with uin this setting, too: x0=u, xn+1 =λn+1u+ (1 −λn+1)Tn+1xn,(6) x0=u, xn+1 =Tn+1(λn+1u+ (1 −λn+1)xn),(7) where Tn=Tnmod Nand the mod Nfunction takes values in 1, . . . , N. We use the following notation Tn,N := Tn+N···Tn+1. The main theorem of the paper is a quantitative result on the asymptotic regularity of the above iterations. Theorem 3.1. Let ε > 0,M > 0be such that M≤r 2,α, γ : (0,∞)→Z+and θ:Z+→Z+. Suppose that (i) ∞ X n=1 λn=∞with rate of divergence θ; (ii) ∞ X n=1 |λn+N−λn|converges with Cauchy modulus γ. Let ˜ Φ(ε, M, γ, θ, δ) = θ 1 1−δγε 4M+ max ln 4M ε,1, Φ(ε, M, γ, θ, δ, N, α) = max n˜ Φε 2, M, γ, θ, δ, α ε 4MN o. Assume either (i) (xn)is given by (6)with d(xn, u)≤Mfor all n≥1and d(u, Tiu)≤M for each i= 1, . . . , N, or (ii) (xn)is given by (7)with d(xn, u)≤Mfor all n≥1. Then lim n→∞ d(xn, xn+N)=0with rate of convergence ˜ Φ. Furthermore, if lim n→∞ λn+1 = 0 with rate of convergence α, then lim n→∞ d(xn, Tn,N (xn)) = 0 with rate of convergence Φ. We give the proof of the theorem in the next section. Let us state now some immediate consequences. Corollary 3.2. Let ε, M, (λn), α, γ, θ, ˜ Φ,Φbe as above. Assume moreover that Cis bounded and Mis an upper bound on its diameter. If (xn)is given by either (6)or (7), then lim n→∞ d(xn, xn+N)=0with rate of convergence ˜ Φand lim n→∞ d(xn, Tn,N (xn)) = 0 with rate of convergence Φ. 6 Thus, for Cbounded we obtain a highly uniform rate of asymptotic regularity Φ which does not depend at all on the starting point uand the nonexpansive mappings T1, . . . , TN. Moreover, the dependence on the set Cand the space X is very weak: via δand a bound M≤r 2on the diameter of C. Corollary 3.3. Suppose that λn=1 n+ 1, n ≥1. Then lim n→∞ d(xn, xn+N) = lim n→∞ d(xn, Tn,N (xn)) = 0 with a common rate of convergence Ψ(ε, M, N, δ) = exp  1 1−δ8M(N+ 1) ε+ 2ln 4. Proof. We can take θ(n) = exp(nln 4), γ(ε) = N εand α(ε) = 1 ε. As mentioned before, in the case N= 1, the iterative scheme defined by (6) yields the usual Halpern iteration, for which rates of asymptotic regularity have already been computed in the setting of CAT(κ) spaces [17]. Our main theorem recovers (with a slightly modified rate) [17, Proposition 3.2] since, for M < Dκ 2, one takes µ=2M Dk in Proposition 2.2 to get that any CAT(κ) space is (M, 1−cos(M√κ))-convex and then apply Corollary 3.2. Furthermore, we generalize with basically the same bounds the results obtained for the Halpern iteration in normed spaces [15] and, more general, W-hyperbolic spaces [16]. As we have already pointed out, in this paper we obtain for the first time, even for Banach spaces, effective bounds on the asymptotic regularity of the iterations (6) and (7). Recently, using proof mining methods as well, Khan and Kohlenbach [9] obtained in the setting of uniformly convex Busemann spaces effective results on the asymptotic behavior of a different iteration associated to a finite family of nonexpansive mappings which extends the Krasnoselski-Mann iteration of a single nonexpansive mapping. 4 Proof of the main result Assume the hypothesis of Theorem 3.1. As in the case of the Halpern iteration associated to a single mapping [15,16,14,17], we shall apply the following quantitative lemma. Lemma 4.1. [17,14] Let (αn)n≥1be a sequence in [0,1] and (an)n≥1,(bn)n≥1 be sequences in R+such that an+1 ≤(1 −αn+1)an+bnfor all n∈Z+.(8) Assume that ∞ X n=1 bnis convergent with Cauchy modulus γand ∞ X n=1 αn+1 diverges with rate of divergence θ. 7 Then, lim n→∞ an= 0 with rate of convergence Σgiven by Σ(ε, P, γ, θ) = θγε 2+ max ln 2P ε,1+ 1 (9) where P > 0is an upper bound on (an). The next lemma is the second main tool for the proof of our main result. Lemma 4.2. Let M > 0satisfy 2M≤r. (i) Assume that (xn)is given by (6),d(u, Tiu)≤Mfor each i= 1, . . . , N and d(xn, u)≤Mfor all n∈N. Then, for all n≥1, d(xn+1, Tn+1xn)≤2Mλn+1, d(xn, xn+N)≤(1 −(1 −δ)λn)d(xn−1, xn+N−1)+2M|λn+N−λn|. (ii) Assume that (xn)is given by (7)and d(xn, u)≤Mfor all n∈N. Then, for all n≥1, d(xn+1, Tn+1xn)≤Mλn+1, d(xn, xn+N)≤(1 −(1 −δ)λn)d(xn−1, xn+N−1) + M|λn+N−λn|. Proof. (i) First, let us note that d(u, Tnxm)≤2Mfor all m, n ≥1. It follows that for all n≥1, d(xn+1, Tn+1xn) = λn+1d(u, Tn+1xn)≤2Mλn+1 and d(xn, xn+N) = d(λnu+ (1 −λn)Tnxn−1, λn+Nu+ (1 −λn+N)Tnxn+N−1) ≤d(λnu+ (1 −λn)Tnxn−1, λnu+ (1 −λn)Tnxn+N−1) +d(λnu+ (1 −λn)Tnxn+N−1, λn+Nu+ (1 −λn+N)Tnxn+N−1) ≤(1 −(1 −δ)λn)d(xn−1, xn+N−1)+2M|λn+N−λn|. (ii) The proof is similar, using that d(xn+1, Tn+1xn)≤d(λn+1u+ (1 −λn+1)xn, xn)≤Mλn+1 and d(xn, xn+N) = d(Tn(λnu+ (1 −λn)xn−1), Tn(λn+Nu+ (1 −λn+N)xn+N−1)) ≤d(λnu+ (1 −λn)xn−1, λn+Nu+ (1 −λn+N)xn+N−1). for all n≥1. 8 4.1 Proof of Theorem 3.1 Let (xn) be given by either (6) or (7). Denote tn+1 = (1 −δ)λn∈[0,1]. As an immediate consequence of Lemma 4.2, we get that d(xn, xn+N)≤(1 −tn+1)d(xn−1, xn+N−1)+2M|λn+N−λn|. Note that ∞ X n=1 2M|λn+N−λn|converges with Cauchy modulus ˜γ(ε) = γε 2M and ∞ X n=1 tn+1 =∞with rate of divergence ˜ θ(n) = θ 1 1−δn. We apply Lemma 4.1 with αn:= tn,P:= 2M,an:= d(xn−1, xn+N−1) and bn:= 2M|λn+N−λn|to obtain that lim n→∞ d(xn−1, xn+N−1) = 0 with rate of convergence ˜ Φ + 1. Hence, lim n→∞ d(xn, xn+N) = 0 with rate of convergence ˜ Φ. Assume now that lim n→∞ λn+1 = 0 with rate of convergence α. By Lemma 4.2, it follows that d(xn+1, Tn+1(xn)) ≤2Mλn+1, hence d(xn+1, Tn+1(xn)) ≤ε 2Nfor all n≥αε 4MN . One can easily see that d(xn, Tn,N (xn)) ≤d(xn, xn+N) + N X i=1 d(xn+i, Tn+i(xn+i−1)). Therefore, d(xn, Tn,N (xn)) ≤εfor all n≥Φ.  Acknowledgements: 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. L´opez, Firmly nonexpansive mappings in classes of geodesic spaces, arXiv:1203.1432v3 [math.FA], accepted for publication in Trans. Amer. Math. Soc., 2012. [2] H.H. Bauschke, The approximation of fixed points of compositions of nonexpansive mappings in Hilbert spaces, J. Math. Anal. Appl. 202 (1996), 150-159. [3] M. Bridson, A. Haefliger, Metric spaces of non-positive curvature, Springer- Verlag, Berlin, 1999. 9