BRICS RS-02-10 U. Kohlenbach: Uniform Asymptotic Regularity for Mann Iterates BRICS

Basic Research in Computer Science

Uniform Asymptotic Regularity for Mann Iterates

Ulrich Kohlenbach BRICS Report Series RS-02-10 ISSN 0909-0878 March 2002 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2002, Ulrich Kohlenbach.

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/10/

Uniform asymptotic regularity for Mann iterates

Ulrich Kohlenbach

BRICS^{∗}

Department of Computer Science University of Aarhus Ny Munkegade DK-8000 Aarhus C, Denmark kohlenb@brics.dk

Key words: Nonexpansive mappings, fixed point theory, Krasnoselski-Mann iteration,

asymptotic regularity, proof mining Mathematics Subject Classification: 47H09, 47H10, 03F10

Abstract

In [16] we obtained an effective quantitative analysis of a theorem due to Borwein, Reich and Shafrir on the asymptotic behavior of general Krasnoselski-Mann iterations for nonexpansive self-mappings of convex sets C in arbitrary normed spaces. We used this result to obtain a new strong uniform version of Ishikawa’s theorem for bounded C. In this paper we give a qualitative improvement of our result in the unbounded case and prove the uniformity result for the bounded case under the weaker assumption that C contains a point x whose Krasnoselski-Mann iteration (x_{n}) is bounded. We also consider more general iterations for which asymptotic regularity is known only for uniformly convex spaces (Groetsch). We give uniform effective bounds for (an extension of) Groetsch’s theorem which generalize previous results by Kirk/Martinez-Yanez and the author.

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

1 Krasnoselski-Mann iterations

This paper is concerned with quantitative estimates on the rate of asymptotic regularity for so-called Krasnoselski-Mann iterations of nonexpansive functions.

Definition 1.1 Let (X, ∥ · ∥) be a normed linear space and S ⊆ X be a subset of X. A function f : S → S is called nonexpansive if

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

In the following, (X, ∥ · ∥) will be an arbitrary normed linear space, C ⊆ X a nonempty convex subset of X and f : C → C a nonexpansive mapping. We consider the so-called Krasnoselski-Mann iteration starting from x ∈ C

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

where (λ_{k})_{k∈IN} is a sequence of real numbers in [0, 1] (for more information on the relevance of this kind of generalized Krasnoselski ([18]) iterations (see e.g [19],[21],[1],[6]).

Under quite general circumstances the sequence (∥x_{n} −f(x_{n})∥) is known to converge towards r_{C}(f) := inf_{x∈C} ∥x − f(x)∥. In many cases r_{C}(f) = 0 so that from sufficiently

large n on x_{n} is an arbitrarily good approximate fixed point. If this is the case for all starting points x of the iteration, f is called ‘asymptotically regular’. We will consider effective uniform bounds on the rate of convergence towards r_{C}(f) both in the general case as well as in the case where r_{C}(f) = 0.

One simple fact we will use is the following:

Lemma 1.2 If C is bounded, then r_{C}(f) = 0.

Proof: We use the following well-known construction (see e.g. [9](prop.1.4)): f_{t}(x) := (1 − t)f(x) + tc for some c ∈ C and t ∈ (0, 1]. f_{t} : C → C is a contraction and therefore Banach’s fixed point theorem applies. Since we only need approximate fixed points it is not necessary to assume that X is complete or that C is closed. For full details see [17]. □

For the rest of this section we assume (following [1]) that (λ_{k})_{k∈IN} is divergent in sum, which can be expressed (since λ_{k} ≥ 0) as

(A) ∀n, i ∈ IN∃k ∈ IN (∑_{j=i}^{i+k} λ_{j} ≥ n) ,

and that

(B) lim sup_{k→∞} λ_{k} < 1.

Theorem 1.3 ([1]) Suppose that (λ_{k})_{k∈IN} satisfies the conditions (A) and (B). Then the Krasnoselski-Mann iteration (x_{n}) starting from any point x ∈ C satisfies

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

Tother with the previous lemma theorem 2.1 implies the following important result due to Ishikawa [12] (for constant λ_{k} := λ it was independently obtained also in [5]):

Corollary 1.4 ([12],[8],[1]) Under the assumptions of theorem 1.3 plus the additional assumption that C is bounded the following holds:

∀x ∈ C(∥x_{n} − f(x_{n})∥ →^{n→∞} 0).

Using an inequality due to [15] the following lemma was proved in [1] (see also [7]):

Lemma 1.5 Let (x_{n}) be given by (+), then, for all n ≥ 1,

∥x − x_{n}∥ ≥ ∑_{i=0}^{n−1} λ_{i}r_{C}(f).

Remark 1.6 In [1] it is assumed that X is complete and C is closed in order to have Banach’s fixed point theorem available. However, the proof can be rewritten with approximate fixed points instead whose existence follows without these assumptions. Alternatively, one can infer the lemma by applying the one proved in [1] to the completion of X.

Corollary 1.7 ([1]) ^{1} If C contains a point x^{∗} ∈ C such that (x_{n}^{∗}) (as defined in (+)) is bounded, then r_{C}(f) = 0.

As observed in [1], theorem 1.3 combined with the previous lemma allows to derive the conclusion of corollary 1.4 under the weaker assumption that C contains an element whose Krasnoselski-Mann iteration is bounded:

Theorem 1.8 ([1]) Under the assumptions of theorem 1.3 we have: if C contains an x^{∗} such that (x_{n}^{∗}) is bounded, then

∀x ∈ C(∥x_{n} − f(x_{n})∥ →^{n→∞} 0).

1The corollary follows also from [12], see remark 1.9 below.

Remark 1.9 The case where x = x^{∗} in theorem 1.8 is already proved in [12].

In the next section we use a result from [16] to prove a uniform bound on the convergence in theorem 1.8 thereby generalizing a corresponding result for corollary 1.4 from [16]. We also give a qualitative improvement of the quantitative version of theorem 2.1 obtained in [16]. In the final section we prove a new bound on Groetsch’s theorem on the asymptotic regularity in the case of uniformly convex spaces where the conditions (A), (B) on the sequence λ_{s} are replaced by the weaker condition

(C) ∑_{s=0}^{∞} λ_{s}(1 − λ_{s}) = +∞.

2 Uniform bounds on asymptotic regularity

In [16], we obtained the following quantitative version of theorem 1.3:

Theorem 2.1 ([16]) Let (X, ∥ · ∥) be a normed linear space, C ⊆ X a non-empty convex subset and f : C → C a nonexpansive mapping. Let (λ_{k})_{k∈IN} be a sequence in [0, 1] which is divergent in sum and satisfies

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

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

∀i, n ∈ IN(α(i, n) ≤ α(i + 1, n)) and

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

Let (x_{n})_{n∈IN} be the Krasnoselski-Mann iteration

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

starting from x ∈ C. Then the following holds

∀x, x^{∗} ∈ C∀ε > 0∀n ≥ h(ε, x, x^{∗}, f, K, α)(∥x_{n} − f(x_{n})∥ < ∥x^{∗} − f(x^{∗})∥ + ε),

where^{2}

h(ε, x, x^{∗}, f, K, α) := α̂(⌈2∥x − f(x)∥ · exp(K(M + 1))⌉ − · 1, M),
with M := ⌈\frac{1+2∥x−x^{∗}∥}{ε}⌉ and
α̂(0, M) := α̃(0, M), α̂(m + 1, M) := α̃(α̂(m, M), M) with
α̃(m, M) := m + α(m, M) (m ∈ IN)

(Instead of M we may use any upper bound IN ∋ M̃ ≥ \frac{1+2∥x−x^{∗}∥}{ε}). Likewise, ∥x − f(x)∥ may be replaced by any upper bound.)

Remark 2.2 Note that a function α satisfying the conditions of theorem 2.1 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 2.1 holds with h(ε, x, x^{∗}, f, K, β^{+}), where β satisfies (∗).

Corollary 2.3 ([16]) Under the same assumptions as in theorem 2.1 plus the assumption that C has a positive^{3} bounded diameter d(C) < ∞ the following holds:

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

where

h(ε, d(C), K, α) := α̂(⌈2d(C) · exp(K(M + 1))⌉ − 1, M), with M := ⌈\frac{1 + 2d(C)}{ε}⌉

and α̂ as in the previous theorem. The bound h(ε, d(C), K, α) can be replaced also by h(\frac{ε}{d(C)}, 1, K, α).

Instead of d(C) we can use any upper bound d ≥ d(C).

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

3For d(C) = 0 things are trivial.

Remark 2.4 Perhaps the most interesting aspect of corollary 2.3 is that the bound h(ε, d(C), K, α) is independent from x, f and depends only weakly on C, λ_{k} via d resp. α, K. This generalizes uniformity results of [5] and [8] which established independence from x resp. x, f. Only for constant λ, independence from C (except via d) had been established before in [2] where for this special case an optimal quadratic bound was obtained. Our result implies a uniform exponential bound (only depending on ε, d, K) for the much more general case of sequences (λ_{s}) ⊂ [\frac{1}{K} , 1 − \frac{1}{K}], where 2 ≤ K ∈ IN. Already for this case (which still is more restrictive than the general result obtained in corollary 2.3) no effective bound at all was known before (for more information on this see [16]). In contrast to [5] and [8], our proof of corollary 2.3 doesn’t use any functional analytic embeddings but an effective logical analysis of the ineffective proof of (non-uniform) convergence from [1] (see [17] for more information on this kind of logical ‘proof mining’).

We now prove the following strengthened version of corollary 2.3:

Theorem 2.5 Under the assumption of theorem 2.1 the following holds. Let d > 0, x, x^{∗} ∈ C be such that ∀n(∥x_{n}^{∗}∥ ≤ d) and ∥x − x^{∗}∥ ≤ d. Then

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

where

h(ε, d, K, α) := α̂(⌈12d · exp(K(M + 1))⌉ − 1, M),
with M := ⌈\frac{1+6d}{ε}⌉ and α̂ as in theorem 2.1.

The bound h(ε, d(C), K, α) can be replaced also by h(\frac{ε}{d(C)}, 1, K, α).

Proof: Let x^{∗}, x ∈ C such that ∀n(∥x_{n}^{∗}∥ ≤ d) and ∥x − x^{∗}∥ ≤ d. Then

(0) ∀n(∥x^{∗} − x_{n}^{∗}∥ ≤ 2d)

and therefore

(1) ∀n(∥x − x_{n}^{∗}∥ ≤ 3d).

Using the nonexpansivity of f we get

(2) ∀n(∥f(x^{∗}) − f(x_{n}^{∗})∥ ≤ 2d) and ∥f(x^{∗}) − f(x)∥ ≤ d.

By theorem 1.8 we obtain

(3) ∀δ > 0∃n(∥x_{n}^{∗} − f(x_{n}^{∗})∥ ≤ δ).

Thus

(4) \{ \begin{matrix}∥x − f(x)∥ ≤ ∥x − x^{∗}∥ + ∥x^{∗} − x_{n}^{∗}∥ + ∥x_{n}^{∗} − f(x_{n}^{∗})∥ \\ +∥f(x_{n}^{∗}) − f(x^{∗})∥ + ∥f(x^{∗}) − f(x)∥ ≤ 6d + δ. \end{matrix}

So be letting δ tend to 0 we conclude

(5) ∥x − f(x)∥ ≤ 6d.

By (3), let n_{δ} again be such that ∥x_{n_{δ}}^{∗} − f(x_{n_{δ}}^{∗})∥ ≤ δ. Let h(ε, d, K, α) be defined as in the theorem. Now we apply theorem 2.1 to x and x_{n_{δ}}^{∗} and use that because of (1) and (5) we can take 3d resp. 6d as upper bound for ∥x − x_{n_{δ}}^{∗}∥ resp. for ∥x − f(x)∥. This yields

(6) ∀n ≥ h(ε, d, K, α)(∥x_{n} − f(x_{n})∥ ≤ ∥x_{n_{δ}}^{∗} − f(x_{n_{δ}}^{∗})∥ + ε ≤ δ + ε).

By letting δ tend to 0, (6) implies the theorem. □

Remark 2.6 Using a simple renorming argument the dependency of the bound from ε and d can be improved to the dependency on ε/d only: define ∥x∥^{∗} := ∥x∥/d. Then the assumptions of the theorem are satisfied for (X, ∥·∥^{∗}) with d = 1. So by the result we just proved we get that

n ≥ h(ε, 1, K, α) → ∥x_{n} − f(x_{n})∥^{∗} ≤ ε

and hence

n ≥ h(ε/d, 1, α) → ∥x_{n} − f(x_{n})∥ ≤ ε.

Our results from [16] were obtained by applying general results from logic about the extractability of effective data from ineffective proofs to the proof of theorem 2.1 as given in [1] (see [17] for more information on this). To understand the reason for the dependence of the bound in theorem 2.1 (compared to the one in corollary 2.3) from the additional input x^{∗}, let us consider the logical form of the statement of theorem 2.1: when formalized appropriately it translates into

(a) ∀ε > 0∃n ∈ IN∀m ≥ n∀x^{∗} ∈ C(∥x_{m} − f(x_{m})∥ < ∥x^{∗} − f(x^{∗})∥ + ε)

where – since (∥x_{n}−f(x_{n})∥)_{n} is non-increasing (see lemma 3.1 below) – the quantifier ‘∀m ≥ n’ is superfluous, i.e. (a) is equivalent to

(b) ∀ε > 0∃n ∈ IN∀x^{∗} ∈ C(∥x_{n} − f(x_{n})∥ < ∥x^{∗} − f(x^{∗})∥ + ε).

An effective bound on n in (b) would (relatively to the computability of (λ_{s}), f, x, ∥·∥) imply the computability of r_{C} which is unlikely to hold for general C. In order to make the aforementioned logical meta-theorem applicable one has to reverse the quantifier alternation ∃n∀x^{∗} into a ∀∃-alternation. The easiest way to do this is just by replacing it by ‘∀x^{∗}∃n’. This is what we did in [16] thereby making x^{∗} an input for the bound on n:

(c) ∀ε > 0∀x^{∗} ∈ C∃n ∈ IN(∥x_{n} − f(x_{n})∥ < ∥x^{∗} − f(x^{∗})∥ + ε).

Although (c) actually is equivalent to (b) (and hence to (a)), and so still a faithful formalization of theorem 2.1, there is no effective way to get from a bound on n in (c) one on n in (b). A more subtle variant is to replace (b) by

(d) ∀ε > 0∀y(·) ⊂ C∃n ∈ IN(∥x_{n} − f(x_{n})∥ < ∥y(n) − f(y(n))∥ + ε),

where y(·) is an arbitrary sequence in C.^{4} Obviously, any bound for (d) yields also one for (c) just by applying it to the constant sequence y(n) := x^{∗}. The next theorem shows that (as guaranteed by our general logical results) an effective bound for n in (d) can indeed be obtained. It provides an upper bound for an n at which the sequence (x_{n}) ‘catches up’ (with an error of at most ε) with the arbitrarily given sequence y(·) w.r.t. its approximate fixed point behaviour:

Theorem 2.7 Under the same assumptions as in theorem 2.1 the following holds:

∀x ∈ C, y(·) ⊂ C∀ε > 0∃n ≤ j(ε, x, y(·), f, K, α)(∥x_{n}−f(x_{n})∥ < ∥y(n)−f(y(n))∥+ε),

where (omitting the arguments f, K, α for better readability)

j(ε, x, y(·)) := max_{i≤k(ε,x,y(·))} h(ε/2, x, y(i))

with

k(ε, x, y(·)) := max_{j<N} g^{j}(0), g(n) := h(ε/2, x, y(n)), N := ⌈\frac{2∥y(0) − f(y(0))∥}{ε}⌉ .

Here h is the bound from theorem 2.1 and g^{n}(0) is defined recursively: g^{0}(0) := 0, g^{n+1}(0) := g(g^{n}(0)). Instead of N, we can take any integer upper bound for 2∥y(0) − f(y(0))∥/ε.

4We write y(·) in order to avoid confusion with (y_{n}) which denotes the Krasnoselski-Mann iteration starting from y.

Proof: By theorem 2.1 we have

(1) ∀k ∈ IN(∥x_{g(k)} − f(x_{g(k)})∥ < ∥y(k) − f(y(k))∥ + \frac{ε}{2}),

where

g(k) := h(\frac{ε}{2}, x, y(k), f, K, α).

We now construct (uniformly in ε, x, y(·), f, K, α) a k ∈ IN such that

(2) ∃i ≤ k(∥y(i) − f(y(i))∥ ≤ ∥y(g(i)) − f(y(g(i)))∥ + \frac{ε}{2}).

(1) and (2) imply

(3) ∃i ≤ k(∥x_{g(i)} − f(x_{g(i)})∥ < ∥y(g(i)) − f(y(g(i)))∥ + ε)

so that the theorem is satisfied with

j(ε, x, y(·), f, K, α) := max_{i≤k} g(i).

Define

(4) k := max_{j<N} g^{j}(0), where IN ∋ N ≥ ⌈\frac{2∥y(0) − f(y(0))∥}{ε}⌉ .

Claim:

∃j < N(∥y(g^{j}(0)) − f(y(g^{j}(0)))∥ ≤ ∥y(g^{j+1}(0)) − f(y(g^{j+1}(0)))∥ + \frac{ε}{2}).

Proof of claim: Suppose not, then

∀j < N(∥y(g^{j+1}(0)) − f(y(g^{j+1}(0)))∥ < ∥y(g^{j}(0)) − f(y(g^{j}(0)))∥ − \frac{ε}{2})

and therefore

∥y(g^{N}(0)) − f(y(g^{N}(0)))∥ < ∥y(0) − f(y(0))∥ − N · \frac{ε}{2} ≤ 0

which is a contradiction. By the claim, (2) is satisfied with k as defined in (4). □

Remark 2.8 Again, the most interesting aspect of the rather complicated bound in theorem 2.7 is its limited dependence on the various parameters: j is independent of C and depends on x, y(·), f only via upper bounds d ≥ ∥x−f(x)∥ and M(n) ≥ ∥x−y(n)∥ (for all n). This follows from the fact that because of

\begin{matrix}∥y(0) − f(y(0))∥ ≤ ∥y(0) − x∥ + ∥x − f(x)∥ + ∥f(x) − f(y(0))∥ \\ ≤ 2∥y(0) − x∥ + ∥x − f(x)∥ ≤ 2M(0) + d \end{matrix}

one gets a bound on ∥y(0) − f(y(0))∥ in terms of M(0) and d as well. Moreover, the bound depends on (λ_{k}) only via the rather general inputs α, K.

3 The uniformly convex case

The assumptions (A), (B) on the sequence λ_{k} in [0, 1] made in Ishikawa’s paper are still the most general ones for which asymptotic regularity has been proved for arbitrary normed spaces. In [2] it is conjectured that Ishikawa’s theorem holds true if (A), (B) are replaced by the following weaker condition which is symmetric w.r.t. λ_{k} and 1 − λ_{k} :

(C) ∑_{s=0}^{∞} λ_{s}(1 − λ_{s}) = +∞.

For the case of uniformly convex normed spaces, this has been proved by Groetsch [10] (see also [20]).^{5} In this section we give a uniform quantitative bound on (a generalization of) Groetsch’s theorem. The following easy lemma holds in arbitrary normed linear spaces (X, ∥ · ∥):

Lemma 3.1 Let C ⊂ X be convex, (λ_{s}) ⊂ [0, 1] and f : C → C nonexpansive. Then ∥x_{n+1} − f(x_{n+1})∥ ≤ ∥x_{n} − f(x_{n})∥ for all n.

Definition 3.2 ([4]) A normed linear space (X, ∥ · ∥) is uniformly convex if

∀ε > 0∃δ > 0∀x, y ∈ X(∥x∥, ∥y∥ ≤ 1 ∧ ∥x − y∥ ≥ ε → ∥\frac{1}{2}(x + y)∥ ≤ 1 − δ).

A function η : (0, 2] → (0, 1] providing such a δ := η(ε) > 0 for given ε > 0 is called a modulus of uniform convexity.

5For recent applications of Groetsch’s theorem to elliptic Cauchy problems see [6].

Lemma 3.3 ([10]) Let (X, ∥ · ∥) be uniformly convex with modulus η. If ∥x∥, ∥y∥ ≤ 1 and ∥x − y∥ ≥ ε > 0, then

∥λx + (1 − λ)y∥ ≤ 1 − 2λ(1 − λ)η(ε)

for 0 ≤ λ ≤ 1.

Groetsch’s theorem ([10]) states that in uniformly convex spaces

∥x_{n} − f(x_{n})∥ →^{n→∞} 0

holds if (λ_{s}) satisfies the condition (C) and f has a fixed point in C. We now give a quantitative version of a strengthening of Groetsch’s theorem which only assumes the existence of approximate fixed points in some neighborhood of x:

Theorem 3.4 Let (X, ∥ · ∥) be a uniformly convex normed linear space with modulus of uniform convexity η, d > 0, C ⊆ X a (non-empty) convex subset, f : C → C nonexpansive and (λ_{k}) ⊂ [0, 1] and γ : IN → IN such that

∀n ∈ IN(∑_{s=0}^{γ(n)} λ_{s}(1 − λ_{s}) ≥ n).

Then for all x ∈ C such that

∀ε > 0∃y ∈ C(∥x − y∥ ≤ d ∧ ∥y − f(y)∥ < ε)

one has

∀ε > 0∀k ≥ h(ε, d, γ)(∥x_{k} − f(x_{k})∥ ≤ ε),

where h(ε, d, γ) := γ (\frac{3(d+1)}{2ε·η( \frac{ε}{d+1} )}) for ε < 2d and h(ε, d) := 0 otherwise.

Moreover, if η(ε) can be written as η(ε) = ε · η̃(ε) with

(∗) ∀ε_{1}, ε_{2} ∈ (0, 2](ε_{1} ≥ ε_{2} → η̃(ε_{1}) ≥ η̃(ε_{2})),

then the bound h(ε, d, γ) can be replaced (for ε < 2d) by

h̃(ε, d, γ) := γ (\frac{d + 1}{2ε · η̃(\frac{ε}{d+1})}) .

Proof: The case ε ≥ 2d is trivial as the assumption on x implies that ∥x−f(x)∥ ≤ 2d. So we may assume that ε < 2d. Let δ > 0 be such that δ < min(1/(2h(ε, d, γ) + 2), ε/3) and let y ∈ C be point satisfying

(0) ∥y − f(y)∥ < δ ∧ ∥x − y∥ ≤ d.

Define

n_{ε} := γ (\frac{3(d + 1)}{2ε · η(ε/(d + 1))}) .

Since for all k (using that f is nonexpansive)

∥x_{k+1} − y∥ =
∥(1 − λ_{k})x_{k} + λ_{k}f(x_{k})) − y∥ = ∥(1 − λ_{k})(x_{k} − y) + λ_{k}(f(x_{k}) − y)∥ ≤
∥(1 − λ_{k})(x_{k} − y)∥ + ∥λ_{k}(f(x_{k}) − f(y))∥ + λ_{k}∥f(y) − y∥ ≤ ∥x_{k} − y∥ + δ

we have

(1) ∀k ≤ n_{ε}(∥x_{k} − y∥ ≤ ∥x − y∥ + kδ ≤ d + \frac{1}{2}).

Assume that k ≤ n_{ε} and

(2) ∥x_{k} − y∥ ≥ \frac{ε}{3} and

(3) ∥x_{k} − f(x_{k})∥ = ∥(x_{k} − y) − (f(x_{k}) − y)∥ > ε.

Then

(4) ∥\frac{x_{k} − y}{∥x_{k} − y∥ + δ} − \frac{f(x_{k}) − y}{∥x_{k} − y∥ + δ} ∥ > \frac{ε}{∥x_{k} − y∥ + δ} ≥^{(1)} \frac{ε}{d + 1}.

Because of

(5) ∥f(x_{k}) − y∥ ≤^{(0)} ∥f(x_{k}) − f(y)∥ + δ ≤ ∥x_{k} − y∥ + δ,

we have

(6) ∥\frac{x_{k} − y}{∥x_{k} − y∥ + δ} ∥ , ∥\frac{f(x_{k}) − y}{∥x_{k} − y∥ + δ} ∥ ≤ 1

and therefore by lemma 3.3

(7) ∥(1 − λ_{k}) (\frac{x_{k} − y}{∥x_{k} − y∥ + δ} ) + λ_{k} (\frac{f(x_{k}) − y}{∥x_{k} − y∥ + δ} )∥ ≤ 1 − 2λ_{k}(1 − λ_{k})η(ε/(d + 1)).

Hence

(8) \{ \begin{matrix}∥x_{k+1} − y∥ = \\ ∥(1 − λ_{k})x_{k} + λ_{k}f(x_{k})) − y∥ = ∥(1 − λ_{k})(x_{k} − y) + λ_{k}(f(x_{k}) − y)∥ ≤ \\ ∥x_{k} − y∥ + δ − (∥x_{k} − y∥ + δ)2λ_{k}(1 − λ_{k}) · η(ε/(d + 1)) ≤^{(2)} \\ ∥x_{k} − y∥ + δ − \frac{2ε}{3}λ_{k}(1 − λ_{k}) · η(ε/(d + 1)). \end{matrix}

If (2), (3) both hold for all k ≤ n_{ε}, then (8) yields

(9) \{ \begin{matrix}∥x_{n_{ε}+1} − y∥ ≤ ∥x_{0} − y∥ − \frac{2ε}{3} · η(ε/(d + 1)) · ∑_{s=0}^{n_{ε}} λ_{s}(1 − λ_{s}) + (n_{ε} + 1) · δ \\ ≤ ∥x_{0} − y∥ − (d + 1) + \frac{1}{2} < ∥x_{0} − y∥ − d ≤^{(0)} 0, \end{matrix}

which is a contradiction. Hence

(10) ∃k ≤ n_{ε}(∥x_{k} − y∥ ≤ \frac{ε}{3} ∨ ∥x_{k} − f(x_{k})∥ ≤ ε).

By the choice of δ,(0) and the nonexpansivity of f, the first disjunct implies ∥f(x_{k})− x_{k}∥ ≤ ε too and so by lemma 3.1

(11) ∀k ≥ n_{ε}(∥x_{k} − f(x_{k})∥ ≤ ε).

The last claim in the theorem follows by choosing y ∈ C as a δ-fixed point of f with δ < min(1/(2h̃(ε, d, γ) + 2), ε/3), replacing n_{ε} by ñ_{ε} := h̃(ε, d, γ) and the following modifications of (7), (8) to

(7)^{∗} \{ \begin{matrix}∥(1 − λ_{k}) (\frac{x_{k}−y}{∥x_{k}−y∥+δ} ) + λ_{k} (\frac{f(x_{k})−y}{∥x_{k}−y∥+δ} )∥ ≤ \\ 1 − 2λ_{k}(1 − λ_{k})η(ε/(∥x_{k} − y∥ + δ)). \end{matrix}

(8)^{∗} \{ \begin{matrix}∥x_{k+1} − y∥ = \\ ∥(1 − λ_{k})x_{k} + λ_{k}f(x_{k})) − y∥ = ∥(1 − λ_{k})(x_{k} − y) + λ_{k}(f(x_{k}) − y)∥ ≤ \\ ∥x_{k} − y∥ + δ − (∥x_{k} − y∥ + δ)2λ_{k}(1 − λ_{k}) · η(ε/(∥x_{k} − y∥ + δ)) ≤ \\ ∥x_{k} − y∥ + δ − 2ελ_{k}(1 − λ_{k}) · η̃(ε/(∥x_{k} − y∥ + δ)) ≤^{(∗)} \\ ∥x_{k} − y∥ + δ − 2ελ_{k}(1 − λ_{k}) · η̃(ε/(d + 1)) \end{matrix}

(note that we can apply η to ε/(∥x_{k} − y∥ + δ) since (3) and

∥f(x_{k}) − y∥ ≤^{(1)} ∥f(x_{k}) − f(y)∥ + δ ≤ ∥x_{k} − y∥ + δ

imply

ε ≤ ∥x_{k} − y∥ + ∥f(x_{k}) − y∥ ≤ 2(∥x_{k} − y∥ + δ)

and therefore

ε/(∥x_{k} − y∥ + δ) ∈ (0, 2]).
⊣

Corollary 3.5 If C has bounded diameter d_{C}, theorem 3.4 holds with d_{C} instead of d for all x ∈ C.

Proof: Follows from theorem 3.4 and lemma 1.2. □

Remark 3.6 Note that the proof of the corollary only uses the elementary lemma 1.2 but not the deep Browder-Göhde-Kirk fixed point theorem which implies the existence of a fixed point of f in C under the assumptions of the corollary (if, moreover, X is complete and C is closed).

Examples: It is well-known that the Banach spaces L_{p} with 1 < p < ∞ are uniformly convex ([4], see also [14]). For p ≥ 2, \frac{ε^{p}}{p2^{p}} is a modulus of convexity ([11], see also [17]). Since

\frac{ε^{p}}{p2^{p}} = ε · η̃_{p}(ε)

we get

η̃_{p}(ε) = \frac{ε^{p−1}}{p2^{p}}

satisfying (∗) in the theorem above. So – disregarding constants depending on p, d only – we get γ(ε^{p}) as rate of asymptotic regularity for L_{p}. For the case X := IR with the Euclidean norm we can choose η̃(ε) := \frac{1}{2} (since ε/2 is a modulus of convexity) which gives the rate γ(ε). For L_{2} and IR these rates are known to be optimal even in the case of constant λ_{k} := \frac{1}{2}, where they were first obtained in [13].

Remark 3.7 In [17] we already treated the case λ_{k} = \frac{1}{2} for uniformly convex spaces by a logical analysis of the usual asymptotic regularity proof which goes back to [18] for the case of compact C and [3] for the case of bounded and closed C. The anlysis of that proof yielded basically the same bound as was obtained in [13] (for the case of general uniformly convex spaces) but with a completely elementary proof (since only approximate fixed points are used) whereas the proof in [13] is based on the Browder-Goehde-Kirk fixed point theorem (to get a real fixed point). We also showed in [17] that a logically motivated modification of that proof allows to take into account the property (∗) from the theorem above which is shared by many moduli of convexity. This yielded in the special cases of X = L_{p} and X = IR the improved bounds mentioned above. We subsequently learned that the simlarly modified proof was used in [10] to prove asymptotic regularity for general sequences (λ_{k}) satisfying condition (C) which suggested the possibility to extend our quantitative analysis from [17] to this case. Our proof above shows that this indeed can be carried out. Again we don’t need the existence of an actual fixed point (but only approximate fixed points) which allows to state the result in greater generality as Groetsch’s theorem.

References

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

[2] 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.

[3] Browder, F.E., Petryshyn, W.V., The solution by iteration of nonlinear functional equations in Banach spaces. Bull. Amer. Math. Soc. 72, pp. 571-575 (1966).

[4] Clarkson, J.A., Uniformly convex spaces. Trans. Amer. Math. Soc. 40, pp. 396-414 (1936).

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

[6] Engl, H.W., Leitão, A., A Mann interative regularization method for elliptic Cauchy problems. Numer. Funct. Anal. and Optimiz. 22. pp. 861-884 (2001).

[7] Fujihara, T., Asymptotic behavior of nonexpansive mappings in Banach spaces. Tokyo J. Math. 7, pp. 119-128 (1984).

[8] 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).

[9] 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.

[10] Groetsch, C.W., A note on segmenting Mann iterates. J. of Math. Anal. and Appl. 40, pp. 369-372 (1972).

[11] Hanner, O., On the uniform convexity of L_{p} and l_{p}. Ark. Mat. 3, pp. 239-244 (1956).

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

[13] Kirk, W.A., Martinez-Yanez, C., Approximate fixed points for nonexpansive mappings in uniformly convex spaces. Annales Polonici Mathematici 51, pp. 189-193 (1990).

[14] Koethe, G., Topoplogische Lineare Räume. Springer-Verlag Berlin-Göttingen-Heidelberg, VI+456 pp., 1960.

[15] Kohlberg, E., Neyman, A., Asymptotic behavior of nonexpansive mappings in normed spaces. Israel J. Math. 38, pp. 269-275 (1981).

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

[17] 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).

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

[19] Mann, W.R., Mean value methods in iteration. Proc. Amer. Math. Soc. 4, pp. 506-510 (1953).

[20] Reich, S., Weak convergence theorems for nonexpansive mappings in Banach spaces. J. Math. Anal. Appl. 67, pp. 274-276 (1979).

[21] Rhoades, B.E., Fixed point iterations using infinite matrices. Trans. Amer. Math. Soc. 196, pp. 161-176 (1974).

Recent BRICS Report Series Publications

RS-02-10 Ulrich Kohlenbach. Uniform Asymptotic Regularity for Mann Iterates. March 2002. 17 pp.

RS-02-9 Anna Östlin and Rasmus Pagh. One-Probe Search. February

2002.

RS-02-8 Ronald Cramer and Serge Fehr. Optimal Black-Box Secret Sharing over Arbitrary Abelian Groups. February 2002.

RS-02-7 Anna Ingólfsdóttir, Anders Lyhne Christensen, Jens Alsted Hansen, Jacob Johnsen, John Knudsen, and Jacob Illum Rasmussen. A Formalization of Linkage Analysis. February 2002. vi+109 pp.

RS-02-6 Luca Aceto, Zoltán Ésik, and Anna Ingólfsdóttir. Equational Axioms for Probabilistic Bisimilarity (Preliminary Report). February 2002. 22 pp.

RS-02-5 Federico Crazzolara and Glynn Winskel. Composing Strand Spaces. February 2002. 30 pp.

RS-02-4 Olivier Danvy and Lasse R. Nielsen. Syntactic Theories in Practice. January 2002. 34 pp. This revised report supersedes the earlier BRICS report RS-01-31.

RS-02-3 Olivier Danvy and Lasse R. Nielsen. On One-Pass CPS Transformations. January 2002. 18 pp.

RS-02-2 Lasse R. Nielsen. A Simple Correctness Proof of the Direct-Style Transformation. January 2002.

RS-02-1 Claus Brabrand, Anders Møller, and Michael I. Schwartzbach. The <bigwig> Project. January 2002. 36 pp. This revised report supersedes the earlier BRICS report RS-00-42.

RS-01-55 Daniel Damian and Olivier Danvy. A Simple CPS Transformation of Control-Flow Information. December 2001.

RS-01-54 Daniel Damian and Olivier Danvy. Syntactic Accidents in Program Analysis: On the Impact of the CPS Transformation. December 2001. 41 pp. To appear in the Journal of Functional Programming. This report supersedes the earlier BRICS report RS-00-15.