BRICS

Basic Research in Computer Science

A Quantitative Version of Kirk’s Fixed Point Theorem for Asymptotic Contractions

Philipp Gerhardy

BRICS Report Series RS-04-32 ISSN 0909-0878 December 2004 BRICS RS-04-32 P. Gerhardy: A Quantitative Version of Kirk’s Fixed Point Theorem for Asymptotic Contractions Copyright \begin{matrix}c \\ ◯ \end{matrix} 2004, Philipp Gerhardy.

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/04/32/

A quantitative version of Kirk’s fixed point theorem for asymptotic contractions

Philipp Gerhardy

December, 2004

Abstract

In [J.Math.Anal.App.277(2003) 645-650], W.A.Kirk introduced the notion of asymptotic contractions and proved a fixed point theorem for such mappings. Using techniques from proof mining, we develop a variant of the notion of asymptotic contractions and prove a quantitative version of the corresponding fixed point theorem.

1 Introduction

In [3], W.A. Kirk proved a fixed-point theorem for so-called asymptotic contractions on complete metric spaces, showing that given a continuous^{1} asymptotic contraction f for every starting point x the iteration sequence {f^{n}(x)} converges to the unique fixed point of f. The proof is non-elementary, as it uses an ultrapower construction to establish the fixed point theorem. Recent alternative proofs by Jachymski and Jóźwik[2], additionally assuming that f is uniformly continuous, and by Arandelović [1], under the same assumptions as Kirk, are elementary and avoid ultrapowers, but neither of the three proofs provides explicit rates of convergence.

1In [2, 1], it is discussed that the requirement that f is continuous is a necessary condition for Kirk’s fixed point theorem. By an oversight the requirement was left out in the original statement of Kirk’s fixed point theorem in [3]

Using techniques from proof mining as developed e.g. in [5, 4], we first derive a suitable generalization of the notion of asymptotic contractivity and subsequently give an elementary proof of Kirk’s fixed point theorem, providing an explicit rate of convergence^{2} (to the unique fixed point) for sequences {f^{n}(x)}.

In detail, we show that:

• the rate of convergence only depends on the starting point x via a bound on the iteration sequence {f^{n}(x)},

• the rate of convergence only depends on the function f via suitable moduli expressing its asymptotic contractivity,

• the continuity of f is only necessary to prove the existence of a unique fixed point, while the convergence to such a fixed point can be proved without the continuity of f.

2 Preliminaries

In [3], Kirk defines asymptotic contractions as follows:

Definition 2.1 (Kirk[3]). A function f : X → X on a metric space (X, d) is called an asymptotic contraction with moduli ϕ, ϕ_{n} : [0, ∞) → [0, ∞) if ϕ, ϕ_{n} are continuous, ϕ(s) < s for all s > 0 and for all x, y ∈ X

d(f^{n}(x), f^{n}(y)) ≤ ϕ_{n}(d(x, y))

and moreover ϕ_{n} → ϕ uniformly on the range of d.

What is needed to prove the fixed point theorem are not so much the moduli ϕ, ϕ_{n}, but instead a function η producing a witness of the inequality ϕ(s) < s and a modulus of convergence β for ϕ_{n} yielding a K s.t. for all k ≥ K ϕ_{k} is close enough to ϕ and hence f^{k} is a contraction. For η it is sufficient to provide a witness for every interval [l, b], for β it suffices to have uniform convergence on every interval [l, b], in both cases with 0 < l ≤ b < ∞.

2Since an asymptotic contraction need not be non-expansive (cf. Example 2 in [2]), convergence need not be monotone, and hence an effective rate of convergence can at most produce a bound M s.t. f^{m}(x) is close to the unique fixed point for some m ≤ M. We will discuss the details later.

Thus, to give an elementary and effective proof of the fixed point theorem proved by Kirk, we derive the following generalized definition of asymptotic contractions:

Definition 2.2. A function f : X → X on a metric space (X, d) is called an asymptotic contraction if for each b > 0 there exist moduli η^{b} : (0, b] → (0, 1) and β^{b} : (0, b] × (0, ∞) → IN and the following hold:

(1) there exists a sequence of functions ϕ_{n} : (0, ∞) → (0, ∞) s.t. for all x, y ∈ X, for all ε > 0 and for all n ∈ IN

b ≥ d(x, y) ≥ ε → d(f^{n}(x), f^{n}(y)) ≤ ϕ_{n}(ε) · d(x, y),

(2) for each 0 < l ≤ b the function β_{l}^{b} := β^{b}(l, ·) is a modulus of uniform convergence for ϕ_{n} on [l, b], i.e.

∀ε > 0 ∀s ∈ [l, b] ∀m, n ≥ β_{l}^{b}(ε) (|ϕ_{m}(s) − ϕ_{n}(s)| ≤ ε),

and (3) defining ϕ := lim_{n→∞} ϕ_{n}, then for each ε > 0 we have that η^{b}(ε) > 0

and ϕ(s) + η^{b}(ε) ≤ s for each s ∈ [ε, b].

All the relevant information is contained in the moduli η and β and we do not need to refer to ϕ, ϕ_{n} at all, as the following proposition shows:

Proposition 2.3. Let (X, d) be a metric space, let f be an asymptotic contraction and let b > 0 and η^{b}, β^{b} be given. Then for every ε > 0 there is a K(η^{b}, β^{b}, ε) s.t. for all k ≥ K, where K = β_{ε}^{b}(\frac{η^{b}(ε)}{2}),

b ≥ d(x, y) ≥ ε → d(f^{k}(x), f^{k}(y)) ≤ (1 − \frac{η^{b}(ε)}{2}) · d(x, y).

Proof: Let K = β_{ε}^{b}(\frac{η^{b}(ε)}{2}), let a suitable sequence ϕ_{n} be given and let ϕ := lim_{n→∞} ϕ_{n}. By the definition of η^{b} we have that ϕ(s) + η^{b}(ε) ≤ 1 for s ∈ [ε, b].

By the definition of β^{b} the function ϕ_{k} is at least \frac{η^{b}(ε)}{2}-close to ϕ for all k ≥ K and for all s ∈ [ε, b] and hence also ϕ_{k}(s) ≤ 1 − \frac{η^{b}(ε)}{2}.

Remark 2.4. Requiring moduli η^{b} and β^{b} for each individual b > 0 instead of one pair of moduli for all b > 0 is no restriction. In the proof given in [3], it is assumed that some iteration sequence of the asymptotic contraction f is bounded, which allows to prove that every iteration sequence is bounded. As we will see, to prove the fixed point theorem it suffices to have moduli η^{b} and β^{b} for the corresponding b-bounded subsets of (X, d).

Next, we show that Kirk’s notion of asymptotic contractivity implies the more general notion in Definition 2.2.

Definition 2.5. Let the function ϕ, a sequence of functions ϕ_{n} and b > 0 be given. Define:

ϕ′(s) := \frac{ϕ(s)}{s} for s ∈ (0, ∞),  ϕ′_{n}(s) := \frac{ϕ_{n}(s)}{s} for s ∈ (0, ∞),
ϕ′′(s) := max_{t∈[s,b]} ϕ′(t) for s ∈ (0, b], ϕ′′_{n}(s) := max_{t∈[s,b]} ϕ′_{n}(t) for s ∈ (0, b].

Proposition 2.6. Let ϕ : [0, ∞) → [0, ∞) be continuous, let ϕ satisfy ϕ(s) < s for s > 0 and let ϕ_{n} : [0, ∞) → [0, ∞) be a sequence of continuous functions converging uniformly to ϕ. Then

• ϕ′ and ϕ′_{n} are continuous on (0, ∞), ϕ′(s) < 1 for all s ∈ (0, ∞) and the sequence ϕ′_{n} converges uniformly to ϕ′ on [l, ∞) for each l > 0,

• ϕ′′ and ϕ′′_{n} are continuous on (0, b], ϕ′′(s) < 1 for all s ∈ (0, b] and the sequence ϕ′′_{n} converges uniformly to ϕ′′ on [l, b] for each 0 < l ≤ b < ∞.

Proof: Obvious.

Remark 2.7. The moduli η^{b}, β^{b} may equivalently be given as functions η^{b} : IN → IN and β^{b} : IN × IN → IN, where real numbers are approximated from below by suitable 2^{−n}. Given b > 0, if ϕ and a modulus β for ϕ_{n} are given as computable number-theoretic functions, then η^{b} and β_{l}^{b} are effectively computable in b.

Proposition 2.8. If a function f : X → X on a metric space (X, d) is an asymptotic contraction with moduli ϕ, ϕ_{n}, then the function f is an asymptotic contraction with suitable moduli η^{b}, β^{b} for every b > 0.

Proof: Follows from the above remarks and constructions.

3 Main results

We are now in position to give an elementary proof of Kirk’s fixed point theorem. The general idea of the proof is similar to the constructivization of Edelstein’s fixed point theorem in [5]. We first derive (variants of) a modulus of uniqueness and of a modulus of asymptotic regularity. These two moduli combined give us a modulus of convergence for the iteration sequence and thereby of the convergence to the unique fixed point.

Throughout this section we assume that f : X → X is a self-mapping on a metric space (X, d). Given x_{0} ∈ X we write x_{n} for f^{n}(x_{0}) and {x_{n}} for the corresponding iteration sequence. When there is no ambiguity we will omit the superscript b from the moduli η^{b}, β^{b}.

Lemma 3.1. Let (X, d) be a metric space, let f be an asymptotic contraction and let b > 0 and η, β be given. Then for every b ≥ ε > 0, for all n ≥ N and all x, y ∈ X with d(x, y) ≤ b

d(x, f^{n}(x)), d(y, f^{n}(y)) ≤ δ → d(x, y) ≤ ε,

where δ(η, ε) = \frac{η(ε)·ε}{4} and N(η, β, ε) = β_{ε}(\frac{η(ε)}{2}).

Proof: Let b ≥ ε > 0 be given. Let n ≥ N, then by Proposition 2.3

b ≥ d(x, y) ≥ ε → d(f^{n}(x), f^{n}(y)) ≤ (1 − \frac{η(ε)}{2}) · d(x, y).

Let d(x, f^{n}(x)), d(y, f^{n}(y)) ≤ δ, with δ = \frac{η(ε)·ε}{4} as described above and assume d(x, y) > ε. Then by the triangle inequality

\begin{aligned}d(x, y) & ≤ d(x, f^{n}(x)) + d(f^{n}(x), f^{n}(y)) + d(y, f^{n}(y)) \\ & ≤ \frac{η(ε)·ε}{2} + (1 − \frac{η(ε)}{2}) · d(x, y) \end{aligned}

and hence \frac{η(ε)}{2} ·d(x, y) ≤ \frac{η(ε)}{2} ·ε which implies d(x, y) ≤ ε. But this contradicts the assumption d(x, y) > ε and therefore d(x, y) ≤ ε.

Lemma 3.2. Let (X, d) be a metric space, let f be an asymptotic contraction and let b > 0 and η, β be given. Then for every δ > 0, for every x_{0} ∈ X s.t. {x_{n}} is bounded by b and for every N there exists an m ≤ M, s.t.

d(x_{m}, f^{N}(x_{m}) < δ,

where M(η, β, δ, b) = k · ⌈(_{\frac{lg(δ)−lg(b)}{lg(1− \frac{η(δ)}{2} )}})⌉ with k = β_{δ}(\frac{η(δ)}{2}).

Proof: Let k = β_{δ}(\frac{η(δ)}{2}). Assume for some M_{0} and all m < M_{0} we have d(x_{mk}, f^{N}(x_{mk})) ≥ δ, then

d(x_{M_{0}k}, f^{N}(x_{M_{0}k})) ≤ (1 − \frac{η(δ)}{2})^{M_{0}}d(x_{0}, f^{N}(x_{0})) ≤ (1 − \frac{η(δ)}{2})^{M_{0}} · b

since by assumption d(x_{0}, f^{N}(x_{0})) ≤ b.

Solving the inequality (1− \frac{η(δ)}{2})^{M_{0}} ·b < δ w.r.t. M_{0} yields the described upper bound M = k · M_{0} on an m s.t. d(x_{m}, f^{N}(x_{m})) < δ.

Remark 3.3. Bounding m by M is in this context optimal. Since f^{k} only is a contraction with constant (1 − \frac{η(δ)}{2}) for x, y s.t. d(x, y) ≥ δ, we cannot be certain, that d(x_{M}, f^{N}(x_{M})) < δ. If for some earlier m < M we have d(x_{m}, f^{N}(x_{m})) < δ, then for these points we no longer have the guarantee that f^{k} is a contraction, and hence we have no (computable) control over the next iteration step, i.e. over d(x_{m+k}, f^{N}(x_{m+k})). If the function f and the space (X, d) have a computable representation one can of course check x_{0}, …, x_{M} to find which one is close to the unique fixed point z.

Theorem 3.4. Let (X, d) be a metric space, let f be an asymptotic contraction and let b > 0 and η, β be given. Assume that f has a (unique) fixed point z. Then for every ε > 0 and every x_{0} ∈ X s.t. {x_{n}} is bounded by b and d(x_{n}, z) ≤ b for all n there exists an m ≤ M s.t.

d(x_{m}, z) ≤ ε,

where M(η, β, ε, b) = k · ⌈(_{\frac{lg(δ)−lg(b)}{lg(1− \frac{η(δ)}{2} )}})⌉, k = β_{δ}(\frac{η(δ)}{2}), δ = \frac{η(ε)·ε}{4}.

Proof: By Lemma 3.1 for every ε > 0 there exist δ, N as described above s.t. if d(x, f^{N}(x)), d(y, f^{N}(x)) ≤ δ then d(x, y) ≤ ε. Any (trivially unique) fixed point z of f satisfies d(z, f^{N}(z)) = 0 ≤ δ, so if d(x, f^{N}(x)) ≤ δ then d(x, z) ≤ ε.

Now, by Lemma 3.2 for every δ and every N we can find an m ≤ M as described above s.t. d(x_{m}, f^{N}(x_{m})) < δ and hence x_{m} is ε-close to the fixed point z.

Note, that the rate of convergence does not depend on the starting point x_{0}, but only on a bound b on {x_{n}}. Also, the rate of convergence only depends on f via the moduli η, β. Finally, if we know that a fixed point z exists, we do not need the continuity of f to prove {x_{n}} converges to z.

Lemma 3.5. Let (X, d) be a metric space, let f be an asymptotic contraction and let b > 0 and η, β be given. Then for every δ > 0, for every x_{0} ∈ X s.t. {x_{n}} bounded by b and for every N there exists an M s.t. for all m ≥ M

d(x_{m}, f^{N}(x_{m})) < δ.

Proof: By Lemma 3.2 there exists an m s.t. d(x_{m}, f^{N}(x_{m})) < δ. Either d(x_{m}, f^{N}(x_{m})) = 0 – then we are done – or d(x_{m}, f^{N}(x_{m})) > ε_{0} for some ε_{0} > 0.

Let K = β_{ε_{0}}(\frac{η(ε_{0})}{2}), then it follows by Proposition 2.3 that for all k ≥ K

d(x_{m+k}), f^{N}(x_{m+k})) ≤ (1 − \frac{η(ε_{0})}{2})d(x_{m}, f^{N}(x_{m})) < δ.

Let M = m + K and the result follows.

Lemma 3.6. Let (X, d) be a metric space, let f be an asymptotic contraction and let b > 0 and η, β be given. If {x_{n}} is bounded by b then {x_{n}} is a Cauchy sequence.

Proof: By Lemma 3.1 for every ε > 0 there exists a δ > 0 and an N s.t. for all x, y ∈ X if d(x, f^{N}(x)), d(y, f^{N}(y) ≤ δ then d(x, y) ≤ ε. By Lemma 3.5 for every δ > 0 and every N there exists an M s.t. d(x_{m}, f^{N}(x_{m})) < δ for all m ≥ M. Then d(x_{m}, x_{n}) ≤ ε for all m, n ≥ M.

Theorem 3.7. Let (X, d) be a complete metric space, let f be a continuous asymptotic contraction and let b > 0 and η, β be given. If for some x_{0} ∈ X the sequence {x_{n}} is bounded by b then f has a unique fixed point z, {x_{n}} converges to z and for every ε > 0 there exists an m ≤ M s.t.

d(x_{m}, z) ≤ ε,

where M is as in Theorem 3.4.

Proof: By Lemma 3.6 every iteration sequence {x_{n}} which is bounded is a Cauchy sequence. Since (X, d) is complete the limit z of {x_{n}} exists. To show that z is a fixed point we show that d(z, f(z)) ≤ ε for every ε > 0. Every fixed point of f is trivially unique.

Since {x_{n}} is a Cauchy sequence and z is the limit, for every δ > 0 there is an M s.t. d(x_{m}, z), d(x_{m}, f(x_{m})) ≤ δ for all m ≥ M. Next, since f is continuous at z for every ε_{0} > 0 there is a δ_{0} > 0 s.t. for all x if d(x, z) ≤ δ_{0} then d(f(x), f(z)) ≤ ε_{0}.

Let ε > 0 be given, choose δ_{0} for ε_{0} = ε/3 and M s.t. d(x_{m}, z), d(x_{m}, f(x_{m})) ≤ min(δ_{0}, ε/3) for all m ≥ M, then

\begin{aligned}d(z, f(z)) & ≤ d(x_{m}, z) + d(x_{m}, f(x_{m})) + d(f(x_{m}), f(z)) \\ & ≤ ε/3 + ε/3 + ε/3 = ε. \end{aligned}

The rate of convergence M follows by Theorem 3.4.

Remark 3.8. By Remark 2.4 and Proposition 2.8 this implies Kirk’s fixed point theorem for asymptotic mappings in [3].

Definition 3.9. A function f : X → X is called quasi-nonexpansive if

∀x, p ∈ X(f(p) = p → d(f(x), p) ≤ d(x, p)).

Corollary 3.10. Let (X, d) be a complete metric space, let f be a continuous, quasi-nonexpansive asymptotic contraction and let b > 0 and η, β be given. If for some x_{0} the sequence {x_{n}} is bounded by b then f has a unique fixed point z, {x_{n}} converges to z and for every ε > 0 and all n ≥ M

d(x_{n}, z) ≤ ε,

where M(η, β, ε, b) is as in Theorem 3.4.

Proof: By Theorem 3.7 there exists m ≤ M s.t. d(x_{m}, z) ≤ ε where z is the unique fixed point of f and M is given as in Theorem 3.4. The function f is quasi-nonexpansive, so for all n ≥ M ≥ m we have that d(x_{n}, z) ≤ d(x_{m}, z) and hence also d(x_{n}, z) ≤ ε.

Acknowledgements: I am grateful to Ulrich Kohlenbach for many useful discussions on the subject and helpful suggestions for improving the presentation of the material in this article.

References

[1] I. D. Arandelović. On a fixed point theorem by Kirk. J. Math. Anal. Appl., 301:384–385, 2005.

[2] J. Jachymski and I. Jóźwik. On Kirk’s asymptotic contractions. J. Math. Anal. Appl., 300:147–159, 2004.

[3] W. A. Kirk. Fixed points of asymptotic contractions. J. Math. Anal. Appl., 277:645–650, 2003.

[4] U. Kohlenbach. Some Logical Metatheorems with Applications in Functional Analysis. Trans. Am. Math. Soc., 357:89–128, 2005.

[5] U. Kohlenbach and P. Oliva. Proof Mining: A Systematic Way of Analyzing Proofs in Mathematics. Proc. Steklov Inst. Math, 242:136–164, 2003.

Recent BRICS Report Series Publications

RS-04-32 Philipp Gerhardy. A Quantitative Version of Kirk’s Fixed Point Theorem for Asymptotic Contractions. December 2004. 9 pp.

RS-04-31 Philipp Gerhardy and Ulrich Kohlenbach. Strongly Uniform Bounds from Semi-Constructive Proofs. December 2004. 31 pp.

RS-04-30 Olivier Danvy. From Reduction-Based to Reduction-Free Normalization. December 2004. 27 pp. Invited talk at the 4th International Workshop on Reduction Strategies in Rewriting and Programming, WRS 2004 (Aachen, Germany, June 2, 2004).

RS-04-29 Ma�gorzata Biernacka, Dariusz Biernacki, and Olivier Danvy. An Operational Foundation for Delimited Continuations in the CPS Hierarchy. December 2004. iii+45 pp.

RS-04-28 Mads Sig Ager, Olivier Danvy, and Jan Midtgaard. A Functional Correspondence between Monadic Evaluators and Abstract Machines for Languages with Computational Effects. December 2004. 44 pp. To appear in Theoretical Computer Science.

RS-04-27 Gerth Stølting Brodal, Rolf Fagerberg, and Gabriel Moruz. On the Adaptiveness of Quicksort. December 2004. 23 pp. To appear in Demetrescu and Tamassia, editors, Seventh Workshop on Algorithm Engineering and Experiments, ALENEX ’05 Proceedings, 2005.

RS-04-26 Olivier Danvy and Lasse R. Nielsen. Refocusing in Reduction Semantics. November 2004. iii+44 pp. This report supersedes BRICS report RS-02-04. A preliminary version appears in the informal proceedings of the Second International Workshop on Rule-Based Programming, RULE 2001, Electronic Notes in Theoretical Computer Science, Vol. 59.4.

RS-04-25 Mayer Goldberg. On the Recursive Enumerability of Fixed-Point Combinators. November 2004. 7 pp.

RS-04-24 Luca Aceto, Willem Jan Fokkink, Anna Ingólfsdóttir, and Sumit Nain. Bisimilarity is not Finitely Based over BPA with Interrupt. October 2004. 30 pp.

RS-04-23 Hans Hüttel and Jiří Srba. Recursion vs. Replication in Simple Cryptographic Protocols. October 2004. 26 pp. To appear in Vojtas, editor, 31st Conference on Current Trends in Theory and Practice of Informatics, SOFSEM ’05 Proceedings, LNCS,