BRICS RS-03-51 Kohlenbach & Lambov: Bounds on Iterations of Asymptotically Quasi-Nonexpansive Mappings BRICS

Basic Research in Computer Science

Bounds on Iterations of Asymptotically Quasi-Nonexpansive Mappings

Ulrich Kohlenbach Branimir Lambov BRICS Report Series RS-03-51 ISSN 0909-0878 December 2003 Copyright \begin{matrix}c \\ ◯ \end{matrix} 2003, Ulrich Kohlenbach & Branimir Lambov.

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/03/51/

Bounds on iterations of asymptotically quasi-nonexpansive mappings

Ulrich Kohlenbach^{∗} and Branimir Lambov

BRICS^{†}

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

AMS Classification: 47H09, 47H10, 03F10, 03F60

Abstract

This paper establishes explicit quantitative bounds on the computation of approximate fixed points of asymptotically (quasi-) nonexpansive mappings f by means of iterative processes. Here f : C → C is a selfmapping of a convex subset C ⊆ X of a uniformly convex normed space X. We consider general Krasnoselski-Mann iterations with and without error terms. As a consequence of our quantitative analysis we also get new qualitative results which show that the assumption on the existence of fixed points of f can be replaced by the existence of approximate fixed points only. We explain how the existence of effective uniform bounds in this context can be inferred already a-priorily by a logical metatheorem recently proved by the first author. Our bounds were in fact found with the help of the general logical machinery behind the proof of this metatheorem. The proofs we present here are, however, completely selfcontained and do not require any tools from logic.

∗ Partially supported by the Danish Natural Science Research Council, Grant no. 21-02-0474.

† Basic Research in Computer Science (www.brics.dk), funded by the Danish National Research Foundation.

1 Introduction

This paper is part of a series of papers which apply tools from mathematical logic to metric fixed point theory ([12, 13, 14, 16] and – for the logical background – [15, 17]). These applications are concerned with both quantitative as well as qualitative aspects of the asymptotic regularity of various iterations of nonexpansive and other mappings in hyperbolic and normed spaces. More specifically, we are interested in effective rates of convergence which are uniform w.r.t. many of the parameters involved. Recently ([15]), the first author proved general logical metatheorems which a-priorily guarantee the existence of such uniform bounds if the convergence statement proved has a certain logical form, and the proof can be carried out in a certain (rather flexible) formal setting. The proofs of these metatheorems are constructive and allow one to actually extract effective bounds from a given ineffective convergence proof. In this paper we apply this methodology to Krasnoselski-Mann iterations of asymptotically quasi-nonexpansive mappings in uniformly convex normed spaces. We first show how this context fits within the scope of the metatheorems from [15] and then actually construct uniform effective bounds in the main part of this paper which is selfcontained and does not rely on any prerequisites from logic. In the following, let (X, ∥ · ∥) be a uniformly convex (real) normed linear space and C ⊆ X a nonempty convex subset. The class of asymptotically nonexpansive mappings f : C → C was introduced in [8]:

Definition 1.1 f : C → C is said to be asymptotically nonexpansive with sequence (k_{n}) ∈ [0, ∞)^{IN} if lim_{n→∞} k_{n} = 0 and

∥f^{n}(x) − f^{n}(y)∥ ≤ (1 + k_{n})∥x − y∥, ∀n ∈ IN, ∀x, y ∈ C.

Definition 1.2 ([26]) f : C → C is said to be uniformly λ-Lipschitzian (λ > 0) if

∥f^{n}(x) − f^{n}(y)∥ ≤ λ∥x − y∥, ∀n ∈ IN, ∀x, y ∈ C.

In the following we use the notation F ix(f) := {p ∈ C : f(p) = p}. The concept of quasi-nonexpansive functions was introduced in [6] (based on a similar concept due to [4, 5]):

Definition 1.3 f : C → C is quasi-nonexpansive if

∥f(x) − p∥ ≤ ∥x − p∥, ∀x ∈ C, ∀p ∈ F ix(f).

Finally, combining the notions of asymptotically nonexpansive mappings and quasi-nonexpansive mappings we obtain the concept of asymptotically quasi-non-expansive mappings first studied in [29] and [20] and more recently in [22, 23, 24]:

Definition 1.4 f : C → C is asymptotically quasi-nonexpansive with sequence k_{n} ∈ [0, ∞)^{IN} if lim_{n→∞} k_{n} = 0 and

∥f^{n}(x) − p∥ ≤ (1 + k_{n})∥x − p∥, ∀n ∈ IN, ∀x ∈ X, ∀p ∈ F ix(f).

In the context of asymptotically (quasi-)nonexpansive mappings f : C → C the so-called Krasnoselski-Mann iteration is defined as follows

x_{0} := x ∈ C, x_{n+1} := (1 − α_{n})x_{n} + α_{n}f^{n}(x_{n}),

where (α_{n}) ∈ [0, 1]^{IN}. We will also consider Krasnoselski-Mann iterations with error terms

x_{0} := x ∈ C, x_{n+1} := α_{n}x_{n} + β_{n}f^{n}(x_{n}) + γ_{n}u_{n},  (1)

where α_{n}, β_{n}, γ_{n} ∈ [0, 1] with α_{n} + β_{n} + γ_{n} = 1 and u_{n} ∈ C for all n ∈ IN (this types of error terms was first considered in [31]).

In this paper we study uniform quantitative versions as well as qualitative improvements of the following theorem which itself seems to be new (though kind of implicit in the literature, see below):

Theorem 1.5 Let (X, ∥·∥) be a uniformly convex (real) normed linear space and C be a convex subset of X. Let (k_{n}) be a sequence in IR_{+} with ∑ k_{n} < ∞. Let k ∈ IN and α_{n}, β_{n}, γ_{n} ∈ [0, 1] such that 1/k ≤ β_{n} ≤ 1−1/k, α_{n}+β_{n}+γ_{n} = 1 and ∑ γ_{n} < ∞. Let f : C → C a uniformly Lipschitz continuous function such that there exists a p ∈ F ix(f) with

∀x ∈ C∀n ∈ IN(∥f^{n}(x) − p∥ ≤ (1 + k_{n})∥x − p∥).

Define

x_{0} := x ∈ C, x_{n+1} := α_{n}x_{n} + β_{n}f^{n}(x_{n}) + γ_{n}u_{n},

where (u_{n}) is a bounded sequence in C. Then the following holds:

∥x_{n} − f(x_{n})∥ → 0.

Corollary 1.6 Let (α_{n}), (β_{n}), (γ_{n}), (k_{n}), (u_{n}), k as well as (X, ∥ · ∥), C as in theorem 1.5. If f : C → C is uniformly Lipschitzian and asymptotically quasi-nonexpansive with sequence (k_{n}) and F ix(f) ≠ ∅, then ∥x_{n}−f(x_{n})∥ → 0.

If f : C → C is asymptotically nonexpansive with a sequence (k_{n}) ∈ IR_{+} such that ∑ k_{n} < ∞ then f automatically is uniformly Lipschitz continuous hence corollary 1.6 implies:

Corollary 1.7 Let (α_{n}), (β_{n}), (γ_{n}), (k_{n}), (u_{n}), (X, ∥·∥), C as in theorem 1.5. If f : C → C is asymptotically nonexpansive with sequence (k_{n}) and F ix(f) ≠ ∅, then ∥x_{n} − f(x_{n})∥ → 0.

Corollary 1.8 Let (X, ∥ · ∥) be a uniformly convex Banach space, C ⊂ X a (nonempty) bounded closed convex subset (α_{n}) ∈ [1/k, 1 − 1/k]^{IN} for some k ∈ IN, f : C → C asymptotically nonexpansive with sequence (k_{n}) such that ∑ k_{n} < ∞ and

x_{0} := x ∈ C, x_{n+1} := α_{n}x_{n} + (1 − α_{n})f^{n}(x_{n}).

Then ∥x_{n} − f(x_{n})∥ → 0.

Proof Corollary 1.8 follows from corollary 1.7 by omitting the error term (i.e. taking an arbitrary sequence (u_{n}) in C with γ_{n} = 0) and using a theorem from [8] stating that asymptotically nonexpansive mappings f : C → C always have fixed points (under the given assumptions on X, C). •

The proof of theorem 1.5 is ineffective and the conclusion ‘∥x_{n}−f(x_{n})∥ → 0’, i.e.

∀l ∈ IN∃n ∈ IN∀m ∈ IN(∥x_{n+m} − f(x_{n+m})∥ < 2^{−l})  (2)

has too complicated a logical form as for our metatheorems to guarantee a computable bound on ‘∃n ∈ IN’, i.e. a computable rate of convergence. Nevertheless, (2) is (non-constructively) equivalent to

∀l ∈ IN∀g ∈ IN^{IN}∃n ∈ IN(∥x_{n+g(n)} − f(x_{n+g(n)}∥ < 2^{−l})  (3)

which does have the required logical form so that we can extract a computable bound Φ on ‘∃n’ with g as an additional argument of the bound Φ. The transformed version (3) of (2) is well-known in logic and called the Herbrand normal form of (2). Whereas (3) trivially follows from (2), the proof of the converse is ineffective.^{1} Hence an effective bound on ‘∃n’ in (3)’ does not lead to an effective bound on ‘∃n’ in (2) unless the sequence (∥x_{n} − f(x_{n})∥) is nonincreasing (where this follows already from the special case where g ≡ 0) which is e.g. the case for nonexpansive functions f. Actually, a slightly more flexible form of (3) still has a the required logical structure^{2}

∀l ∈ IN∀g ∈ IN^{IN}∃n ∈ IN∀m ∈ [n, n + g(n)](∥x_{m} − f(x_{m})∥ < 2^{−l})

and we will focus on effective bound Φ(l, g) on this ‘∃n’. In practice, it will be mostly the special case where g ≡ 0, i.e.

∀l ∈ IN∃n ≤ Φ(l, 0)(∥x_{n} − f(x_{n})∥ < 2^{−l})

which is of relevance. However, this will not always be sufficient. On general logical grounds though, namely the soundness of the so-called monotone functional interpretation on which our metatheorems are based and the fact that a bound on (3) realizes the monotone functional interpretation of (the Gödel negative translation of) (2), it follows that a bound for general g is sufficient for a quantitative analysis of any use of theorem 1.5 in a proof of a ∀∃-consequence. Our bounds seem to be (already in the case of asymptotically nonexpansive mappings) the only known general quantitative results of that kind (see e.g. [2] for a discussion of the lack of quantitative results in this context).

1Suppose (2) fails for l ∈ IN. Then (3) fails for the same l if we take g(n) := min m(∥x_{n+m} − f(x_{n+m})∥ ≥ 2^{−l}).

2Here and below we write m ∈ [n, n + g(n)] for m ∈ IN ∧ m ∈ [n, n + g(n)].

The qualitative improvement of theorem 1.5 which is obtained via our quantitative analysis consists in the possibility to replace in order to show ∥x_{n} − f(x_{n})∥ → 0 for a given x ∈ C the assumption

∃p ∈ F ix(f)∀y ∈ C∀n ∈ IN(∥f^{n}(y) − p∥ ≤ (1 + k_{n})∥y − p∥)

by

∃d ∈ IN∀ε > 0∃p_{ε} ∈ F ix_{ε}(x, d, f)∀y ∈ C, n ∈ IN
(∥f^{n}(y) − f^{n}(p_{ε})∥ ≤ (1 + k_{n})∥y − p_{ε}∥),

where

F ix_{ε}(x, d, f) := {p ∈ C : ∥x − p∥ ≤ d ∧ ∥f(p) − p∥ ≤ ε}.

This, of course, is of interest mainly for asymptotically nonexpansive mappings where it replaces the assumption that F ix(f) ≠ ∅ by

∀x ∈ C∃d ∈ IN∀ε > 0(F ix_{ε}(x, d, f) ≠ ∅).

With the stronger assumption on (k_{n}) that ∑((k_{n} + 1)^{r} − 1) < ∞ for some r > 1, corollary 1.8 is proved in [25]. For Hilbert spaces X and r = 2 corollary 1.8 is already due to [26]. For Banach spaces satisfying Opial’s condition ([21]) and ∑ k_{n} < ∞, corollary 1.8 follows from [28] (note, however, that Opial’s condition is not even satisfied for L_{p} except for p = 2).^{3} The result in the literature most close to corollary 1.6 is the main theorem in [24] whose proof technique – together with an argument reminiscent of a lemma in [26] – we actually use to prove theorem 1.5 and corollary 1.6. The theorem in [24] is concerned with the convergence of (x_{n}) towards a fixed point of f and the assumption of C being compact.^{4} Without that assumption but assuming that F ix(f) ≠ ∅ the proof actually yields that

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

3For some generalizations of the main results of [28] see also [30].

4[24] actually considers more general Ishikawa-type iterations. In order to keep the technicalities of our paper down we confine ourselves here to the Krasnoselski-Mann type iterations.

which together with an argument from [26] gives

lim_{n→∞} ∥x_{n} − f(x_{n})∥ = 0.

[24] in turn relies on [27] (see also [30]).

2 A logical metatheorem with applications in fixed point theory

This section – which is independent from the main part of this paper – requires some background in logic as developed in [15]. In [15], we have defined a formal system A^{ω}[X, ∥ · ∥, C, η] for classical analysis over a uniformly convex normed space (X, ∥ · ∥) (with a modulus of uniform convexity η) and a bounded convex subset C ⊂ X. The system is formulated in the language of functionals of finite type over the types X (for variables ranging over Xelements) and IN by closure of these types under function space formation: with ρ, τ being types, ρ → τ is the type of all functions mapping objects of type ρ to objects of type τ. The type C is treated as a subtype of X. The system contains full countable choice (and hence full comprehension over integers) and even full dependent choice. It is well known in logic that such a system allows to formalize most of existing proofs in analysis. Whereas elements of X are treated as ‘primitive’ objects (so-called ‘atoms’) real numbers are – as usual – explicitly represented via Cauchy sequences of rationals numbers with fixed rate of convergence. Both equality =_{IR} on IR as well as equality =_{X} on X are defined notions where x =_{X} y :≡ ∥x−y∥ =_{IR} 0. There are some subtleties, though, which have to do with the restricted availability of extensionality of functions w.r.t. =_{X} . These issues, however, are trivial in our applications in this paper as full extensionality of the functions we will consider follows from the continuity assumptions made (see below).

Definition 2.1 A formula F is called ∀-formula (resp. ∃-formula) if it has the form F ≡ ∀\underline{a}\underline{σ}F_{qf}(\underline{a}) (resp. F ≡ ∃\underline{a}\underline{σ}F_{qf}(\underline{a})) where \underline{a}\underline{σ} = a_{1}^{σ_{1}}, …, a_{k}^{σ_{k}}, F_{qf} does not contain any quantifier and the types in σ_{i} are IN or C.^{5}

Remark 2.2 The notions of ∀-formula and ∃-formula (as well as the theorem corresponding to theorem 2.4 below) from [15] allow more general types. For simplicity we formulate above just the special case needed in this paper.

Every (real) normed space (X, ∥ · ∥) together with a bounded convex subset C of X gives rise to the ‘full’ model S^{ω,X} over X, C of A^{ω}[X, ∥ · ∥, C]. If (X, ∥·∥) is uniformly convex and η : IN → IN a modulus of uniform convexity^{6} than this model will be a model of A^{ω}[X, ∥ · ∥, C, η]. We say that a sentence A ∈ L(A^{ω}[X, ∥ · ∥, C, η]) holds in (X, ∥ · ∥) and C if it holds in this model (see [15] for details on all this).

5Recall from [15] that the type ‘C’ is a defined type where – using the notation from [15] – ‘∀x^{C}A’ and ‘∃x^{C}A’ stand for ‘∀x^{X}(χ_{C}(x) =_{IN} 0 → A)’ and ‘∃x^{X}(χ_{C}(x) =_{IN} 0 ∧ A)’, where χ_{C} represents the characteristic function of C in X.

Definition 2.3 For functionals x^{ρ}, y^{ρ} of type ρ = IN → IN we define x ≤_{ρ} y by

x ≤_{ρ} y :≡ ∀z^{IN}(x(z) ≤_{IN} y(z)).

Theorem 2.4 ([15]) Let η be a constant of type IN → IN, σ, ρ = IN → IN and τ = C, IN → C or C → C. s is a closed term of type σ → ρ and B_{∀}, C_{∃} are ∀- resp. ∃-formulas. If the sentence

∀x^{σ}∀y ≤_{ρ} s(x)∀z^{τ} (∀u^{IN}B_{∀}(x, y, z, u) → ∃v^{IN}C_{∃}(x, y, z, v))

is provable in A^{ω}[X, ∥·∥, C, η], then one can extract a computable functional^{7} Φ : IN^{IN} × IN × IN^{IN} → IN such that

∀y ≤_{ρ} s(x)∀z^{τ} [∀u ≤ Φ(x, b, η) B_{∀}(x, y, z, u) → ∃v ≤ Φ(x, b, η) C_{∃}(x, y, z, v)]

holds in any non-trivial (real) uniformly convex normed linear space (X, ∥·∥) with convexity modulus η and any non-empty b-bounded convex subset C ⊂ X. Instead of single variables x, y, z, u, v we may also have finite tuples of variables \underline{x}, \underline{y}, \underline{z}, \underline{u}, \underline{v} as long as the elements of the respective tuples satisfy the same type restrictions as x, y, z, u, v. Moreover, instead of a single premise of the form ‘∀u^{IN}B_{∀}(x, y, z, u)’ we may have a finite conjunction of such premises.

Using the so-called standard representation of compact Polish spaces like [0, 1]^{IN} (with the product metric) theorem 2.4 implies the following corollary (see [15]):

Corollary 2.5 Let B_{∀}, C_{∃} be ∀- resp. ∃-formulas and φ : IN → IN be a (primitive recursive function). If the sentence

∀n^{IN}, g^{IN→IN}, (a_{k}) ∈ [0, φ(n)]^{IN}, x^{C}, (u_{k})^{IN→C}, f^{C→C}
(∀w^{IN}B_{∀}(w) → ∃v^{IN}C_{∃}(v))

6I.e. ∀x, y ∈ X, k ∈ IN(∥x∥, ∥y∥ ≤ 1 ∧ ∥\frac{x+y}{2} ∥ ≥ 1 − 2^{−η(k)} → ∥x − y∥ ≤ 2^{−k}).

7In the sense type-2 computability theory, i.e. Turing computability w.r.t. oracle Turing machines.

is provable in A^{ω}[X, ∥·∥, C, η], then one can extract a computable functional Φ(n, g, b, η) such that

∀n, b ∈ IN, α, η ∈ IN^{IN}, (a_{k}) ∈ [0, φ(n)]^{IN}, x ∈ C, (u_{k}) ∈ C^{IN}, f : C → C

(∀w ≤ Φ(n, g, b, η) B_{∀}(w) → ∃v ≤ Φ(n, g, b, η) C_{∃}(v))

holds in any non-trivial (real) uniformly convex normed linear space (X, ∥·∥) with convexity modulus η and any non-empty b-bounded convex subset C ⊂ X. Instead of single variables n, g, (a_{n}) we may also have finite tuples of each of these variables. Moreover, instead of a single premise of the form ‘∀w^{IN}B_{∀}(w)’ we may have a finite conjunction of such premises.

A crucial feature in the above corollary is that the bound Φ(n, α, b, η) does not depend on (a_{k}), x, (u_{k}) or f at all and on X and C only via η and b.

Theorem 1.5 can be proved in A^{ω}[X, ∥ · ∥, C, η] and even in a weak fragment thereof (as the proof of the quantitative strengthened form of theorem 1.5 given below shows, neither dependent choice DC nor countable choice is needed). Problems in connection with the restricted availability of extensionality in A^{ω}[X, ∥·, ∥, C, η] (see [15]) do not apply here since the assumption on f being (even uniformly) Lipschitz continuous implies the extensionality (see the detailed discussion in the case of nonexpansive functions given in [15]). Hence corollary 2.5 is applicable and guarantees a-priorily a strong uniform effective version of theorem 1.5 in the sense explained in the introduction.

Remark 2.6 (for logicians) There is a minor problem having to do with the fact that our formal system proves only weak extensionality of the constant χ_{C} representing the characteristic function of C. As a consequence of this we have to make sure that the condition (we discuss things for notational simplicity here only for the special case of constant sequences) α + β + γ = 1 becomes provable which can be achieved by replacing

(∗) ∀α, β, γ ∈ [0, 1](α + β + γ = 1 → A(α, β, γ))

officially by

(∗∗)∀α, β ∈ [0, 1] A(α, min(1 − α, β), 1 − α − min(1 − α, β)).

In the following, though, we will continue to write (∗) instead of (∗∗) for better readability.

The assumptions on α_{n}, β_{n}, γ_{n}, k_{n} all become ∀-formulas once we express ‘∑ k_{n} < ∞’ and ‘∑ γ_{n} < ∞’ explicitly with bounds K, E ∈ IN, i.e.

A_{1} :≡ ∀n ∈ IN

(α_{n} + β_{n} + γ_{n} =_{IR} 1 ∧ \frac{1}{k} ≤_{IR} β_{n} ≤_{IR} 1 − \frac{1}{k} ∧ ∑_{i=0}^{n} k_{i} ≤_{IR} K ∧ ∑_{i=0}^{n} γ_{i} ≤_{IR} E).

The existential quantifier ‘∃p ∈ C’ in the premise

∃p ∈ C(f(p) =_{X} p ∧ ∀x ∈ C∀i ∈ IN(∥f^{i}(x) − p∥ ≤_{IR} (1 + k_{i})∥x − p∥)).

can be moved out as a universal quantifier in front of the whole implication leaving back the ∀-premise

A_{2} :≡ f(p) =_{X} p ∧ ∀x ∈ C∀i ∈ IN(∥f^{i}(x) − p∥ ≤_{IR} (1 + k_{i})∥x − p∥).

Finally, we have the condition on f being uniformly Lipschitz continuous which becomes an ∀-formula once stated with a Lipschitz constant λ ∈ IN

A_{3} :≡ ∀n ∈ IN∀x, y ∈ C(∥f^{n}(x) − f^{n}(y)∥ ≤_{IR} λ · ∥x − y∥).

Hence in total, theorem 1.5 can be reformulated as

∀λ, k, l, K, E ∈ IN, g ∈ IN^{IN}, (k_{n}) ∈ [0, K]^{IN}, (α_{n}), (β_{n}), (γ_{n}) ∈ [0, 1]^{IN}
∀x^{C}, p^{C}, (u_{n})^{IN→C}, f^{C→C}
(A_{1} ∧ A_{2} ∧ A_{3}→∃n∀m ∈ [n, n + g(n)](∥x_{m} − f(x_{m})∥ <_{IR} 2^{−l}).

Since the conclusion is (relative to A^{ω}[X, ∥ · ∥, C, η] equivalent to) an ∃- formula and the premise is a conjunction of ∀-formulas, we can apply corollary 2.5 to get an effective bound Φ(λ, k, l, K, E, g, b, η) on ‘∃n’, i.e.

∃n ≤ Φ(λ, k, l, K, E, g, b, η)∀m ∈ [n, n + g(n)](∥x_{m} − f(x_{m})∥ <_{IR} 2^{−l}), (4)

that does not depend on (α_{n}), (β_{n}), (γ_{n}), x, p, f, (k_{n}), (u_{n}) but only on λ, k, l, K, E, g as well as a bound^{8} b on C and the modulus η.

Corollary 2.5 not only provides an effective bound for the conclusion but also allows one to to replace ∀-premises by approximate versions thereof. We are here only interested in one of the premises, namely A_{2}, which can be also written as

∀m ∈ IN

((∥f(p) − p∥ ≤_{IR} 2^{−m}) ∧ ∀x ∈ C∀i ∈ IN(∥f^{i}(x) − f^{i}(p)∥ ≤_{IR} (1 + k_{i})∥x − p∥)), (5) where

8This requirement will be weakened below.

(∥f(p) − p∥ ≤_{IR} 2^{−m}) ∧ ∀x ∈ C∀i ∈ IN(∥f^{i}(x) − f^{i}(p)∥ ≤_{IR} (1 + k_{i})∥x − p∥)

itself is a ∀-formula. By the corollary we get an effective bound Ψ := Ψ(λ, k, l, K, E, g, b, η) on ‘∀m’ such that in order to obtain the conclusion (4) we can replace (5) by

\begin{matrix}∀m ≤ Ψ \\ ((∥f(p) − p∥ ≤_{IR} 2^{−m}) ∧ ∀x ∈ C∀i ∈ IN(∥f^{i}(x) − f^{i}(p)∥ ≤_{IR} (1 + k_{i})∥x − p∥)) \end{matrix}

and hence – since Ψ does not depend on p – by

∀m ∈ IN∃p ∈ C((∥f(p) − p∥ ≤_{IR} 2^{−m}) ∧ ∀x ∈ C∀i ∈ IN
(∥f^{i}(x) − f^{i}(p)∥ ≤_{IR} (1 + k_{i})∥x − p∥)).

So in effect we have replaced the assumption on f having real fixed points by the weaker assumption on f having approximate fixed points.

The proof of theorem 2.4 in [15] (and hence that of corollary 2.5) is constructive and provides algorithm for actually extracting a bound Φ from the proof of theorem 1.5 together with a proof verifying the bound which – moreover – only uses the existence of ε-fixed points of f. The latter will be shown to always exist for asymptotically nonexpansive mappings by a completely elementary argument, while the existence of real fixed points requires the completeness of X and closedness of C and is based on the non-trivial convex intersection property of uniformly convex Banach spaces, see [8] and also [7]. All this will be carried out in the reminder of this paper. The explicit extraction of the bounds will, furthermore, show that the assumption on C being bounded (needed in the conclusion of the application of theorem 2.4 and hence corollary 2.5) can be replaced by the assumption that (u_{n}) is bounded (as in theorem 1.5) and that there exists a d ∈ IN such that within the d-neighbourhood of x ∈ C there are approximate fixed points p_{ε} ∈ C of f for any ε > 0 (which is trivially satisfied if F ix(f) ≠ ∅). Hence we indeed get in the end a uniform quantitative version of the ‘original’ theorem 1.5.

3 Some helpful lemmata

Lemma 3.1 Let (a_{n}) be a sequence in IR_{+} with a_{n+1} ≤ a_{n} for all n. Then

∀ε > 0∀g : IN → IN∃n ≤ max_{i<⌊a_{0}/ε⌋} g^{i}(0) (a_{n} − a_{g(n)} ≤ ε)

Proof The inequality can fail in at most ⌊a_{0}/ε⌋ − 1 steps of applying g, thus it has to be true for at least the one remaining. • Lemma 3.2 (Quantitative version of a lemma by Qihou, [23]) Let (a_{n}), (b_{n}), (c_{n}) be sequences in IR_{+}, A ∈ Q_{+}^{∗}, B, C ∈ Q_{+}, such that a_{n+1} ≤ (1 + b_{n})a_{n} + c_{n}; a_{0} ≤ A; ∑ b_{n} ≤ B; ∑ c_{n} ≤ C. Then the following hold:

1) (A + C)e^{B} is an upper bound on a_{n}.

2) Let

Φ(A, B, C, g, ε) := max_{i<⌊(4BD+4C+D)/ε⌋} g^{i}(0),

where D = (A + C)e^{D}. Then

\begin{matrix}∀ε ∈ (0, 1]∀g ∈ IN → IN∃n ≤ Φ(A, B, C, g, ε) \\ (g(n) > n → |a_{g(n)} − a_{n}| ≤ ε) . \end{matrix}  (6)

3) Let

Ψ(A, B, C, g, ε) = Φ(A, B, C, g, ε/3).

Then

∀ε ∈ (0, 1]∀g : IN → IN∃n ≤ Ψ(A, B, C, g, ε)
∀i, j (g(n) ≥ j > i ≥ n → |a_{j} − a_{i}| ≤ ε) .  (7)

Proof 1: By induction on m one shows

a_{n+m} ≤ a_{n} · ∏_{j=0}^{m−1}(1 + b_{n+j}) + ∑_{i=0}^{m−1} c_{n+i} · ∏_{j=i+1}^{m−1}(1 + b_{n+j})

and also (by the arithmetic-geometric mean inequality)

∏_{j=0}^{m−1}(1 + b_{n+j}) ≤ (1 + \frac{∑_{j=0}^{m−1} b_{n+j}}{m})^{m} < e^{∑_{j=0}^{m−1} b_{n+j}}

and combined

a_{n+m} ≤ (a_{n} + ∑_{j=0}^{m−1} c_{n+j}) · e^{∑_{j=0}^{m−1} b_{n+j}},  (8)
a_{m} ≤ (A + C) · e^{B}

for all m ∈ IN.

2: Consider (a_{n}^{∗}) in which a_{0}^{∗} = a_{0} and a_{n+1}^{∗} = (1 + b_{n})a_{n}^{∗} + c_{n}. Note D ≥ a_{n+1}^{∗} ≥ a_{n+1}^{∗} − a_{n+1} ≥ (1 + b_{n})(a_{n}^{∗} − a_{n}) ≥ a_{n}^{∗} − a_{n}. Build the two series

E_{n} = 4(BD + C − ∑_{i≤n}(b_{i}D + c_{i}))

and

D_{n} = D − (a_{n}^{∗} − a_{n}).

Their sum satisfies the conditions of Lemma 3.1, therefore there exists n ≤ Φ(A, B, C, g, ε), such that E_{n} − E_{g(n)} ≤ ε and D_{n} − D_{g(n)} ≤ ε, but this means

∑_{i=n}^{g(n)} b_{i}D + ∑_{i=n}^{g(n)} c_{i} ≤ \frac{ε}{4}.

Then (using e^{x} ≤ 1 + 2x for 0 ≤ x < 1)

a_{j} − a_{i} < (a_{i} + \frac{ε}{4})e^{\frac{ε}{4D}} − a_{i} ≤

(a_{i} + \frac{ε}{4})(1 + \frac{ε}{2D}) − a_{i} ≤

\frac{εD}{2D} + \frac{ε}{4} + \frac{ε^{2}}{8D} < ε

for all i, j, such that n ≤ i < j ≤ g(n). That is, if the series grows (i.e. a_{g(n)} > a_{n}), it will satisfy the inequality. If it decreases, then

a_{n} − a_{g(n)} ≤ a_{n} − a_{g(n)} + a_{g(n)}^{∗} − a_{n}^{∗} = D_{n} − D_{g(n)} ≤ ε.

3: By the proof of the previous point, there is an n ≤ Ψ(A, B, C, g, ε), for which we have |a_{g(n)} − a_{n}| ≤ ε/3 and also ∀i, j(g(n) ≥ j > i ≥ n ∧ a_{j} > a_{i} → a_{j} − a_{i} ≤ ε/3). Therefore, for any i with g(n) ≥ i ≥ n we have a_{g(n)} − ε/3 ≤ a_{i} ≤ a_{n} + ε/3 and hence ∀i, j ∈ [n, g(n)](a_{i} ≤ a_{n} + ε/3 ≤ a_{g(n)} + 2ε/3 ≤ a_{j} + ε), from which the needed inequality follows directly. •

Lemma 3.3 Let D : IN → Q_{+}^{∗}, B, C : IN → Q_{+}, and for all q, let (a_{n})^{q}, (b_{n})^{q}, (c_{n})^{q} be sequences in IR_{+}, such that a_{n+1}^{q} ≤ (1+b_{n}^{q})a_{n}^{q}+c_{n}^{q}; a_{n}^{q} ≤ D(q); ∑ b_{i}^{q} ≤ B(q); ∑ c_{i}^{q} ≤ C(q) for all n, q ∈ IN. Then:

1) Let

Φ(D, B, C, g, ε, m) = max ; i<⌊ \frac{1}{ε} ∑_{q=0}^{m−1}(4B(q)D(q)+4C(q)+D(q))⌋ g^{i}(0).

Then

∀ε ∈ (0, 1]∀m ∈ IN∀g ∈ IN → IN∃n ≤ Φ(D, B, C, g, ε, m)
∀q < m (g(n) > n → |a_{g(n)}^{q} − a_{n}^{q}| ≤ ε) .

2) Let Ψ(D, B, C, g, ε, m) = Φ(D, B, C, g, ε/3, m). Then

∀ε ∈ (0, 1]∀m ∈ IN∀g ∈ IN → IN∃n ≤ Ψ(D, B, C, g, ε, m)
∀q < m∀i, j (g(n) ≥ j > i ≥ n → |a_{j}^{q} − a_{i}^{q}| ≤ ε) .

Proof As in the previous proof, we can represent every (a_{n}^{q}) by two series (D_{n}^{q}) and (E_{n}^{q}) in a common sum, to which we can apply Lemma 3.1. Then we can carry on the rest of the proof for the individual sequences. •

Definition 3.4 (Clarkson, [3]) A modulus of uniform convexity of a uniformly convex space (X, ∥ · ∥) is a mapping η : (0, 2] → (0, 1], such that for all x, y ∈ X, ε ∈ (0, 2]

∥x∥, ∥y∥ ≤ 1 ∧ ∥x − y∥ ≥ ε → ∥\frac{x + y}{2} ∥ ≤ 1 − η(ε).

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

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

The next lemma is an adaptation (and improvement) of a lemma from [26] to our situation, i.e. Mann iterations with error term instead of Ishikawa iterations without error term as considered by Schu:

Lemma 3.6 Let X be a normed linear space, C ⊆ X a convex subset of X, f : C → C uniformly l-Lipschitzian, and (x_{n}) be a Krasnoselski-Mann iteration starting from x ∈ C with error vector (u_{n}) where ∥u_{n} − x_{n}∥ is bounded by u for all n ∈ IN.

Then if ∥x_{n} − f^{n}(x_{n})∥ ≤ ε_{n} and ∥x_{n+1} − f^{n+1}(x_{n+1})∥ ≤ ε_{n+1}, then ∥x_{n+1} − f(x_{n+1})∥ ≤ ε_{n+1} + (ε_{n} + γ_{n}u)(l + l^{2}).

Proof

∥x_{n+1} − f(x_{n+1})∥ ≤ ∥x_{n+1} − f^{n+1}(x_{n+1})∥ + ∥f^{n+1}(x_{n+1}) − f(x_{n+1})∥
≤ ε_{n+1} + l∥f^{n}(x_{n+1}) − x_{n+1}∥
≤ ε_{n+1} + l∥f^{n}(x_{n+1}) − α_{n}x_{n} − β_{n}f^{n}(x_{n}) − γ_{n}u_{n}∥
≤ ε_{n+1} + l∥f^{n}(x_{n+1}) − f^{n}(x_{n})∥ +
+l(α_{n} + γ_{n})∥f^{n}(x_{n}) − x_{n}∥ + lγ_{n}∥u_{n} − x_{n}∥
≤ ε_{n+1} + lε_{n} + l^{2}∥x_{n+1} − x_{n}∥ + γ_{n}ul
≤ ε_{n+1} + lε_{n} + l^{2}∥β_{n}f^{n}(x_{n}) − (β_{n} + γ_{n})x_{n} + γ_{n}u_{n}∥ +
+γ_{n}ul
≤ ε_{n+1} + lε_{n} + l^{2}β_{n}∥f^{n}(x_{n}) − x_{n}∥ + γ_{n}u(l + l^{2})
≤ ε_{n+1} + (ε_{n} + γ_{n}u)(l + l^{2}).
•

In [8] it is shown – using that reflexive and hence a-fortiori uniformly convex Banach spaces have the so-called ‘convex intersection property CIP’ – that asymptotically nonexpansive selfmappings of bounded closed convex subsets C ⊂ X have fixed points. Our quantitative results reduce the need of fixed points to that of approximate fixed points. For the latter we now give a fully elementary proof which does not need CIP (nor the completeness/closedness of X/C):

Lemma 3.7 Let (X, ∥ · ∥) be a uniformly convex space with modulus η, and C ⊆ X be nonempty, convex and bounded. Let f : C → C be asymptotically non-expansive with sequence (k_{n}).

Then Fix_{ε}(f) := {x ∈ C : ∥f(x) − x∥ ≤ ε} ≠ ∅, ∀ε > 0.

Proof Let y ∈ C. Consider

ρ_{0} := inf {ρ ∈ IR_{+} : ∃x ∈ C∃k ∈ IN∀i > k.∥f^{i}(y) − x∥ ≤ ρ}

Since C is bounded, the set is non-empty and ρ_{0} exists. We also have ρ_{0} ≥ 0 and

∀δ > 0∃x ∈ C∃k ∈ IN∀i > k.∥f^{i}(y) − x∥ ≤ ρ_{0} + δ/2.  (9)

Case 1. ρ_{0} > 0:

Let ε ∈ (0, 4] and choose δ ∈ (0, 1] such that

η (\frac{ε}{2(ρ_{0} + 1)}) > 1 − \frac{ρ_{0} − δ}{ρ_{0} + δ} .

By (9), there is an x_{δ} ∈ C, such that

∃k ∈ IN∀i > k.∥f^{i}(y) − x_{δ}∥ ≤ ρ_{0} + δ/2.  (10)

Assume that

∀k ∈ IN∃n > k.∥f^{n}(x_{δ}) − x_{δ}∥ ≥ ε/2.  (11)

Let n be large enough that (using (11))

(1 + k_{n})(ρ_{0} + δ/2) ≤ ρ_{0} + δ ∧ ∥f^{n}(x_{δ}) − x_{δ}∥ ≥ ε/2,  (12)

and m ≥ n be large enough that (using (10))

∥f^{k}(y) − x_{δ}∥ ≤ ρ_{0} + δ/2

for all k ≥ m − n. Then

∥f^{n}(x_{δ}) − f^{k}(y)∥ ≤ (1 + k_{n})∥x_{δ} − f^{k−n}(y)∥ ≤ ρ_{0} + δ  (13)

and

∥x_{δ} − f^{k}(y)∥ ≤ ρ_{0} + δ/2 ≤ ρ_{0} + δ  (14)

for all k ≥ m.

(12), (13) and (14) yield by uniform convexity and δ ≤ 1

∥\frac{x_{δ} − f^{n}(x_{δ})}{2} − f^{k}(y)∥ ≤ (1 − η (\frac{ε}{2(ρ_{0} + 1)})) (ρ_{0} + δ) < ρ_{0} − δ

for all k ≥ m, which contradicts the minimality of ρ_{0}.

Hence (11) is false, i.e.

∃k∀n ≥ k.∥f^{n}(x_{δ}) − x_{δ}∥ < ε/2,

which implies that there exists a k, such that

∥f^{k+1}(x_{δ}) − x_{δ}∥ < ε/2 and ∥f^{k+2}(x_{δ}) − x_{δ}∥ < ε/2

and hence ∥f(x) − x∥ < ε for x := f^{k+1}(x_{δ}).

Since ε ∈ (0; 4] was arbitrary, this implies Fix_{ε}(f) ≠ ∅.

Case 2. ρ_{0} = 0:

Let ε > 0. Then (9) implies

∃x ∈ C∃k ∈ IN∀i > k.∥f^{i}(y) − x∥ ≤ ε/2

and therefore x_{ε} := f^{k+1}(y) is an ε-fixed point of f, and again Fix_{ε}(f) ≠ ∅. •

4 Main results

Throughout this section, (X, ∥ · ∥) will be a uniformly convex space with modulus of uniform convexity η and C a convex subset of X. f will be a mapping from C to C, x ∈ C and the series (x_{n}) will be a Krasnoselski-Mann iteration with error terms (1), and (α_{n}), (β_{n}), (γ_{n}), (u_{n}) as defined in (1).

Theorem 4.1 Let f be uniformly l-Lipschitzian and

∀ε > 0∃p_{ε} ∈ C ( \begin{matrix}∥f(p_{ε}) − p_{ε}∥ ≤ ε ∧ \\ ∥p_{ε} − x∥ ≤ d ∧ \\ ∀y ∈ C∀n (∥f^{n}(y) − f^{n}(p_{ε})∥ ≤ (1 + k_{n})∥y − p_{ε}∥) \end{matrix} )

(15)

where d ∈ Q_{+}^{∗}, k_{n} ∈ IR_{+} and also ∑_{n=0}^{∞} k_{n} ≤ K ∈ Q_{+}.

Let 1/k ≤ β_{n} ≤ 1 − 1/k for some k ∈ IN, ∑_{n=0}^{∞} γ_{n} ≤ E ∈ Q_{+}, and (u_{n}) be bounded with ∥u_{n} − x∥ ≤ u ∈ Q_{+}.

Then

∀δ ∈ (0, 1]∀g : IN → IN∃n ≤ Φ∀m ∈ [n, n + g(n)] (∥x_{m} − f(x_{m})∥ ≤ δ) where Φ = Φ(K, E, u, k, d, l, η, δ, g) and

Φ(K, E, u, k, d, l, η, δ, g) = h^{i}(0)
h = λn.(g(n + 1) + n + 1)
i = ⌊\frac{3(5KD + 6E(U + D) + D)k^{2}}{εη (ε/(D(1 + K)))} ⌋
D = e^{K}(d + EU)
U = u + d
ε = δ/(2(1 + l(l + 1)(l + 2))).  (16)

Proof Let ν ∈ (0, 1)∩Q, p be a p_{ε} from (15), and for the moment assume ∥f(p) − p∥ ≤ ν^{n+1}/(n + K) is satisfied for all n. Set U := u + d ≥ ∥u_{n} − p∥. Then we also have ∥f^{n}(p) − p∥ = ∥f^{n−1}(f(p)) − f^{n−1}(p) + f^{n−1}(p) − p∥ ≤ \frac{ν^{n+1}}{n+K} ∑_{i=0}^{n−1}(1 + k_{i}) ≤ ν^{n+1} by the third clause in (15), and

∥x_{n+1} − p∥ = ∥α_{n}x_{n} + β_{n}f^{n}(x_{n}) + γ_{n}u_{n} − p∥

= ∥α_{n}(x_{n} − p) + β_{n}(f^{n}(x_{n}) − f^{n}(p)) + γ_{n}(u_{n} − p) + β_{n}(f^{n}(p) − p)∥ ≤ α_{n}∥x_{n} − p∥ + β_{n}∥f^{n}(x_{n}) − f^{n}(p)∥ + γ_{n}U + β_{n}ν^{n+1} ≤ α_{n}∥x_{n} − p∥ + β_{n}(1 + k_{n})∥x_{n} − p∥ + γ_{n}U + ν^{n+1}

≤ (1 + k_{n})∥x_{n} − p∥ + γ_{n}U + ν^{n+1}.  (17)

By Lemma 3.2 for all m ∈ IN

∥x_{m} − p∥ ≤ D,  (18)

where D := e^{K} · (d + EU + ν(1 − ν)).

For any n, assume ∥x_{n} − p∥ ≥ ε + ν^{n+1} and ∥f^{n}(x_{n}) − x_{n}∥ ≥ ε + ν^{n+1}. The latter implies

∥(x_{n} − p) − (f^{n}(x_{n}) − f^{n}(p))∥ ≥ ∥x_{n} − f^{n}(x_{n})∥ − ∥p + f^{n}(p)∥ ≥ ε.

Hence by Lemma 3.5, using k_{n} ≤ K, and (18),

∥(1 − β_{n})\frac{x_{n} − p}{(1 + k_{n})∥x_{n} − p∥} + β_{n} \frac{f^{n}(x_{n}) − f^{n}(p)}{(1 + k_{n})∥x_{n} − p∥}∥ ≤

1 − 2β_{n}(1 − β_{n}) · η (\frac{ε}{(1 + K)D} ) .  (19)

Thus

∥x_{n+1} − p∥ = ∥α_{n}x_{n} + β_{n}f^{n}(x_{n}) + γ_{n}u_{n} − p∥

= ∥(1 − β_{n} − γ_{n})(x_{n} − p) + β_{n}(f^{n}(x_{n}) − f^{n}(p) − p + f^{n}(p))

+ γ_{n}(u_{n} − p)∥ ≤ ∥(1 − β_{n})(x_{n} − p) + β_{n}(f^{n}(x_{n}) − f^{n}(p))∥ + γ_{n}∥u_{n} − x_{n}∥ + ν^{n+1}

≤ ((1 + k_{n})∥x_{n} − p∥) (1 − 2β_{n}(1 − β_{n})η (\frac{ε}{(1 + K)D} ))

+ γ_{n}(U + D) + ν^{n+1}

≤ ∥x_{n} − p∥ + k_{n}D + γ_{n}(U + D) + ν^{n+1} − ε · 2\frac{1}{k^{2}} η (\frac{ε}{(1 + K)D} ) (20)

but ∥x_{n} − p∥ ≤ ∥x_{n+1} − p∥ + |∥x_{n} − p∥ − ∥x_{n+1} − p∥|, therefore (20) implies

0 ≤ |∥x_{n} − p∥ − ∥x_{n+1} − p∥|+k_{n}D+γ_{n}(U+D)+ν^{n+1}−2εk^{−2}η (\frac{ε}{(1 + K)D} ) ,

where the positive additives can be made arbitrarily small by Lemma 3.2, and the negative is a constant greater than 0. Assume we have made the positive sum smaller than this constant for two consecutive members of the series starting at n. By contradiction we will have for both i = n and i = n + 1

∥x_{i} − p∥ < ε + ν^{i+1} or ∥f^{i}(x_{i}) − x_{i}∥ < ε + ν^{i+1}.  (21)

Consider the following cases: Case 1. ∥x_{n+1} − p∥ < ε + ν^{n+2}. Here we have

∥f(x_{n+1}) − x_{n+1}∥ ≤ ∥f(x_{n+1}) − f(p)∥ + ∥p − x_{n+1}∥ + ∥p − f(p)∥
≤ (1 + l)∥x_{n+1} − p∥ + ν^{n+1} ≤ (2 + l)(ε + ν^{n+1}). (22)

Case 2. ∥x_{n+1} −f^{n+1}(x_{n+1})∥ < ε+ν^{n+2} and ∥x_{n} −f^{n}(x_{n})∥ < ε+ν^{n+1}. Then, using Lemma 3.6 with ε_{n+1} = ε_{n} = ε + ν^{n+1}, we have

∥x_{n+1} − f(x_{n+1})∥ ≤ (ε + ν^{n+1} + γ_{n}(U + D))(1 + l + l^{2}).

Case 3. ∥x_{n+1} − f^{n+1}(x_{n+1})∥ < ε + ν^{n+2} and ∥x_{n} − p∥ < ε + ν^{n+1}. In this case we have (reasoning as in (22))

∥x_{n} − f^{n}(x_{n})∥ ≤ (2 + l)(ε + ν^{n+1})

and again using Lemma 3.6

∥x_{n+1} − f(x_{n+1})∥ ≤ (ε + ν^{n+1} + γ_{n}(U + D))(1 + l(l + 1)(l + 2)).

In either case, if we denote

p_{n} = |∥x_{n} − p∥ − ∥x_{n+1} − p∥|
q_{n} = k_{n}D + 2γ_{n}(U + D) + 2ν^{n+1}

and we have

p_{n}, q_{n} < εk^{−2}η (\frac{ε}{(1 + K)D} )  (23)

and

p_{n+1}, q_{n+1} < εk^{−2}η (\frac{ε}{(1 + K)D} ),

(note that |∥x_{n} − p∥ − ∥x_{n+1} − p∥| + k_{n}D + γ_{n}(U + D) + ν^{n+1} ≤ p_{n} + q_{n} < 2εk^{−2}η (\frac{ε}{(1+K)D} )) where ε = δ/(2(1 + l(l + 1)(l + 2))), then (using that q_{n+1} < ε)

∥x_{n+1} − f(x_{n+1})∥ ≤ (ε + \frac{q_{n+1}}{2} ) (1 + l(l + 1)(l + 2)) ≤ δ  (24)

Next, construct the two series

a_{n} = ∥x_{n} − p∥ and
b_{n} = KD + 2E(U + D) + \frac{2ν}{(1 − ν)} − ∑_{i=0}^{n−1}(k_{i}D + 2γ_{i}(U + D) + 2ν^{i+1}))

(note p_{n} = a_{n+1} − a_{n}, and q_{n} = b_{n+1} − b_{n}). We know from (17) that a_{n+1} ≤ (1 + k_{n})a_{n} + γ_{n}U + ν^{n+1}, and b_{n+1} ≤ b_{n}, therefore by Lemma 3.3

∀k ∈ IN∀g : IN → IN∃m < Φ_{ν}∀i, j

(m − 1 ≤ i < j ≤ m + g(m) → |a_{j} − a_{i}|, |b_{j} − b_{i}| ≤ εk^{−2}η (\frac{ε}{(1+K)D} )) ,

where

Φ_{ν}(K, E, u, k, d, l, η, δ, g) = h^{i}(0)
h = λn.(g(n + 1) + n + 1)
i = ⌊\frac{3(5KD + 6E(U + D) + 6ν/(1 − ν) + D)k^{2}}{εη (ε/(D(1 + K)))} ⌋
D = e^{K}(d + EU + ν/(1 − ν))
U = u + d
ε = δ/(2(1 + l(l + 1)(l + 2))).

This is enough to ensure (21) and hence (24) for all n ∈ [m, m + g(m)] and therefore

∀δ ∈ (0, 1]∀g : IN → IN

∃n ≤ Φ_{ν}(K, E, u, k, d, l, η, δ, g)∀m ∈ [n, n + g(n)] (∥x_{m} − f(x_{m})∥ ≤ δ) .

It only remains to throw away the assumption that ∥f(p)−p∥ ≤ ν^{n+1}/(n+ K) holds for all n. This we can do by simply relaxing it to only the n’s for which the inequality was used in the proof, i.e. for all n ≤ Φ_{ν}. This is certainly satisfied by p_{ν^{Φν +1}/(Φ_{ν}+K)} using (15).

The value of ν was arbitrary within (0, 1) ∩ Q, thus we can take it arbitrarily small and the bound will get lower at the expense of requiring better approximate fixed points (which we have). Therefore Φ = inf_{ν∈(0,1)} Φ_{ν} will be sufficient for the bound.

Computing the infimum yields the form (16). •

Remark 4.2 Using the argument about the Herbrand normal form (3) in Section 1, this theorem and all its corollaries allow us to also conclude

∥f(x_{n}) − x_{n}∥ → 0.

In particular, theorem 4.1 implies theorem 1.5 from the introduction and is in fact a quantitative strengthening of the latter.

Corollary 4.3 Let f be uniformly l-Lipschitzian and asymptotically quasinonexpansive with sequence (k_{n}), Fix(f) ≠ ∅, and also ∑_{n=0}^{∞} k_{n} ≤ K ∈ Q_{+}.

Let 1/k ≤ β_{n} ≤ 1 − 1/k for some k ∈ IN, ∑_{n=0}^{∞} γ_{n} ≤ E ∈ Q_{+}, and (u_{n}) be bounded with ∥u_{n} − x∥ ≤ u ∈ Q_{+}.

Then

∀δ ∈ (0, 1]∀g : IN → IN∃n ≤ Φ∀m ∈ [n, n + g(n)] (∥x_{m} − f(x_{m})∥ ≤ δ)

where Φ is as defined in theorem 4.1 with d ≥ ∥x − p∥ for some p ∈ Fix(f).

Proof Direct corollary of the main theorem, where the first and second clauses of (15) are satisfied by the existence of real fixed points of f, and the third clause follows from the assumption on f being asymptotically quasinonexpansive. •

Corollary 4.4 If we only need to find a single x_{n}, which is an approximate fixed point of the function, taking g(n) ≡ 0 gives

∀δ ∈ (0, 1]∃n ≤ Φ_{1}(K, E, u, k, d, l, η, δ) (∥x_{n} − f(x_{n})∥ ≤ δ)  (25)

where

Φ_{1}(K, E, u, k, d, l, η, δ) = ⌊\frac{3(5KD + 6E(U + D) + D)k^{2}}{εη (ε/(D(1 + K)))} ⌋
D = e^{K}(d + EU)
U = u + d
ε = δ/(2(1 + l(l + 1)(l + 2))).

Remark 4.5 If the modulus of uniform convexity of the space can be written in the form η(ε) = εη̃(ε) where η̃ is monotone (0 < ε_{1} ≤ ε_{2} ≤ 2 → η̃(ε_{1}) ≤ η̃(ε_{2})), the proof of Theorem 4.1 allows to extract a bound with η replaced by η̃ (by changing η (\frac{ε}{(1+K)D} ) to η (\frac{ε}{(1+k_{n})∥x_{n}−p∥}) in (19) we can replace (20)

by ∥x_{n+1} − p∥ ≤ ∥x_{n} − p∥ + k_{n}D + γ_{n}(U + D) + ν^{n+1} − ε · 2\frac{1}{k^{2}} η̃ (\frac{ε}{(1+K)D} ) and the change carries on through the proof).

Disregarding the various constants, the ε-dependency of our bounds in the case g ≡ 0 is ε · η(ε).

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

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

where

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

is monotone, we can apply the previous remark. Hence we get – disregarding again constants – that the ε-dependency of our bounds in the case of L_{p} (p ≥ 2) is ε^{p}. For the case X := IR with the Euclidean norm, where we can choose η̃(ε) := \frac{1}{2} (since ε/2 is a modulus of convexity), we have a linear dependency in ε. These results match in quality the bounds obtained in [11, 12, 14] for the case of nonexpansive functions and the usual Krasnoselski-Mann iteration (without error terms). In that case, the deep work in [1] even established a quadratic bound in arbitrary normed spaces for the special case of constant λ_{n} = λ ∈ (0, 1). For general (λ_{n}) (satisfying λ_{n} ∈ (0, 1 − 1/k) and ∑ λ_{n} = ∞), the first bounds for Krasnoselski-Mann iterations in arbitrary normed and even hyperbolic spaces were established in [13, 16].

In the case of asymptotically nonexpansive mappings f : C → C (C ⊂ X bounded, closed and convex) it is an open problem whether F ix_{ε}(f) ≠ ∅, ∀ε > 0, for general (i.e. not uniformly convex) Banach spaces X (see [7], p.135).

Corollary 4.6 Let f be asymptotically nonexpansive with sequence (k_{n}), d is such that Fix_{ε}(x, d, f) ≠ ∅ for all ε > 0 and also ∑_{n=0}^{∞} k_{n} ≤ K ∈ Q_{+}.

Let 1/k ≤ β_{n} ≤ 1 − 1/k for some k ∈ IN, ∑_{n=0}^{∞} γ_{n} ≤ E ∈ Q_{+}, and (u_{n}) be bounded with ∥u_{n} − x∥ ≤ u ∈ Q_{+}.

Then

∀δin(0, 1]∀g : IN → IN∃n ≤ Φ∀m ∈ [n, n + g(n)] (∥x_{m} − f(x_{m})∥ ≤ δ)

where Φ is as defined in theorem 4.1 with l = 1 + K.

Proof Direct corollary to the main theorem, using 1 + K ≥ 1 + k_{n} for any n as the Lipschitz constant. •

Corollary 4.7 Let C be a bounded convex subset of X with diameter d ∈ Q_{+}^{∗} and f be asymptotically nonexpansive with sequence (k_{n}), and also ∑_{n=0}^{∞} k_{n} ≤ K ∈ Q_{+}.

Let 1/k ≤ β_{n} ≤ 1 − 1/k for some k ∈ IN, ∑_{n=0}^{∞} γ_{n} ≤ E ∈ Q_{+}.

Then

∀δ ∈ (0, 1]∀g : IN → IN

∃n ≤ Φ_{2}(K, E, k, d, η, δ, g)∀m ∈ [n, n + g(n)] (∥x_{m} − f(x_{m})∥ ≤ δ)

where

Φ_{2}(K, E, k, d, η, δ, g) = h^{i}(0)
h = λn.(g(n + 1) + n + 1)
i = ⌊\frac{3(5Kd + 6Ed + d)k^{2}}{εη (ε/(d(1 + K)))} ⌋
ε = δ/(2(1 + (K + 1)(K + 2)(K + 3))).

Proof Using Lemma 3.7 we can fulfill the conditions of the previous corollary, and the boundedness of C allows us to replace all bounds on the distances in the proof with d. •

Concluding remark:

1) With somewhat more complicated bounds our analysis also extends to the case where f : C → C is instead of being l-uniformly Lipschitzian only ω-uniformly continuous, i.e.

∀ε > 0, n ∈ IN, x, y ∈ X(∥x − y∥ < ω(ε) → ∥f^{n}(x) − f^{n}(y)∥ < ε),

where ω : IR_{+}^{∗} → IR_{+}^{∗} (i.e. ω is what in constructive analysis is called a modulus of uniform continuity for all f^{n}). In particular, this covers the case of λ-α-uniformly Lipschitzian functions (see [24]).

2) We expect that our analysis can be adapted also to Ishikawa-type iterations. However, this would further complicate the technical details.

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] Berinde, V., Iterative approximation of fixed points. Efemeride, Baia Mare, xii+283pp. (2002).

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

[4] Diaz, J.B., Metcalf, F.T., On the structure of the set of subsequential limit points of successive approximations. Bull. Amer. Math. Soc. 73, pp. 516-519 (1967).

[5] Diaz, J.B., Metcalf, F.T., On the set of subsequential limit points of successive approximations. Trans. Amer. Math. Soc. 135, pp. 459-485 (1969).

[6] Dotson, W.G., Jr., On the Mann iterative process. Trans. Amer. Math. Soc. 149, pp. 65-73 (1970).

[7] Goebel, K., Concise Course of Fixed Point Theorems. Yokohama Publishers, Yokohama, iii+182pp. (2002).

[8] Goebel, K., Kirk, W.A., A fixed point theorem for asymptotically nonexpansive mappings. Proc. Amer. Math. Soc. 35, pp. 171-174 (1972).

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

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

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

[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. J. Math. Anal. Appl. 279, pp. 531-544 (2003).

[15] Kohlenbach, U., Some logical metatheorems with applications in functional analysis. To appear in: Trans. Amer. Math. Soc.

[16] Kohlenbach, U., Leuştean, L., Mann iterates of directionally nonexpansive mappings in hyperbolic spaces. Abstr. Appl. Anal. 2003, no.8, pp. 449-477 (2003).

[17] Kohlenbach, U., Oliva, P., Proof mining: a systematic way of analysing proofs in analysis. Proc. Steklov Inst. Math. 242, 136-164 (2003).

[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] Naimpally, S.A., Singh, K.L., Whitfield, J.H.M., Fixed points and sequences of iterates in locally convex spaces. In: Topological methods in nonlinear functional analysis. Contemp. Math. 21, Amer. Math. Soc., pp. 159-166 (1983).

[21] Opial, Z., Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Amer. Math. Soc. 73, pp. 595-597 (1967).

[22] Qihou, L., Iteration sequences for asymptotically quasi-nonexpansive mappings. J. Math. Anal. Appl. 259, pp. 1-7, (2001).

[23] Qihou, L., Iteration sequences for asymptotically quasi-nonexpansive mappings with error member. J. Math. Anal. Appl. 259, pp. 18-24 (2001).

[24] Qihou, L., Iteration sequences for asymptotically quasi-nonexpansive mapping with an error member of uniform convex Banach spcace. J. Math. Anal. Appl. 266, pp. 468-471 (2002).

[25] Rhoades, B.E., Fixed point iterations for certain nonlinear mappings. J. Math. Anal. Appl. 183, pp. 118-120 (1994).

[26] Schu, J., Iterative construction of fixed points of asymptotically nonexpansive mappings. J. Math. Anal. Appl. 158, pp. 407-413 (1991).

[27] Schu, J., Iterative construction of fixed points of strictly quasicontractive mappings. Appl. Anal. 40, pp. 67-72 (1991).

[28] Schu, J., Weak and strong convergence to fixed points of asymptotically nonexpansive mappings. Bull. Austral. Math. Soc. 43, pp. 153-159 (1991).

[29] Srivastava, P., Srivastava, S.C., On asymptotically quasinonexpansive families of mappings. In: Nonlinear analysis and applications (St.

Johns, 1981), Lecture Notes in Pure and Appl. Math. 80, pp. 265-270, Dekker (1982).

[30] Tan, K.-K., Xu, H.K., Fixed point iteration processes for asymptotically nonexpansive mappings. Proc. Amer. Math. Soc. 122, pp. 733-739 (1994).

[31] Xu,Y., Ishikawa and Mann iterative processes with errors for nonlinear strongly accretive operator equations. J. Math. Anal. Appl. 224, pp. 91-101 (1998).

Recent BRICS Report Series Publications

RS-03-51 Ulrich Kohlenbach and Branimir Lambov. Bounds on Iterations of Asymptotically Quasi-Nonexpansive Mappings. December 2003. 24 pp.

RS-03-50 Branimir Lambov. A Two-Layer Approach to the Computability and Complexity of Real Numbers. December 2003. 16 pp.

RS-03-49 Marius Mikucionis, Kim G. Larsen, and Brian Nielsen. Online On-the-Fly Testing of Real-time Systems. December 2003. 14 pp.

RS-03-48 Kim G. Larsen, Ulrik Larsen, Brian Nielsen, Arne Skou, and Andrzej Wasowski. Danfoss EKC Trial Project Deliverables. December 2003. 53 pp.

RS-03-47 Hans Hüttel and Jiří Srba. Recursive Ping-Pong Protocols. December 2003. To appear in the proceedings of 2004 IFIP WG 1.7, ACM SIGPLAN and GI FoMSESS Workshop on Issues in the Theory of Security (WITS’04).

RS-03-46 Philipp Gerhardy. The Role of Quantifier Alternations in Cut Elimination. December 2003. 10 pp. Extends paper appearing in Baaz and Makowsky, editors, European Association for Computer Science Logic: 17th International Workshop, CSL ’03 Proceedings, LNCS 2803, 2003, pages 212-225.

RS-03-45 Peter Bro Miltersen, Jaikumar Radhakrishnan, and Ingo Wegener. On converting CNF to DNF. December 2003. 11 pp. A preliminary version appeared in Rovan and Vojtás, editors, Mathematical Foundations of Computer Science: 28th International Symposium, MFCS ’03 Proceedings, LNCS 2747, 2003, pages 612–621.

RS-03-44 Anna Gál and Peter Bro Miltersen. The Cell Probe Complexity of Succinct Data Structures. December 2003. 17 pp. An early version of this paper appeared in Baeten, Lenstra, Parrow and Woeginger, editors, 30th International Colloquium on Automata, Languages, and Programming, ICALP ’03 Proceedings, LNCS 2719, 2003, pages 332–344.

RS-03-43 Mikkel Nygaard and Glynn Winskel. Domain Theory for Concurrency. December 2003. 45 pp. To appear in a Theoretical Computer Science special issue on Domain Theory.