BRICS RS-02-28 Kohlenbach & Leuştean: Mann Iterates in Hyperbolic Spaces BRICS

Basic Research in Computer Science

Mann Iterates of Directionally Nonexpansive Mappings in Hyperbolic Spaces

Ulrich Kohlenbach Laurenţiu Leuştean

BRICS Report Series RS-02-28 ISSN 0909-0878 June 2002 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2002, Ulrich Kohlenbach & Laurenţiu Leuştean.

BRICS, Department of Computer Science University of Aarhus. All rights reserved.

Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy.

See back inner page for a list of recent BRICS Report Series publications. Copies may be obtained by contacting:

BRICS Department of Computer Science University of Aarhus Ny Munkegade, building 540 DK–8000 Aarhus C Denmark

Telephone: +45 8942 3360
Telefax: +45 8942 3255
Internet: BRICS@brics.dk

BRICS publications are in general accessible through the World Wide Web and anonymous FTP through these URLs:

http://www.brics.dk
ftp://ftp.brics.dk

This document in subdirectory RS/02/28/

Mann iterates of directionally nonexpansive mappings in hyperbolic spaces

Ulrich Kohlenbach ^{∗} and Laurenţiu Leuştean ^{∗∗}

∗ BRICS^{∗}

Department of Computer Science, University of Aarhus,

Ny Munkegade, DK-8000 Aarhus C, Denmark.

E-mail: kohlenb@brics.dk

∗∗ National Institute for Research and Development in Informatics,

8-10 Averescu Avenue, 71316, Bucharest, 1, Romania,

E-mail: leo@u3.ici.ro

Key words: Krasnoselski-Mann iterations, directionally nonexpansive mappings, nonexpansive mappings, hyperbolic spaces, fixed point theory, asymptotic regularity, proof mining. Mathematics Subject Classification: 47H09, 47H10, 03F10, 03F60

Abstract

In a previous paper, the first author derived an explicit quantitative version of a theorem due to Borwein, Reich and Shafrir on the asymptotic behaviour of Mann iterations of nonexpansive mappings of convex sets C in normed linear spaces. This quantitative version, which was obtained by a logical analysis of the ineffective proof given by Borwein, Reich and Shafrir, could be used to obtain strong uniform bounds on the asymptotic regularity of such iterations in the case of bounded C and even weaker conditions. In this paper we extend these results to hyperbolic spaces and directionally nonexpansive mappings. In particular, we obtain significantly stronger and more general forms of the main results of a recent paper by W.A. Kirk with explicit bounds. As a special feature of our approach, which is based on logical analysis instead of functional analysis, no functional analytic embeddings are needed to obtain our uniformity results which contain all previously known results of this kind as special cases.

∗Basic Research in Computer Science, funded by the Danish National Research Foundation.

1 Introduction

This paper continuous the approach of applying logic to metric fixed point theory started by the first author in [12],[13],[14]. In particular, the last two papers were concerned with explicit bounds on the asymptotic behaviour of so-called Mann iterations of nonexpansive mappings in the following setting: Let (X, ∥ · ∥) be a normed linear space, C ⊆ X convex and f : C → C nonexpansive, i.e.

∀x, y ∈ C(∥f(x) − f(y)∥ ≤ ∥x − y∥).

Let (λ_{n})_{n∈IN} be a sequence of real numbers in [0, 1). Then Mann iteration starting from x_{0} := x ∈ C is defined as^{1}

x_{n+1} := (1 − λ_{n})x_{n} + λ_{n}f(x_{n}).

In [2], the following important result is proved: If (λ_{n})_{n∈IN} is divergent in sum and is bounded away from 1 then

∀x ∈ C(∥x_{n} − f(x_{n})∥ → r_{C}(f)),

where r_{C}(f) := inf{∥x − f(x)∥ | x ∈ C}. In many cases, e.g. for bounded C, r_{C}(f) can be shown to be 0, i.e ∥x_{n} − f(x_{n})∥ → 0 which (for bounded C) was first proved by Ishikawa in the classical paper [6]. The special case of constant λ_{k} = λ also follows from [3] which even proves uniform (in x) convergence. Later, [4] extended this to uniformity in both x and f. Using specially designed techniques from mathematical logic the first author established in a series of papers general theorems on the extractability of explicit bounds from large classes of prima-facie ineffective existence proofs together with procedures to transform such proofs into new ones from which these bounds can be read off (see [9],[10] and, in particular, [11]). The proof given by Borwein, Reich and Shafrir in [2] of the result just cited happens to be of the required form. In [13], as a result of the logical transformation of the proof, a new quantitative version of the Borwein-Reich-Shafrir theorem was obtained. From this version, explicit uniform bounds for the case of bounded C could simply be read off. These bounds only depend on the error ε, an upper bound for the diameter of C, a distance by which (λ_{n}) stays away from 1 and a rate of divergence of the sum of that sequence towards infinity. Subsequently ([14]), this could be extended to the case where not C as a whole is required to be bounded but only some Mann iteration sequence. The logical approach does not use any tools from functional analysis to establish these uniformity results which suggests that it should be possible to generalize the results to other settings in which the basic proof idea of the Borwein-Reich-Shafrir theorem applies. In this paper we show that, indeed, all results from [13] (as well as the one from [14] just mentioned) extend to the more general class of hyperbolic spaces (in the sense of [16]) and (with minor changes in the assumptions) to the more general class of directionally nonexpansive mappings (in the sense of [8]). In particular, we prove significantly stronger forms of the main results in [8]. Although some of the proofs follow closely those in [13] we include them in this paper for completeness.

1The special case of λ_{n} := \frac{1}{2} was already considered by Krasnoselski in [15].

2 Hyperbolic spaces-basic results

In this section we present hyperbolic spaces, defined by Reich and Shafrir [16] as an appropriate context for the study of operator theory in general, and of iterative processes for nonexpansive mappings in particular. This class of metric spaces includes all normed linear spaces and Hadamard manifolds, as well as the Hilbert ball equipped with the hyperbolic metric [7] and the Cartesian products of Hilbert balls. Extensive information on hyperbolic spaces and a detailed treatment of examples like the Hilbert ball can be found in [5] (see also [4, 7] and [17]).

A still more general class of metric spaces is the class of spaces of hyperbolic type (see [4, 7]), also called convex metric spaces ([18]). In particular, every hyperbolic space is a space of hyperbolic type.

In the following we collect some basic facts on hyperbolic spaces which we will need later. To make the paper self-contained we include the (short) proofs. Let (X, ρ) be a metric space and let IR denote the real line. We say that a mapping c : IR → X is a metric embedding of IR into X if

ρ(c(s), c(t)) = |s − t|

for all real s and t. The image of IR under a metric embedding will be called a metric line. Any isometry c : IR → X is a metric embedding and the metric line associated with it is X. In fact, a metric embedding is an isometry iff it is surjective. The image c([a, b]) ⊆ X of a real interval under a metric embedding c : IR → X will be called a metric segment. Let x, y ∈ X and c : IR → X a metric embedding. We say that the metric line c(IR) passes through x and y if x, y ∈ c(IR) and that the metric segment c([a, b]) joins x and y if (c(a) = x and c(b) = y) or (c(a) = y and c(b) = x).

In the sequel, we shall assume that (X, ρ) contains a non-empty family M of metric lines such that for each pair of distinct points x and y in X there is a unique metric line which passes through x and y. Hence, there is a nonempty family {c_{i}}_{i∈I} of metric embeddings such that for all x ≠ y ∈ X there is a unique i ∈ I such that x, y ∈ c_{i}(IR).

Remark 2.1 Since M ≠ ∅, there is at least one metric embedding c : IR → X. Since c is injective, it follows that card(X) ≥ card(IR) = ℵ_{1}.

The following lemmas collect some simple facts. For the sake of completeness, we shall prove them.

Lemma 2.2 For any x ∈ X there is at least one metric line from M that passes through x.

Proof: By the above remark, X is infinite, so there is y ∈ X, y ≠ x. Take now the unique metric line that passes through x and y. □

Lemma 2.3 For any distinct points x and y in X there is a unique metric segment joining them.

Proof: There is a unique i ∈ I such that x, y ∈ c_{i}(IR). Since c_{i} is injective, there are unique a, b ∈ IR, a ≠ b such that c_{i}(a) = x and c_{i}(b) = y. Hence, the unique metric segment joining x and y is c_{i}([a, b]) if a < b or c_{i}([b, a]) if b < a. □

We shall denote by [x, y] or [y, x] the unique metric segment joining two distinct points x and y from X. For any x ∈ X, by [x, x] we shall understand the singleton {x}. By Lemma 2.2, there is c : IR → X and a ∈ IR such that c(a) = x, hence {x} = c([a, a]). Thus, [x, x] is a degenerate metric segment.

Lemma 2.4 Let x, y ∈ X, x ≠ y and z, w ∈ [x, y]. Then

(i) 0 ≤ ρ(x, z) ≤ ρ(x, y); (ii) if ρ(x, z) = ρ(x, w), then z = w.

Proof: Let [x, y] = c([a, b]).

(i) Let s ∈ [a, b] such that c(s) = z. If c(a) = x and c(b) = y, then ρ(x, z) = ρ(c(a), c(s)) = |s − a| = s − a ≤ b − a = ρ(x, y). If c(a) = y and c(b) = x, then ρ(x, z) = ρ(c(b), c(s)) = |b − s| = b − s ≤ b − a = ρ(x, y). (ii) Since z, w ∈ [x, y], there are s_{1}, s_{2} ∈ [a, b]. such that c(s_{1}) = z and c(s_{2}) = w. Let us suppose that c(a) = x and c(b) = y. It follows that ρ(x, z) = ρ(c(a), c(s_{1})) = |a − s_{1}| = s_{1} − a and, similarly, ρ(x, w) = s_{2} − a. Thus, ρ(x, z) = ρ(x, w) iff s_{1} − a = s_{2} − a iff s_{1} = s_{2} iff z = w. □

Lemma 2.5 Let c : IR → X be a metric embedding, a ≤ b ∈ IR and t ∈ [0, 1]. Then

\begin{matrix}ρ(c(a), c((1 − t)a + tb)) = tρ(c(a), c(b)) and \\ ρ(c(b), c((1 − t)a + tb)) = (1 − t)ρ(c(a), c(b)). \end{matrix}

Proof: ρ(c(a), c((1−t)a+tb)) = |a−((1−t)a+tb)| = t|a−b| = tρ(c(a), c(b)) and, similarly, ρ(c(b), c((1 − t)a + tb)) = |b − ((1 − t)a + tb)| = (1 − t)|a − b| = (1 − t)ρ(c(a), c(b)). □

Proposition 2.6 Let x, y ∈ X. For each t ∈ [0, 1] there is a unique point z ∈ [x, y] such that

(1) ρ(x, z) = tρ(x, y) and ρ(y, z) = (1 − t)ρ(x, y).

Proof: If x = y, then, obviously, z = x = y. Suppose that x ≠ y. Let [x, y] = c([a, b]). If c(a) = x and c(b) = y, then take z = c((1 − t)a + tb). If c(b) = x and c(a) = y, then take z = c((1 − t)b + ta). Then z ∈ [x, y] and z satisfies (1), by Lemma 2.5. Unicity of z follows from Lemma 2.4(ii). □

The unique point satisfying (1) will be denoted (1 − t)x ⊕ ty. Then, for any x ∈ X and t ∈ [0, 1], (1 − t)x ⊕ tx = x. If z ∈ [x, y] satisfies only one of the conditions (1), then it is necessary that z = (1 − t)x ⊕ ty. Hence, any point of the segment [x, y] satisfying one of the conditions (1), satisfies also the other.

Remark 2.7 Let x, y ∈ X, x ≠ y and s, t ∈ [0, 1]. Then

(i) (1 − t)x ⊕ ty = (1 − s)x ⊕ sy iff s = t; (ii) (1 − t)x ⊕ ty = ty ⊕ (1 − t)x.

Lemma 2.8 Let x, y ∈ X, x ≠ y. Then

(i) [x, y] = {(1 − t)x ⊕ ty | t ∈ [0, 1]}; (ii) the mapping f : [0, 1] → [x, y], f(t) = (1 − t)x ⊕ ty is continuous and bijective; (iii) ρ(x, z) + ρ(z, y) = ρ(x, y) for all z ∈ [x, y]; (iv) if z ≠ w ∈ X are such that ρ(x, y) ≤ ρ(z, w), then there is a unique v ∈ [z, w] such that ρ(z, v) = ρ(x, y).

Proof: (i) ⊇ By definition. ⊆ Let z ∈ [x, y] and t = ρ(x, z)/ρ(x, y). Then, by Lemma 2.4(i), t ∈ [0, 1] and ρ(x, z) = tρ(x, y). It follows that z = (1 − t)x ⊕ ty. (ii) Applying (i) and Remark 2.7(i), we get immediately that f is well-defined and bijective. Let c([a, b]) = [x, y]. Then for all t ∈ [0, 1], f(t) = c((1 − t)a + tb). Since c is continuous and the map [0, 1] → [a, b], t ↦ (1 − t)a + tb is also continuous, it follows that f is continuous. (iii) Let z ∈ [x, y]. By (i), there is t ∈ [0, 1] such that z = (1 − t)x ⊕ ty, hence ρ(x, z) + ρ(z, y) = tρ(x, y) + (1 − t)ρ(x, y) = ρ(x, y).

(iv) Let t = ρ(x, y)/ρ(z, w), so t ∈ [0, 1]. Let v = (1 − t)z ⊕ tw. Then v ∈ [z, w] and ρ(z, v) = tρ(z, w) = ρ(x, y). □

Definition 2.9 ([16]) We say that (X, ρ, M) is a hyperbolic space if

(2) ρ(\frac{1}{2}x ⊕ \frac{1}{2}y, \frac{1}{2}x ⊕ \frac{1}{2}z) ≤ \frac{1}{2}ρ(y, z)

for all x, y, z ∈ X.

Remark 2.10 ([16]) (2) is equivalent to

(2′) ρ(\frac{1}{2}x ⊕ \frac{1}{2}y, \frac{1}{2}w ⊕ \frac{1}{2}z) ≤ \frac{1}{2}(ρ(x, w) + ρ(y, z))

for all x, y, z, w ∈ X.

Proof: (2′) ⇒ (2) is obvious, take w = x. It remains to prove (2) ⇒ (2′). For any x, y, z, w ∈ X,

\begin{aligned}ρ(\frac{1}{2}x ⊕ \frac{1}{2}y, \frac{1}{2}w ⊕ \frac{1}{2}z) & ≤ & ρ(\frac{1}{2}x ⊕ \frac{1}{2}y, \frac{1}{2}x ⊕ \frac{1}{2}z) + ρ(\frac{1}{2}x ⊕ \frac{1}{2}z, \frac{1}{2}w ⊕ \frac{1}{2}z) \\ & ≤ & \frac{1}{2}(ρ(y, z) + ρ(x, w)). \end{aligned}

□ Let (X, ρ, M) be a hyperbolic space. A non-empty subset C ⊆ X is convex if [x, y] ∈ C for all x, y ∈ C. We shall denote by d(C) the diameter of C. Hence,

d(C) = sup{ρ(x, y) | x, y ∈ C}.

The set C is bounded if d(C) < ∞. A sequence (x_{n})_{n∈IN} ⊆ X is bounded if the set {x_{n} | n ∈ IN} is bounded.

At a few places we will use the following fact

Proposition 2.11 ([5, 16]) Let (X, ρ, M) be a hyperbolic space. Then

(3) ρ((1 − t)x ⊕ tz, (1 − t)y ⊕ tw) ≤ (1 − t)ρ(x, y) + tρ(z, w)

for all t ∈ [0, 1] and x, y, z, w ∈ X.

Proof: The idea of the proof is presented in [5, pp. 77, 104]. We first prove the result for t = \frac{k}{2^{n}}, where k, n ∈ IN are such that k ≤ 2^{n}. We use induction on n. If n = 0, then \frac{k}{2^{n}} = k and k ∈ \{0, 1\}. If k = 0, then (3) ⇔ (ρ(1x ⊕ 0z, 1y ⊕ 0w) ≤ ρ(x, y)) ⇔ (ρ(x, y) ≤ ρ(x, y)). If k = 1, then (3) ⇔ (ρ(0x ⊕ 1z, 0y ⊕ 1w) ≤ ρ(z, w)) ⇔ (ρ(z, w) ≤ ρ(z, w)). Hence, (3) is true even with equality. Suppose now that (3) is true for t = \frac{k}{2^{n}}. Hence,

(∗) ρ((1 − \frac{k}{2^{n}})x ⊕ \frac{k}{2^{n}} z, (1 − \frac{k}{2^{n}})y ⊕ \frac{k}{2^{n}} w) ≤ (1 − \frac{k}{2^{n}})ρ(x, y) + \frac{k}{2^{n}} ρ(z, w)

for all k ∈ IN, k ≤ 2^{n} and for all x, y, z, w ∈ X. We have to prove (3) for t = \frac{k}{2^{n+1}} , where k ∈ IN, k ≤ 2^{n+1}. If we denote u := (1 − \frac{k}{2^{n+1}} )x ⊕ \frac{k}{2^{n+1}} z and v := (1 − \frac{k}{2^{n+1}} )y ⊕ \frac{k}{2^{n+1}} w, then we have to prove

(∗∗) ρ(u, v) ≤ (1 − \frac{k}{2^{n+1}} )ρ(x, y) + \frac{k}{2^{n+1}} ρ(z, w).

First, let us show (**) for k ≤ 2^{n}, that is \frac{k}{2^{n}} ∈ [0, 1]. Let α := (1− \frac{k}{2^{n}})x⊕ \frac{k}{2^{n}} z, β := (1 − \frac{k}{2^{n}})y ⊕ \frac{k}{2^{n}} w, α_{1} := \frac{1}{2}x ⊕ \frac{1}{2}α and β_{1} := \frac{1}{2}y ⊕ \frac{1}{2}β. Then ρ(x, α_{1}) = \frac{1}{2}ρ(x, α) = \frac{k}{2^{n+1}} ρ(x, z) = ρ(x, u) and α_{1}, u ∈ [x, z], since u, α ∈ [x, z] and α_{1} ∈ [x, α]. Applying Lemma 2.4(ii), it follows that u = α_{1}. We get similarly that v = β_{1}. Applying now (2′) and the induction hypothesis, it follows that

ρ(u, v) = ρ(α_{1}, β_{1}) = ρ(\frac{1}{2}x ⊕ \frac{1}{2}α, \frac{1}{2}y ⊕ \frac{1}{2}β) ≤ \frac{1}{2}(ρ(x, y) + ρ(α, β))
≤ \frac{1}{2}ρ(x, y) + \frac{1}{2}((1 − \frac{k}{2^{n}})ρ(x, y) + \frac{k}{2^{n}} ρ(z, w))
= (1 − \frac{k}{2^{n+1}} )ρ(x, y) + \frac{k}{2^{n+1}} ρ(z, w).

Suppose now that 2^{n} < k ≤ 2^{n+1} and let p := 2^{n+1} − k. Then p ≤ 2^{n}, so we can apply (∗∗) for p. We obtain

ρ(u, v) = ρ(\frac{p}{2^{n+1}} x ⊕ (1 − \frac{p}{2^{n+1}} )z, \frac{p}{2^{n+1}} y ⊕ (1 − \frac{p}{2^{n+1}} )w)
= ρ((1 − \frac{p}{2^{n+1}} )z ⊕ \frac{p}{2^{n+1}} x, (1 − \frac{p}{2^{n+1}} )w ⊕ \frac{p}{2^{n+1}} y)
≤ (1 − \frac{p}{2^{n+1}} )ρ(z, w) + \frac{p}{2^{n+1}} ρ(x, y)
= (1 − \frac{k}{2^{n+1}} )ρ(x, y) + \frac{k}{2^{n+1}} ρ(z, w).

In the sequel, we use the fact that the set D := \{\frac{k}{2^{n}} | k, n ∈ IN, k ≤ 2^{n}\} is dense in [0, 1]. Let t ∈ [0, 1]. Then there is (t_{p})_{p∈IN} ⊆ D such that lim_{p→∞} t_{p} = t. For all p ∈ IN,

ρ((1 − t_{p})x ⊕ t_{p}z, (1 − t_{p})y ⊕ t_{p}z) ≤ (1 − t_{p})ρ(x, y).

Letting p → ∞ and using Lemma 2.8(ii) and the fact that ρ is continuous, we get (3). □

Corollary 2.12 Let (X, ρ, M) be a hyperbolic space. Then for all t ∈ [0, 1] and x, y, z ∈ X,

(4) ρ((1 − t)x ⊕ tz, y) ≤ (1 − t)ρ(x, y) + tρ(z, y).

Proof: Apply (3) with w = y. □

Let us now present the related concept of metric space of hyperbolic type [7, 4] which was introduced first in [18] under the name ‘convex metric space’. Let (X, ρ) be a metric space and S a family of metric segments. We say that (X, ρ, S) is of hyperbolic type if the following are satisfied:

(i) for each two points x, y ∈ X there is a unique metric segment from S that joins them, denoted [x, y]; (ii) if p, x, y, m ∈ X and if m ∈ [x, y] satisfies ρ(x, m) = tρ(x, y) for t ∈ [0, 1], then

ρ(p, m) ≤ (1 − t)ρ(p, x) + tρ(p, y).

Proposition 2.13 Any hyperbolic space is of hyperbolic type.

Proof: Let (X, ρ, M) be a hyperbolic space. Let S be the family of all metric segments determined by the metric embeddings associated with M. Let x, y ∈ M. If x ≠ y, then (i) is satisfied, by Proposition 2.3. If x = y, then the unique metric segment from S that joins x and x is [x, x] = {x}. Let us verify (ii). Since m ∈ [x, y] and ρ(x, m) = tρ(x, y) = ρ(x, (1 − t)x ⊕ ty), by Lemma 2.4(ii), we must have m = (1 − t)x ⊕ ty. Now apply (4). □

In the sequel, let (λ_{n})_{n∈IN} ⊆ [0, 1).

Let us denote for all i, n ∈ IN,

S_{i,n} := ∑_{s=i}^{i+n−1} λ_{s},

P_{i,n} := ∏_{s=i}^{i+n−1} \frac{1}{1 − λ_{s}} .

Let (x_{n})_{n∈IN}, (y_{n})_{n∈IN} be two sequences in X such that for all n ∈ IN,

x_{n+1} = (1 − λ_{n})x_{n} ⊕ λ_{n}y_{n}.

The following very important result was proved in [4] for spaces of hyperbolic type. Hence, by Proposition 2.13, it is true also for hyperbolic spaces.

Proposition 2.14 ([4]) Let (X, ρ, M) be a hyperbolic space. Suppose that (x_{n})_{n∈IN}, (y_{n})_{n∈IN} satisfy for all n ∈ IN,

ρ(y_{n}, y_{n+1}) ≤ ρ(x_{n}, x_{n+1}).

Then the sequence (ρ(x_{n}, y_{n}))_{n∈IN} ⊆ IR is nonincreasing and for all i, n ∈ IN,

(1 + S_{i,n})ρ(x_{i}, y_{i}) ≤ ρ(x_{i}, y_{i+n}) + P_{i,n}[ρ(x_{i}, y_{i}) − ρ(x_{i+n}, y_{i+n})].

We shall use in the sequel the following consequence of the above inequality.

Proposition 2.15 ([2]) In the assumptions of Proposition 2.14,

S_{i,n}ρ(x_{i}, y_{i}) ≤ ρ(x_{i}, x_{i+n}) + P_{i,n}[ρ(x_{i}, y_{i}) − ρ(x_{i+n}, y_{i+n})].

Proof: Apply Proposition 2.14 and the fact that ρ(x_{i}, y_{i+n}) − ρ(x_{i}, y_{i}) ≤ ρ(x_{i}, x_{i+n})+ρ(x_{i+n}, y_{i+n})−ρ(x_{i}, y_{i}) ≤ ρ(x_{i}, x_{i+n}), since(ρ(x_{n}, y_{n}))_{n∈IN} is nonincreasing, hence ρ(x_{i+n}, y_{i+n}) − ρ(x_{i}, y_{i}) ≤ 0. □

Proposition 2.16 ([4]) In addition to the assumptions of Proposition 2.14, assume that

(i) the set {ρ(x_{n}, y_{n+i}) | n, i ∈ IN} is bounded; (ii) (λ_{n})_{n∈IN} is divergent in sum; (iii) there is b ∈ (0, 1) such that λ_{n} ≤ b for all n ∈ IN.

Then lim_{n→∞} ρ(x_{n}, y_{n}) = 0.

Proof: This result is proved in [4] for any space of hyperbolic type. Applying again Proposition 2.13, it follows that it is true for any hyperbolic space, too. □

Lemma 2.17 In the hypotheses of Proposition 2.14, the following are equivalent

(i) (x_{n})_{n∈IN} is bounded; (ii) (y_{n})_{n∈IN} is bounded; (iii) the set {ρ(x_{n}, y_{n+i}) | n, i ∈ IN} is bounded.

Proof: Let n, i ∈ IN. (i)⇒(ii) ρ(y_{n}, y_{n+i}) ≤ ρ(y_{n}, x_{n}) + ρ(x_{n}, x_{n+i}) + ρ(x_{n+i}, y_{n+i}) ≤ 2ρ(x_{0}, y_{0}) + ρ(x_{n}, x_{n+i}), since (ρ(x_{n}, y_{n}))_{n∈IN} is nonincreasing, by Proposition 2.14. (ii)⇒(iii) ρ(x_{n}, y_{n+i}) ≤ ρ(x_{n}, y_{n}) + ρ(y_{n}, y_{n+i}) ≤ ρ(x_{0}, y_{0}) + ρ(y_{n}, y_{n+i}). (iii)⇒(i) ρ(x_{n}, x_{n+i}) ≤ ρ(x_{n}, y_{n+i}) + ρ(y_{n+i}, x_{n+i}) ≤ ρ(x_{n}, y_{n+i}) + ρ(x_{0}, y_{0}). □

Lemma 2.18 The following are equivalent:

(i) lim sup_{n→∞} λ_{n} < 1;

(ii) there is b ∈ (0, 1) such that λ_{n} ≤ b < 1 for all n ∈ IN.

Proof: Obviously, since λ_{n} < 1 for all n ∈ IN. □

Using these lemmas, we obtain the following reformulation of Proposition 2.16.

Theorem 2.19 Let (X, ρ, M) be a hyperbolic space and (λ_{n})_{n∈IN} ⊆ [0, 1). Suppose that (λ_{n})_{n∈IN} is divergent in sum and lim sup_{n→∞} λ_{n} < 1.

Let (x_{n})_{n∈IN}, (y_{n})_{n∈IN} be two sequences in X which satisfy for all n ∈ IN:

x_{n+1} = (1 − λ_{n})x_{n} ⊕ λ_{n}y_{n} and
ρ(y_{n}, y_{n+1}) ≤ ρ(x_{n}, x_{n+1}).

If (x_{n})_{n∈IN} is bounded, then lim_{n→∞} ρ(x_{n}, y_{n}) = 0.

3 Uniform asymptotic regularity for directionally nonexpansive mappings

The main purpose of the present paper is to generalize the core results from [13] and [14] not only to hyperbolic spaces (which is largely straightforward) but at the same time to directionally nonexpansive mappings which requires quite some care. Directionally nonexpansive mappings were considered in [8]. In this section we will, in particular, strengthen the main results from [8].

Definition 3.1 ([8]) Let (X, ρ, M) be a hyperbolic space and C ⊆ X a nonempty convex subset. A mapping f : C → C is called directionally nonexpansive if

ρ(f(x), f(y)) ≤ ρ(x, y),

for all x ∈ C and y ∈ [x, f(x)].

Let us recall that f : C → C is called nonexpansive if for all x, y ∈ C,

ρ(f(x), f(y)) ≤ ρ(x, y).

Obviously, any nonexpansive mapping is directionally nonexpansive, but the converse fails as directionally nonexpansive mappings not even need to be continuous on the whole space:

Example (simplified by Paulo Oliva): Consider the normed space (IR^{2}, ∥ · ∥_{max}) and the function

f : [0, 1]^{2} → [0, 1]^{2}, f(x, y) := \{ \begin{matrix}(1, y), if y > 0 \\ (0, y), if y = 0. \end{matrix}

Clearly, f is directionally nonexpansive (even directionally constant) but discontinuous at (0, 0).

In the following, (X, ρ, M) will be an arbitrary hyperbolic space, C ⊆ X a non-empty convex subset of X and f : C → C a directionally nonexpansive mapping. Let us define [2]

r_{C}(f) := inf{ρ(x, f(x)) | x ∈ C}.

We consider the so-called Krasnoselski-Mann iteration starting from x ∈ C

x_{0} := x, x_{n+1} := (1 − λ_{n})x_{n} ⊕ λ_{n}f(x_{n}),

where (λ_{n})_{n∈IN} is a sequence of real numbers in [0, 1).

Lemma 3.2 For all n ∈ IN,

ρ(f(x_{n}), f(x_{n+1})) ≤ ρ(x_{n}, x_{n+1}).

Proof: Since x_{n+1} ∈ [x_{n}, f(x_{n})], we can apply the fact that f is directionally nonexpansive to obtain that ρ(f(x_{n}), f(x_{n+1})) ≤ ρ(x_{n}, x_{n+1}). □

Thus, the sequences (x_{n})_{n∈IN}, (f(x_{n}))_{n∈IN} satisfy the hypotheses of Proposition 2.14 with y_{n} := f(x_{n}). We get immediately the following results.

Proposition 3.3 The sequence (ρ(x_{n}, f(x_{n})))_{n∈IN} ⊆ IR is nonincreasing and for all i, n ∈ IN,

S_{i,n}ρ(x_{i}, f(x_{i})) ≤ ρ(x_{i}, x_{i+n}) + P_{i,n}[ρ(x_{i}, f(x_{i})) − ρ(x_{i+n}, f(x_{i+n}))].

Proof: Apply Lemma 3.2, Proposition 2.14 and Proposition 2.15. □

For nonexpansive mappings the following proposition is due to [6] (normed spaces) and [4] for hyperbolic spaces. Using Lemma 3.2, the proof from [4] extends to directionally nonexpansive mappings:

Proposition 3.4 Suppose that (λ_{n})_{n∈IN} is divergent in sum and lim sup_{n→∞} λ_{n} < 1.

If (x_{n})_{n∈IN} is bounded, then lim_{n→∞} ρ(x_{n}, f(x_{n})) = 0.

Proof: By Theorem 2.19 and Lemma 3.2. □

Corollary 3.5 Suppose that (λ_{n})_{n∈IN} is divergent in sum and lim sup_{n→∞} λ_{n} < 1.

If C is bounded, then for every x ∈ X, lim_{n→∞} ρ(x_{n}, f(x_{n})) = 0.

Corollary 3.6 Suppose that (λ_{n})_{n∈IN} is divergent in sum and lim sup_{n→∞} λ_{n} < 1.

If C is bounded or – even weaker – there is x ∈ C such that (x_{n})_{n∈IN} is bounded, then r_{C}(f) = 0.

Let x^{∗} ∈ C and (x_{n}^{∗})_{n∈IN} be the Krasnoselski-Mann iteration starting from x^{∗}. The next inequality is due to [2]:

Lemma 3.7 If f is nonexpansive, then for all n ∈ IN,

ρ(x_{n+1}, x_{n+1}^{∗}) ≤ ρ(x_{n}, x_{n}^{∗}).

Proof: Applying inequality (3) and the definition of a nonexpansive mapping, we get that

ρ(x_{n+1}, x_{n+1}^{∗}) = ρ((1 − λ_{n})x_{n} ⊕ λ_{n}f(x_{n}), (1 − λ_{n})x_{n}^{∗} ⊕ λ_{n}f(x_{n}^{∗}))
≤ (1 − λ_{n})ρ(x_{n}, x_{n}^{∗}) + λ_{n}ρ(f(x_{n}), f(x_{n}^{∗}))
≤ (1 − λ_{n})ρ(x_{n}, x_{n}^{∗}) + λ_{n}ρ(x_{n}, x_{n}^{∗})
= ρ(x_{n}, x_{n}^{∗}).

□ Since in general x_{n}^{∗} ∈ /[x_{n}, f(x_{n})], we cannot prove the inequality

ρ(f(x_{n}), f(x_{n}^{∗})) ≤ ρ(x_{n}, x_{n}^{∗})

on which the proof of Lemma 3.7 is based for directionally nonexpansive mappings f. The absence of Lemma 3.7 will cause some changes in the generalizations of the main results from [13] and [14] to directionally nonexpansive mappings carried out below.

In [2] the following theorem is proved:

Theorem 3.8 ([2]) Let (X, ∥ · ∥) be a normed linear space, C ⊆ X convex and f : C → C nonexpansive. Let (λ_{n})_{n∈IN} be a sequence of real numbers in [0, 1) which is divergent in sum and satisfies lim sup_{n→∞} λ_{n} < 1. Then

∥x_{n} − f(x_{n})∥ →^{n→∞} r_{C}(f),

where (x_{n})_{n∈IN} is the Krasnoselski-Mann iteration starting from x ∈ C.

In [13], the first author obtained by a logical analysis of the proof of Theorem 3.8 from [2] an effective quantitative version of that theorem (see also Remark 3.10). From this quantitative version various strong (effective) uniformity results for the case of bounded C were derived (improving previous results in this direction from [3] and [4]) as well as (for the first time) for the more general case of bounded (x_{n})_{n∈IN} (see [14]). Since these uniformity results were obtained by logical analysis and, in particular, did not use any functional analytic embedding techniques (in contrast to [3] and [4]) this suggests that it should be possible to extend these results to the more general setting of hyperbolic spaces and directionally nonexpansive mappings. The main content of this paper is to show that this is indeed true to a large extent. Whereas the extension to hyperbolic spaces does not cause any problems at all, the absence of Lemma 3.2 for directionally nonexpansive mappings results in an additional hypothesis which, however, is trivially satisfied e.g. in the bounded case.

Theorem 3.9 Let (X, ρ, M) be a hyperbolic space, C ⊆ X a non-empty convex subset and f : C → C a directionally nonexpansive mapping. Let (λ_{n})_{n∈IN} be a sequence in [0, 1) which is divergent in sum and satisfies

∀n ∈ IN(λ_{n} ≤ 1 − \frac{1}{K})

for some K ∈ IN. Let α : IN × IN → IN be such that

∀i, n ∈ IN((α(i, n) ≤ α(i + 1, n)) ∧ (n ≤ ∑_{s=i}^{i+α(i,n)−1} λ_{s})).

Let x, x^{∗} ∈ C and d > 0 be such that

∀n ∈ IN(ρ(x_{n}, x_{n}^{∗}) ≤ d),

where (x_{n})_{n∈IN} and (x_{n}^{∗})_{n∈IN} are the Krasnoselski-Mann iterations starting from x and x^{∗}. Then the following holds

∀ε > 0∀n ≥ h(ε, x, d, f, K, α)(ρ(x_{n}, f(x_{n})) < ρ(x^{∗}, f(x^{∗})) + ε),

where^{2}

h(ε, x, d, f, K, α) := α̂(⌈2c(f, x) · exp(K(M + 1))⌉ − · 1, M), where M ∈ IN is such that M ≥ \frac{1+2d}{ε}, c(f, x) ∈ IR is such that c(f, x) ≥ ρ(x, f(x)) and α̂(0, n) := α̃(0, n), α̂(i + 1, n) := α̃(α̂(i, n), n) with α̃(i, n) := i + α(i, n) (i, n ∈ IN)

2n − · 1 = max(0, n − 1).

Proof: Most parts of the proof follow closely the one given in [13] for the nonexpansive case (and normed spaces). For completeness we present, nevertheless, all details. Let

(1) γ := ρ(x^{∗}, f(x^{∗})).

Let ε > 0 be arbitrary and M ∈ IN be such that

(2) M ≥ \frac{1 + 2d}{ε}.

For example, M := ⌈\frac{1+2d}{ε}⌉.

Let δ > 0 be so small that

(3) δ exp(K(M + 1)) < 1.

For example, δ := \frac{1}{2 exp(K(M+1))}.

Let i, n ∈ IN. Then (reasoning as in [6])

P_{i,n} = ∏_{s=i}^{i+n−1}(1 + \frac{λ_{s}}{1−λ_{s}}) = exp(ln ∏_{s=i}^{i+n−1}(1 + \frac{λ_{s}}{1−λ_{s}}))

= exp( ∑_{s=i}^{i+n−1} ln(1 + \frac{λ_{s}}{1−λ_{s}}))

≤ exp( ∑_{s=i}^{i+n−1} \frac{λ_{s}}{1−λ_{s}}), since ln(1 + x) ≤ x for x ≥ 0

≤ exp(K ∑_{s=i}^{i+n−1} λ_{s}) = exp(K · S_{i,n}),

since λ_{s} ≤ 1 − \frac{1}{K} implies 1 − λ_{s} ≥ \frac{1}{K}, so \frac{1}{1−λ_{s}} ≤ K for all s ∈ IN. Hence, we have proved that for all i, n ∈ IN,

(4) P_{i,n} ≤ exp(K · S_{i,n}).

Let us define α^{∗} : IN × IN → IN by

(5) α^{∗}(i, n) := min{m ∈ IN | n ≤ S_{i,m}}.

Since (λ_{n})_{n∈IN} is divergent in sum, it follows that for all i ∈ IN, the sequence (S_{i,m})_{m∈IN} is not bounded above, so for all n ∈ IN the set A_{i,n} := {m ∈ IN | n ≤ S_{i,m}} is non-empty, hence it has a least element. Thus, α^{∗} is well-defined.

We also get that α^{∗}(i, n) − 1 ∈ / A_{i,n}, which means that S_{i,α^{∗}(i,n)−1} < n, that is S_{i,α^{∗}(i,n)} − λ_{i+α^{∗}(i,n)−1} < n, so S_{i,α^{∗}(i,n)} < n + λ_{i+α^{∗}(i,n)−1} < n + 1. Hence, for all i, n ∈ IN,

(6) n ≤ S_{i,α^{∗}(i,n)} < n + 1.

Consider the Krasnoselski-Mann iteration (x_{n}^{∗})_{n∈IN} starting from x^{∗}. Then

\begin{matrix}ρ(x_{i}^{∗}, x_{i+n}^{∗}) ≤ ∑_{s=i}^{i+n−1} ρ(x_{s}^{∗}, x_{s+1}^{∗}) = ∑_{s=i}^{i+n−1} λ_{s}ρ(x_{s}^{∗}, f(x_{s}^{∗})) \\ ≤ ( ∑_{s=i}^{i+n−1} λ_{s})ρ(x_{i}^{∗}, f(x_{i}^{∗})) = S_{i,n} · ρ(x_{i}^{∗}, f(x_{i}^{∗})) ≤ S_{i,n} · ρ(x^{∗}, f(x^{∗})), \end{matrix}

since, by Proposition 3.3, (ρ(x_{n}^{∗}, f(x_{n}^{∗})))_{n∈IN} is nonincreasing. Hence, for all i, n ∈ IN,

(7) ρ(x_{i}^{∗}, x_{i+n}^{∗}) ≤ S_{i,n} · ρ(x^{∗}, f(x^{∗})).

Consider now the Krasnoselski-Mann iteration (x_{n})_{n∈IN} starting from x. Applying again Proposition 3.3, we get that the sequence (ρ(x_{n}, f(x_{n})))_{n∈IN} is nonincreasing and, since is bounded below by 0, it is convergent and hence Cauchy. Thus, for δ > 0 there exists an i such that

(8) ρ(x_{i}, f(x_{i})) − ρ(x_{i+α^{∗}(i,M)}, f(x_{i+α^{∗}(i,M)})) ≤ δ.

In the sequel, we shall consider an i satisfying (8). Applying Proposition 3.3 and (8), we get that

S_{i,α^{∗}(i,M)} · ρ(x_{i}, f(x_{i})) ≤ ρ(x_{i}, x_{i+α^{∗}(i,M)}) + δ · P_{i,α^{∗}(i,M)}

≤ ρ(x_{i}, x_{i}^{∗}) + ρ(x_{i}^{∗}, x_{i+α^{∗}(i,M)}^{∗}) + ρ(x_{i+α^{∗}(i,M)}^{∗}, x_{i+α^{∗}(i,M)}) + δ · P_{i,α^{∗}(i,M)} ≤ 2d + S_{i,α^{∗}(i,M)} · ρ(x^{∗}, f(x^{∗})) + δ · P_{i,α^{∗}(i,M)}, by the hypothesis and (7) = 2d + S_{i,α^{∗}(i,M)} · γ + δ · P_{i,α^{∗}(i,M)}, by (1).

That is, we have got

(9) S_{i,α^{∗}(i,M)} · ρ(x_{i}, f(x_{i})) ≤ 2d + S_{i,α^{∗}(i,M)} · γ + δ · P_{i,α^{∗}(i,M)}.

Let us now prove

(10) ρ(x_{i}, f(x_{i})) < γ + ε.

Suppose that ρ(x_{i}, f(x_{i})) ≥ γ + ε. It follows that S_{i,α^{∗}(i,M)}(γ + ε) ≤ S_{i,α^{∗}(i,M)} · ρ(x_{i}, f(x_{i})), so applying (9), we get that S_{i,α^{∗}(i,M)}(γ + ε) ≤ 2d + S_{i,α^{∗}(i,M)} · γ + δ · P_{i,α^{∗}(i,M)}. Hence,

(11) S_{i,α^{∗}(i,M)} · ε ≤ 2d + δ · P_{i,α^{∗}(i,M)}.

It follows that

1 + 2d ≤ M · ε  by (2)
≤ S_{i,α^{∗}(i,M)} · ε  by (6)
≤ 2d + δ · P_{i,α^{∗}(i,M)}  by (11)
≤ 2d + δ · exp(K · S_{i,α^{∗}(i,M)}) by (4)
< 2d + δ · exp(K(M + 1)) by (6)
< 2d + 1  by (3).

That is, we have got a contradiction. Hence, we have proved that if i ∈ IN is such that

(8) ρ(x_{i}, f(x_{i})) − ρ(x_{i+α^{∗}(i,M)}, f(x_{i+α^{∗}(i,M)})) ≤ δ,

then

(10) ρ(x_{i}, f(x_{i})) < γ + ε.

Define α̃^{∗}, α̂^{∗} : IN × IN → IN by

α̃^{∗}(k, n) := k + α^{∗}(k, n) and

α̂^{∗}(0, n) := α̃^{∗}(0, n) and α̂^{∗}(k + 1, n) := α̃^{∗}(α̂^{∗}(k, n), n).

Since α̂^{∗}(k + 1, n) = α̃^{∗}(α̂^{∗}(k, n), n) = α̂^{∗}(k, n) + α^{∗}(α̂^{∗}(k, n), n) ≥ α̂^{∗}(k, n), it follows that for all k, n ∈ IN,

(12) α̂^{∗}(k, n) ≤ α̂^{∗}(k + 1, n).

Claim: Let j := ⌈\frac{ρ(x,f(x))}{δ}⌉ − · 1. For all n ∈ IN,

(13) ∃k ≤ j(ρ(x_{_{α^{∗}}(k,n)}, f(x_{_{α^{∗}}(k,n)})) − ρ(x_{_{α^{∗}}(k+1,n)}, f(x_{_{α^{∗}}(k+1,n)})) ≤ δ).

Proof of Claim: Let n ∈ IN and for every k ∈ IN let

T_{k} := ρ(x_{_{α^{∗}}(k,n)}, f(x_{_{α^{∗}}(k,n)})) − ρ(x_{_{α^{∗}}(k+1,n)}, f(x_{_{α^{∗}}(k+1,n)})).

Suppose the claim is false. Then T_{k} > δ for all k ≤ j, so ∑_{k=0}^{j} T_{k} > δ · (j + 1), that is

\begin{matrix}ρ(x_{_{α^{∗}}(0,n)}, f(x_{_{α^{∗}}(0,n)})) − ρ(x_{_{α^{∗}}(j+1,n)}, f(x_{_{α^{∗}}(j+1,n)})) \\ > δ · (j + 1) = δ · ⌈\frac{ρ(x,f(x))}{δ}⌉ ≥ ρ(x, f(x)). \end{matrix}

¿From this we get that

ρ(x_{_{α^{∗}}(0,n)}, f(x_{_{α^{∗}}(0,n)})) > ρ(x, f(x)),

which is a contradiction to the fact that the sequence (ρ(x_{n}, f(x_{n})))_{n∈IN} is nonincreasing and finishes the proof of the claim. Let k satisfy (13) with n := M and let i := α̂^{∗}(k, M). Applying (13) and the definition of α̂^{∗}, it follows immediately that i satisfies (8). Hence, i also satisfies (10). Let c(f, x) ∈ IR be such that c(f, x) ≥ ρ(x, f(x)). Let

h(ε, x, d, f, K, α^{∗}) := α̂^{∗}(⌈2c(f, x) · exp(K(M + 1))⌉ − · 1, M).

Since we can put δ := \frac{1}{2 exp(K(M+1))}, we get that

\frac{ρ(x, f(x))}{δ} = 2ρ(x, f(x)) · exp(K(M + 1)) ≤ 2c(f, x) · exp(K(M + 1)).

Hence

k ≤ ⌈\frac{ρ(x, f(x))}{δ}⌉ − · 1 ≤ ⌈2c(f, x) · exp(K(M + 1))⌉ − · 1

Applying (12), it follows that i ≤ h(ε, x, d, f, K, α^{∗}). Using now the fact that i satisfies (10), we get immediately that

(13) ∀n ≥ h(ε, x, f, d, K, α^{∗})(ρ(x_{n}, f(x_{n})) < ρ(x^{∗}, f(x^{∗})) + ε).

Hence, we have obtained the conclusion of the theorem with α^{∗} instead of α. We now show that we can replace α^{∗} with α satisfying the more flexible requirement from the hypothesis

(14) ∀i, n ∈ IN((α(i, n) ≤ α(i + 1, n)) ∧ (n ≤ ∑_{s=i}^{i+α(i,n)−1} λ_{s})).

Since n ≤ S_{i,α(i,n)}, by the definition of α^{∗} it follows that for all i, n ∈ IN,

(15) α^{∗}(i, n) ≤ α(i, n).

Let us now prove that for all i, n ∈ IN,

α̂^{∗}(i, n) ≤ α̂(i, n).

We use induction on i. For i = 0, we get that

α̂^{∗}(0, n) = α̃^{∗}(0, n) = α^{∗}(0, n) ≤ α(0, n) = α̃(0, n) = α̂(0, n).

Suppose that α̂^{∗}(i, n) ≤ α̂(i, n). Using (15) and the fact that, by the hypothesis, α is nondecreasing in the first argument, we get that α̂^{∗}(i + 1, n) = α̃^{∗}(α̂^{∗}(i, n), n) = α̂^{∗}(i, n)+α^{∗}(α̂^{∗}(i, n), n) ≤ α̂(i, n)+α(α̂^{∗}(i, n), n) ≤ α̂(i, n)+ α(α̂(i, n), n) = α̃(α̂(i, n), n) = α̂(i + 1, n). It follows that

h(ε, x, d, f, K, α^{∗}) = α̂^{∗}(⌈2c(f, x) · exp(K(M + 1))⌉ − · 1, M)
≤ α̂(⌈2c(f, x) · exp(K(M + 1))⌉ − · 1, M)
= h(ε, x, d, f, K, α).

Finally, applying (13) we obtain

∀n ≥ h(ε, x, d, f, K, α)(ρ(x_{n}, f(x_{n})) < ρ(x^{∗}, f(x^{∗})) + ε).

□

Remark 3.10 If f is nonexpansive, applying Lemma 3.7, it follows that the sequence (ρ(x_{n}, x_{n}^{∗}))_{n∈IN} is nonincreasing, so letting d := ρ(x, x^{∗}) we get that

∀n ∈ IN(ρ(x_{n}, x_{n}^{∗}) ≤ d).

Hence, Theorem 3.9 holds with

h(ε, x, x^{∗}, f, K, α) = α̂(⌈2c(f, x) · exp(K(M + 1))⌉ − · 1, M), where
M ∈ IN is such that M ≥ \frac{1+2ρ(x,x^{∗})}{ε} and
c(f, x), α̃ and α̂ are as above.

It is this restricted form (for normed spaces) of Theorem 3.9 which is proved in [13].

The following remarks from [13] apply in our context as well:

Remark 3.11 Let α : IN × IN → IN be such that

(∗) ∀i, n ∈ IN(n ≤ ∑_{s=i}^{i+α(i,n)−1} λ_{s}).

Define α^{+} : IN × IN → IN by

α^{+}(i, n) := max_{j≤i} α(j, n).

Then α^{+} is nondecreasing in the first argument and also satisfies (*), so that Theorem 3.9 holds with h(ε, x, d, f, K, α^{+}).

Remark 3.12 A function α satisfying the conditions of Theorem 3.9 can easily be computed from a function β : IN → IN satisfying the weaker requirement

(∗∗) ∀n(n ≤ ∑_{s=0}^{β(n)} λ_{s}).

Just define β′(i, n) := β(n + i) − i + 1 and β^{+}(i, n) := max_{j≤i} β′(j, n).

Then β^{+} satisfies the conditions imposed on α so that Theorem 3.9 holds with h(ε, x, d, f, K, β^{+}), where β satisfies (∗).

Proof: We have only to verify that β′ satisfies the condition (∗) from Remark 3.11. Let i, n ∈ IN. Then

∑_{s=i}^{i+β′(i,n)−1} λ_{s} = ∑_{s=i}^{β(n+i)} λ_{s} = ∑_{s=0}^{β(n+i)} λ_{s} − ∑_{s=0}^{i−1} λ_{s} ≥ n + i − ∑_{s=0}^{i−1} λ_{s} > n + i − i = n,

since λ_{s} < 1 for all s ∈ IN. □

Let us just note that as a corollary to Theorem 3.9 we get the following (non-quantitative) strengthened version of the original Borwein-Reich-Shafrir theorem

Corollary 3.13 Let (X, ρ, M) be a hyperbolic space, C ⊆ X a non-empty convex subset and f : C → C a directionally nonexpansive mapping. Let (λ_{n})_{n∈IN} be a sequence in [0, 1) which is divergent in sum and satisfies that lim sup_{n→∞} λ_{n} < ∞. Then for all x ∈ C if

∀ε > 0∃x^{∗} ∈ C(ρ(x_{n}, x_{n}^{∗}) bounded ∧ ρ(x^{∗}, f(x^{∗})) ≤ r_{C}(f) + ε)

then

ρ(x_{n}, f(x_{n})) →^{n→∞} r_{C}(f).

The main application of the quantitative version of the Borwein-Reich-Shafrir theorem given in [13] was a fully uniform bound on the asymptotic regularity ∥x_{n} − f(x_{n})∥ → 0 in the case of bounded C. ‘Fully uniform’ here means that the rate of convergence only depends on the error ε, an upper bound d for the diameter of C and the quantities K, α on λ_{k} but not on x, f or any special features of C. Uniformity in x (for constant λ_{k} := λ) was first established in [3]. In [4], uniformity in x and f has been proved for general λ_{k}, but no uniformity in C or λ_{k}. Moreover, no effective bounds were obtained. Recently ([8], Theorem 1), Kirk established uniformity in x, f for directionally nonexpansive mappings in the case of constant λ_{k} := λ. All these results are based on functional analytic embeddings. We now show that the results obtained in [13] by logical analysis of the proof of Theorem 3.8 extend even with the same numerical bounds to the case of hyperbolic spaces and directionally nonexpansive mappings (containing Theorem 1 from [8] just mentioned as a special case). This is due to the fact that the only additional assumption that ∀n ∈ IN(ρ(x_{n}, x_{n}^{∗}) ≤ d) which we had to impose in the directionally nonexpansive case holds trivially for sets C whose diameter is bounded by d. The proofs of Corollaries 3.14,3.16,3.17 and 3.19 follow the ones in [13] for the corresponding results in the case of nonexpansive mappings in normed spaces except that we now have to use our more general Theorem 3.9:

Corollary 3.14 Let (X, ρ, M) be a hyperbolic space, C ⊆ X a non-empty convex bounded subset with diameter d(C) < ∞ and f : C → C a directionally nonexpansive mapping. Let (λ_{n})_{n∈IN} be a sequence in [0, 1) which is divergent in sum and satisfies

∀n ∈ IN(λ_{n} ≤ 1 − \frac{1}{K})

for some K ∈ IN. Let α : IN × IN → IN be such that

∀i, n ∈ IN((α(i, n) ≤ α(i + 1, n)) ∧ (n ≤ ∑_{s=i}^{i+α(i,n)−1} λ_{s})).

Then the following holds

∀x ∈ C∀ε > 0∀n ≥ h(ε, d, K, α)(ρ(x_{n}, f(x_{n})) ≤ ε),

where

h(ε, d, K, α) := α̂(⌈2d · exp(K(M + 1))⌉ − 1, M)), with
d ∈ IR is such that d ≥ d(C),
M ∈ IN is such that M ≥ \frac{1+2d}{ε} and
α̂(0, n) := α̃(0, n), α̂(i + 1, n) := α̃(α̂(i, n), n) with
α̃(i, n) := i + α(i, n).

Proof: Let x ∈ C and ε > 0. Let d ≥ d(C). Then for every x^{∗} ∈ C, we have that ρ(x_{n}, x_{n}^{∗}) ≤ d(C) ≤ d for all n ∈ IN. Hence, for every x^{∗} ∈ C, we can apply Theorem 3.9 to get

∀n ≥ h(ε, x, d, f, K, α)(ρ(x_{n}, f(x_{n})) < ρ(x^{∗}, f(x^{∗})) + ε),

where

h(ε, x, d, f, K, α) := α̂(⌈2c(f, x) · exp(K(M + 1))⌉ − · 1, M), where M ∈ IN is such that M ≥ \frac{1+2d}{ε}, c(f, x) ∈ IR is such that c(f, x) ≥ ρ(x, f(x)) and α̃, α̂ are defined as above.

Since d ≥ d(C) ≥ ρ(x, f(x)), we can take c(x, f) := d. Thus, we get that

\begin{aligned}h(ε, x, d, f, K, α) & = α̂(⌈2d · exp(K(M + 1))⌉ − 1, M) \\ & = h(ε, d, K, α). \end{aligned}

Let n ≥ h(ε, d, K, α). It follows that

∀x^{∗} ∈ C(ρ(x_{n}, f(x_{n})) < ρ(x^{∗}, f(x^{∗})) + ε),

hence

ρ(x_{n}, f(x_{n})) ≤ inf{ρ(x^{∗}, f(x^{∗})) | x^{∗} ∈ C} + ε,

that is

ρ(x_{n}, f(x_{n})) ≤ r_{C}(f) + ε.

Apply now the fact that r_{C}(f) = 0, by Corollary 3.6. □

Remark 3.15 In Corollary 3.14, the bound h(ε, d, K, α) can be replaced by h(ε/d, 1, K, α) just by applying the old bound to the modified hyperbolic space, where ρ_{d}(x, y) := \frac{1}{d}ρ(x, y) and c_{d}(s) := c(d · s).

Corollary 3.16 Let d, ε > 0, K ∈ IN and β : IN → IN be an arbitrary mapping. Then there exists an N ∈ IN such that for any hyperbolic space (X, ρ, M), any non-empty bounded convex set C ⊆ X such that d(C) ≤ d, any directionally nonexpansive mapping f : C → C, any sequence λ_{n} ∈ [0, 1 − \frac{1}{K}]

satisfying n ≤ ∑_{s=0}^{β(n)} λ_{s} (for all n ∈ IN) and any x ∈ C, the following holds

∀n ≥ N(ρ(x_{n}, f(x_{n})) ≤ ε).

Proof: ¿From n ≤ ∑_{s=0}^{β(n)} λ_{s} for all n ∈ IN, it follows that (λ_{n})_{n∈IN} is divergent

in sum. Apply Remark 3.12 and Corollary 3.14. □

Corollary 3.17 Let (X, ρ, M) be a hyperbolic space, C ⊆ X a non-empty convex bounded subset with diameter d(C) < ∞ and f : C → C a directionally nonexpansive mapping. Let K ∈ IN, K ≥ 2 and (λ_{n})_{n∈IN} be a sequence in [\frac{1}{K} , 1 − \frac{1}{K}]. Then the following holds:

∀x ∈ C∀ε > 0∀n ≥ h(ε, d, K)(ρ(x_{n}, f(x_{n})) ≤ ε),

where

h(ε, d, K) := K · M · ⌈2d · exp(K(M + 1))⌉ with
d ∈ IR, d ≥ d(C) and
M ∈ IN, M ≥ \frac{1+2d}{ε}.

Proof: Define α : IN × IN → IN by

α(i, n) = Kn.

Then ∑_{s=i}^{i+α(i,n)−1} λ_{s} ≥ ∑_{s=i}^{i+α(i,n)−1} \frac{1}{K} = \frac{1}{K} α(i, n) = n and α(i, n) = α(i + 1, n) =

Kn, so α satisfies the conditions of Corollary 3.14. We also get immediately that

α̃(i, n) = i + α(i, n) = i + Kn and
α̂(i, n) = K(i + 1)n.

Applying Corollary 3.14, it follows that

∀x ∈ C∀ε > 0∀n ≥ h(ε, d, K, α)(ρ(x_{n}, f(x_{n})) ≤ ε),

where

h(ε, d, K, α) = α̂(⌈2d · exp(K(M + 1))⌉ − 1, M)
= K · M · ⌈2d · exp(K(M + 1))⌉
= h(ε, d, K).

□ Remark 3.18 1. We could have used in the proof of the above corollary

also Corollary 3.12 for the function β : IN → IN defined by

β(n) = Kn − 1

instead of 3.14. However, this would have resulted in the much less good bound

h(ε, d, K) = \frac{K}{K−1} · M · (K^{⌈2d·exp(K(M+1))⌉−1} − 1), where
d ≥ d(C) and M ∈ IN, M ≥ \frac{1+2d}{ε}.

2. For the special case of constant λ_{n} = λ ∈ (0, 1), normed spaces and nonexpansive functions the exponential bound in Corollary 3.17 is not optimal. In fact, [1] establishes – using an extremely complicated proof involving computer aided calculations – an optimal quadratic bound in this special case. However, even for normed spaces and nonexpansive mappings the bounds in the present paper and [13] are the only effective bounds known at all for non-constant sequences λ_{n}.

The next corollary strengthens theorem 1 in [8]:

Corollary 3.19 Let d, ε > 0 and K ∈ IN, K ≥ 2. Then there exists an N ∈ IN such that for any hyperbolic space (X, ρ, M), any non-empty bounded convex set C ⊆ X such that d(C) ≤ d, any directionally nonexpansive mapping f : C → C, any sequence (λ_{n})_{n∈IN} in [\frac{1}{K} , 1 − \frac{1}{K}] and any x ∈ C, the following holds

∀n ≥ N(ρ(x_{n}, f(x_{n})) ≤ ε).

Proof: Apply Corollary 3.17. □

In [14] (Theorem 2.5) the first author extended (for normed spaces and nonexpansive mappings) Corollary 3.14 to the situation where C no longer is required to be bounded but only the existence of a point x^{∗} ∈ C whose iteration sequence (x_{n}^{∗})_{n∈IN} is bounded is assumed. We obtained a fully uniform bound which only depends on an upper bound d on ∥x − x^{∗}∥ and ∥x_{n}^{∗}∥ (and ε, K, α). This is of interest since the functional analytic embedding techniques from [4],[8] seem to require that C is bounded. Using the results above it is easy to see that Theorem 2.5 from [14] extends to hyperbolic spaces:

Theorem 3.20 Let (X, ρ, M) be a hyperbolic space, C ⊆ X a non-empty convex subset and f : C → C a nonexpansive mapping, (λ_{n})_{n∈IN}, α and K be as before. Let d > 0, x, x^{∗} ∈ C be such that

ρ(x, x^{∗}) ≤ d ∧ ∀n, m ∈ IN(ρ(x_{n}^{∗}, x_{m}^{∗}) ≤ d).

Then the following holds

∀ε > 0∀n ≥ h(ε, d, K, α)(ρ(x_{n}, f(x_{n})) ≤ ε),

where

h(ε, d, K, α) := α̂(⌈12d · exp(K(M + 1))⌉ − 1, M)), with d ∈ IR is such that d ≥ d(C), M ∈ IN is such that M ≥ \frac{1+6d}{ε} and α̂ as before.

Proof: As in the proof of Theorem 2.5 in [14] using Remark 3.10 and Proposition 3.4. □

For the case of directionally nonexpansive mappings, however, the additional assumption in our Theorem 3.9 causes various problems and changes in the proofs. In the following, we will only consider the case where (x_{n})_{n∈IN} itself is bounded (i.e. x = x^{∗}). We will need an additional assumption which for the case of constant λ_{k} := λ though is redundant. The proof differs significantly from that given in [14] since the argument which was used there to derive the bound ρ(x, f(x)) ≤ 6d in the nonexpansive case does not seem to hold for directionally nonexpansive mappings. However, a different bound can be obtained depending on α.

For any k ∈ IN, we define the sequence ((x_{k})_{m})_{m∈IN} by:

(x_{k})_{0} = x_{k}, (x_{k})_{m+1} = (1 − λ_{m})(x_{k})_{m} ⊕ λ_{k}f((x_{k})_{m}).

Hence, for any k ∈ IN, ((x_{k})_{m})_{m∈IN} is the Krasnoselski-Mann iteration starting with x_{k}.

Remark 3.21 ((x_{k})_{m})_{m∈IN} is not in general a subsequence of (x_{n})_{n∈IN}. But if (λ_{n})_{n∈IN} is a constant sequence, λ_{n} = λ, then (x_{k})_{m} = x_{k+m} for all m, k ∈ IN, hence ((x_{k})_{m})_{m∈IN} is a subsequence of (x_{n})_{n∈IN}.

Theorem 3.22 Let (X, ρ, M) be a hyperbolic space, C ⊆ X a non-empty convex subset and f : C → C a directionally nonexpansive mapping. Let (λ_{n})_{n∈IN} be a sequence in [0, 1) which is divergent in sum and satisfies

∀n ∈ IN(λ_{n} ≤ 1 − \frac{1}{K})

for some K ∈ IN. Let α : IN × IN → IN be such that

∀i, n ∈ IN((α(i, n) ≤ α(i + 1, n)) ∧ (n ≤ ∑_{s=i}^{i+α(i,n)−1} λ_{s})).

Let d > 0 and x ∈ C such that

∀n, k, m ∈ IN(ρ(x_{n}, (x_{k})_{m}) ≤ d).

Then the following holds

∀ε > 0∀n ≥ h(ε, d, K, α)(ρ(x_{n}, f(x_{n})) ≤ ε),

where

h(ε, d, K, α) := α(0, 1) + α̂^{∗}(⌈2d · α(0, 1) · exp(K(M + 1))⌉ − 1, M), with M ∈ IN is such that M ≥ \frac{1+2d}{ε}, α̂^{∗}(0, n) := α̃^{∗}(0, n), α̂^{∗}(i + 1, n) := α̃^{∗}(α̂^{∗}(i, n), n) with α̃^{∗}(i, n) := i + α^{∗}(i, n), α^{∗}(i, n) := α(i + α(0, 1), n) (i, n ∈ IN).

Proof: The sequence (x_{n})_{n∈IN} is bounded, since

∀m, n ∈ IN(ρ(x_{n}, x_{m}) = ρ(x_{n}, (x_{0})_{m}) ≤ d).

By the hypothesis on α, we have that ∑_{s=0}^{α(0,1)−1} λ_{s} ≥ 1. From this it is easy to

see that there is N ∈ IN, N ≤ α(0, 1) − 1 such that

λ_{N} ≥ \frac{1}{α(0, 1)}.

It follows that

(1) ρ(x_{α(0,1)}, f(x_{α(0,1)})) ≤ ρ(x_{N}, f(x_{N})) = \frac{1}{λ_{N}} ρ(x_{N}, x_{N+1}) ≤ d · α(0, 1).

Let μ_{n} = λ_{α(0,1)+n} for all n ∈ IN. It is obvious that (μ_{n})_{n∈IN} is divergent in sum and μ_{n} ≤ 1 − \frac{1}{K} for all n ∈ IN. Let us consider the sequence (y_{n})_{n∈IN} defined by

y_{0} := y := x_{α(0,1)}, y_{n+1} := (1 − μ_{n})y_{n} ⊕ μ_{n}f(y_{n}).

Hence, (y_{n})_{n∈IN} is the Krasnoselski-Mann iteration associated with (μ_{n})_{n∈IN}, starting with x_{α(0,1)}. It follows by an easy induction on n that

y_{n} = x_{α(0,1)+n}, so
∀m, n ∈ IN(ρ(y_{n}, y_{m}) = ρ(x_{α(0,1)+n}, x_{α(0,1)+m}) ≤ d).

Thus, we can apply Proposition 3.4 to get that lim_{n→∞} ρ(y_{n}, f(y_{n})) = 0. It follows that

(2) ∀δ > 0∃N_{δ}∀n ≥ N_{δ}(ρ(y_{n}, f(y_{n})) < δ).

Let y^{∗} := y_{N_{δ}}. Then, by the hypothesis,

∀n ∈ IN(ρ(y_{n}, y_{n}^{∗}) = ρ(x_{α(0,1)+n}, (x_{N_{δ}+α(0,1)})_{n}) ≤ d).

Define for all i, n ∈ IN,

α^{∗}(i, n) := α(i + α(0, 1), n).

It follows immediately that α^{∗}(i, n) ≤ α^{∗}(i + 1, n) and that

∑_{s=i}^{i+α^{∗}(i,n)−1} μ_{s} = ∑_{s=i}^{i+α(i+α(0,1),n)−1} λ_{α(0,1)+s} = ∑_{s=i+α(0,1)}^{i+α(0,1)+α(i+α(0,1),n)−1} λ_{s} ≥ n.

There are satisfied the hypotheses of Theorem 3.9 with μ_{n}, α^{∗}, y, y^{∗} instead of λ_{n}, α, x, x^{∗}, so we can apply it to get

∀ε > 0∀n ≥ h^{∗}(ε, y, d, f, K, α^{∗})(ρ(y_{n}, f(y_{n})) < ρ(y^{∗}, f(y^{∗})) + ε),

where

h^{∗}(ε, y, d, f, K, α^{∗}) := α̂^{∗}(⌈2c(f, y) · exp(K(M + 1))⌉ − · 1, M), where
M ∈ IN is such that M ≥ \frac{1+2d}{ε},
c(f, y) ∈ IR is such that c(f, y) ≥ ρ(y, f(y)).

By (1), we have that

ρ(y, f(y)) = ρ(x_{α(0,1)}, f(x_{α(0,1)})) ≤ d · α(0, 1),

so we can take c(f, y) := d · α(0, 1). We get that

h^{∗}(ε, y, d, f, K, α^{∗}) = α̂^{∗}(⌈2d·α(0, 1)·exp(K(M +1))⌉−1, M) = h^{∗}(ε, d, K, α),

since α^{∗} is defined in terms of α. Applying now (2), it follows that

(3) ∀ε > 0∀n ≥ h^{∗}(ε, d, K, α)(ρ(y_{n}, f(y_{n})) < δ + ε).

Since (3) is true for every δ > 0, we obtain

\begin{matrix}∀ε > 0∀n ≥ h^{∗}(ε, d, K, α)(ρ(y_{n}, f(y_{n})) ≤ ε), that is \\ ∀ε > 0∀n ≥ h^{∗}(ε, d, K, α)(ρ(x_{α(0,1)+n}, f(x_{α(0,1)+n})) ≤ ε). \end{matrix}

Finally, letting h(ε, d, K, α) := α(0, 1) + h^{∗}(ε, d, K, α), we get

∀ε > 0∀n ≥ h(ε, d, K, α)(ρ(x_{n}, f(x_{n})) ≤ ε).

□

As mentioned already, the condition

∀n, k, m ∈ IN(ρ(x_{n}, (x_{k})_{m}) ≤ d)

is equivalent to the boundedness of (x_{n}) by d

∀n, m ∈ IN(ρ(x_{n}, x_{m}) ≤ d)

in the case of constant λ_{n} = λ. Hence we obtain the following strong uniform version of Theorem 2 in [8] (note that Theorem 2 in [8] does not state any uniformity of the convergence at all).

Corollary 3.23 Let (X, ρ, M) be a hyperbolic space, C ⊆ X a non-empty convex subset and f : C → C a directionally nonexpansive mapping. Let d > 0, K ∈ IN, K ≥ 2 and λ ∈ [\frac{1}{K} , 1 − \frac{1}{K}]. Let λ_{n} := λ for all n ∈ IN. Let x ∈ C such that ρ(x_{n}, x_{m}) ≤ d for all m, n ∈ IN. Then the following holds

∀ε > 0∀n ≥ h(ε, d, K)(ρ(x_{n}, f(x_{n})) ≤ ε),

where

h(ε, d, K) := K + K · M · ⌈2d · K · exp(K(M + 1))⌉ and
M ∈ IN, M ≥ \frac{1+2d}{ε}.

Proof: Obviously, (λ_{n})_{n∈IN} is divergent in sum. Define α : IN × IN → IN by

α(i, n) = Kn.

Then α(i, n) = α(i + 1, n) = Kn and

∑_{s=i}^{i+α(i,n)−1} λ_{s} ≥ ∑_{s=i}^{i+α(i,n)−1} \frac{1}{K} = \frac{1}{K} · α(i, n) = n.

It is an easy exercise to see that

α^{∗}(i, n) = α(i + α(0, 1), n) = Kn = α(i, n),
α̃^{∗}(i, n) = α̃(i, n) = i + α(i, n) = i + Kn and
α̂^{∗}(i, n) = α̂(i, n) = K(i + 1)n.

Since λ_{n} = λ for all n ∈ IN, it follows that (x_{k})_{m} = x_{k+m}, hence for all m, n, k ∈ IN,

ρ(x_{n}, (x_{k})_{m}) = ρ(x_{n}, x_{k+m}) ≤ d.

Hence, we can apply Theorem 3.22 to obtain

∀ε > 0∀n ≥ h(ε, d, K, α)(ρ(x_{n}, f(x_{n})) ≤ ε),

where

M ∈ IN is such that M ≥ \frac{1+2d}{ε} and
h(ε, d, K, α) := α(0, 1) + α̂^{∗}(⌈2d · α(0, 1) · exp(K(M + 1))⌉ − 1, M)
= K + K · M · ⌈2d · K · exp(K(M + 1))⌉
= h(ε, d, K).
□

Final Remark: Inspection of the proofs in this paper shows that the only places where we used the requirement (2) from the definition of hyperbolic spaces was in Lemma 3.7 which in turn only was used in Remark 3.10 as well as the proof of Theorem 3.20. Thus all other results in this paper even hold for spaces of hyperbolic type in the sense of [4], i.e. convex metric spaces in the sense of [18].

Acknowledgement

The research of Laurenţiu Leuştean has been supported by a Marie Curie Fellowship of the European Community Programme Improving the Human Research Potential and the Socio-economic Knowledge Base under contract number HPTM-CT-2000-00093 at BRICS, Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation.

References

[1] Baillon, J, Bruck, R.E., The rate of asymptotic regularity is 0(\frac{1}{\sqrt{n}}). Theory and applications of nonlinear operators of accretive and monotone type, Lecture Notes in Pure and Appl. Math. 178, pp. 51-81, Dekker, New York, 1996.

[2] Borwein, J., Reich, S., Shafrir, I., Krasnoselski-Mann iterations in normed spaces. Canad. Math. Bull. 35, pp. 21-28 (1992).

[3] Edelstein, M., O’Brien, R.C., Nonexpansive mappings, asymptotic regularity and successive approximations. J. London Math. Soc. 17, pp. 547-554 (1978).

[4] Goebel, K., Kirk, W.A., Iteration processes for nonexpansive mappings. In: Singh, S.P., Thomeier, S., Watson, B., eds., Topological Methods in Nonlinear Functional Analysis. Contemporary Mathematics 21, AMS, pp. 115-123 (1983)

[5] Goebel, K., Reich, S., Uniform convexity, hyperbolic geometry, and nonexpansive mappings. Monographs and Textbooks in Pure and Applied Mathematics, 83. Marcel Dekker, Inc., New York, ix+170 pp., 1984.

[6] Ishikawa, S., Fixed points and iterations of a nonexpansive mapping in a Banach space. Proc. Amer. Math. Soc. 59, pp. 65-71 (1976).

[7] Kirk, W.A., Krasnosel’skii iteration process in hyperbolic spaces, Numer. Funct. Anal. and Optimiz. 4, pp. 371-381 (1982).

[8] Kirk, W.A., Nonexpansive mappings and asymptotic regularity, Nonlinear Analysis, 40, pp. 323-332, 2000.

[9] Kohlenbach, U., Analysing proofs in analysis. In: W. Hodges, M. Hyland, C. Steinhorn, J. Truss, editors, Logic: from Foundations to Applications. European Logic Colloquium (Keele, 1993), pp. 225–260, Oxford University Press (1996).

[10] Kohlenbach, U., Mathematically strong subsystems of analysis with low rate of growth of provably recursive functionals. Arch. Math. Logic 36, pp. 31–71 (1996).

[11] Kohlenbach, U., Arithmetizing proofs in analysis. In: Larrazabal, J.M., Lascar, D., Mints, G. (eds.), Logic Colloquium ’96, Springer Lecture Notes in Logic 12, pp. 115-158 (1998)

[12] Kohlenbach, U., On the computational content of the Krasnoselski and Ishikawa fixed point theorems. In: Proceedings of the Fourth Workshop on Computability and Complexity in Analysis, J. Blanck, V. Brattka, P. Hertling (eds.), Springer LNCS 2064, pp. 119-145 (2001).

[13] Kohlenbach, U., A quantitative version of a theorem due to Borwein-Reich-Shafrir. Numer. Funct. Anal. and Optimiz. 22, pp. 641-656 (2001).

[14] Kohlenbach, U., Uniform asymptotic regularity for Mann iterates. Submitted.

[15] Krasnoselski, M. A., Two remarks on the method of successive approximation. Usp. Math. Nauk (N.S.) 10, pp. 123-127 (1955) (Russian).

[16] Reich, S., Shafrir, I., Nonexpansive iterations in hyperbolic spaces. Nonlinear Analysis, Theory, Methods and Applications 15, pp. 537-558 (1990).

[17] Reich, S., Zaslavski, A.J., Generic aspects of metric fixed point theory, in W. A. Kirk, B. Sims, editors, Handbook of Metric Fixed Point Theory, Kluwer Academic Publishers, 2001, pp. 557-576.

[18] Takahashi, W., A convexity in metric space and nonexpansive mappings, I. Kodai Math. Se. Rep. 22, pp. 142-149 (1970).

Recent BRICS Report Series Publications

RS-02-28 Ulrich Kohlenbach and Laurenţiu Leuştean. Mann Iterates of Directionally Nonexpansive Mappings in Hyperbolic Spaces. June 2002. 33 pp.

RS-02-27 Anna Östlin and Rasmus Pagh. Simulating Uniform Hashing in Constant Time and Optimal Space. 2002. 11 pp.

RS-02-26 Margarita Korovina. Fixed Points on Abstract Structures without the Equality Test. June 2002.

RS-02-25 Hans Hüttel. Deciding Framed Bisimilarity. May 2002. 20 pp.

RS-02-24 Aske Simon Christensen, Anders Møller, and Michael I. Schwartzbach. Static Analysis of Dynamic XML. May 2002.

RS-02-23 Antonio Di Nola and Laurenţiu Leuştean. Compact Representations of BL-Algebras. May 2002. 25 pp.

RS-02-22 Mogens Nielsen, Catuscia Palamidessi, and Frank D. Valencia. On the Expressive Power of Concurrent Constraint Programming Languages. May 2002. 34 pp.

RS-02-21 ZoltánÉsik and Werner Kuich. Formal Tree Series. April 2002. 66 pp.

RS-02-20 Zoltán Ésik and Kim G. Larsen. Regular Languages Definable by Lindström Quantifiers (Preliminary Version). April 2002. 56 pp.

RS-02-19 Stephen L. Bloom and Zoltán Ésik. An Extension Theorem with an Application to Formal Tree Series. April 2002. 51 pp. To appear in Blute, editor, Category Theory and Computer Science: 9th International Conference, CTCS ’02 Proceedings, ENTCS, 2002 under the title Unique Guarded Fixed Points in an Additive Setting.

RS-02-18 Gerth Stølting Brodal and Rolf Fagerberg. Cache Oblivious Distribution Sweeping. April 2002. To appear in 29th International Colloquium on Automata, Languages, and Programming, ICALP ’02 Proceedings, LNCS, 2002.

RS-02-17 Bolette Ammitzbøll Madsen, Jesper Makholm Nielsen, and Bjarke Skjernaa. On the Number of Maximal Bipartite Subgraphs of a Graph. April 2002. 7 pp.