Contractive Mappings on Metric Spaces with Graphs

Abstract

We establish fixed point, stability and genericity theorems for strict contractions on complete metric spaces with graphs.

1. Introduction

For nearly sixty years now, there has been a lot of research activity regarding the fixed point theory of nonexpansive (that is, 1-Lipschitz) and contractive mappings. See, for example, Refs. [1,2,3,4,5,6,7,8,9,10,11,12,13,14] and references cited therein. This activity stems from Banach’s classical theorem [15] concerning the existence of a unique fixed point for a strict contraction. It also concerns the convergence of (inexact) iterates of a nonexpansive mapping to one of its fixed points. Since that seminal result, many developments have taken place in this field including, in particular, studies of feasibility, common fixed point problems, nonlinear operator theory and variational inequalities, which find important applications in engineering, medical and the natural sciences [13,14,16,17,18,19]. In particular, the study of nonexpansive and contractive mappings on complete metric spaces with graphs has recently become a rapidly growing area of research. See, for instance, Refs. [9,10,20]. In the present paper we establish fixed point, stability and genericity theorems for strict contractions on complete metric spaces with graphs (see Section 3 and Section 4 below).

2. Preliminaries

Let $(X,\rho )$ be a complete metric space and let G be a (directed) graph. Let $V(G)$ be the set of its vertices and let $E(G)$ be the set of its edges. We identify the graph G with the pair $(V(G),E(G))$.

Denoted by ${\mathcal{M}}_{ne}$ is the set of all mappings $T:X\to X$ such that for each $x,y\in X$ satisfying $(x,y)\in E(G)$, we have

$$(T(x),T(y))\in E(G) \mathrm{a}\mathrm{n}\mathrm{d} \rho (T(x),T(y))\le \rho (x,y).$$

(1)

A mapping $T\in {\mathcal{M}}_{ne}$ is called G-nonexpansive. If $T\in {\mathcal{M}}_{ne}$, $\alpha \in (0,1)$ and for each $x,y\in X$ satisfying $(x,y)\in E(G)$, we have

$$\rho (T(x),T(y))\le \alpha \rho (x,y),$$

(2)

then T is called a G-strict contraction.

Fix $\theta \in X$. For each $x\in X$ and each $r>0$, set

$$B_{\rho }(x,r):=\{y\in X:\rho (x,y)\le r\}.$$

We may assume without loss of generality that if $x,y\in X$ satisfies $(x,y)\in E(G)$, then

$$(y,x)\in E(G).$$

In this paper, we assume the following assumption:

(P) For each $x,y\in X$, there exist an integer $q\ge 1$ and points $x_i\in X$, $i=0,\dots ,q$, such that

$$x_0=x,x_q=y,(x_i,x_{i+1})\in E(G),i=0,\dots ,q-1.$$

Thus, $V(G)=X$ and the graph G is connected.

Let $T\in {\mathcal{M}}_{ne}$ be a G-strict contraction. It is known [20] that under certain mild assumptions, the mapping T has a unique fixed point which attracts all the iterates of T. In the present paper we provide a very simple proof of this fact by using a certain metric on X which is defined below (see Theorem 1). Then we establish (see Theorem 2) uniform convergence of the iterates of T on bounded subsets of X and show that this convergence is stable under small perturbations of these iterates (Theorems 3 and 4). All these results are stated and proved in Section 3. In Section 4, under certain assumptions, we show that a typical G-nonexpansive mapping has a unique fixed point which attracts all its iterates, uniformly on bounded subsets of X.

For each $x,y\in X$, define

$${\rho }_1(x,y):=\inf \{\sum _{i=0}^{q-1}\rho (x_i,x_{i+1}):q\ge 1 \mathrm{i}\mathrm{s} \mathrm{a}\mathrm{n} \mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{g}\mathrm{e}\mathrm{r},$$

$$x_i\in X,i=0,\dots ,q,x_0=x,x_q=y,(x_i,x_{i+1})\in E(G),i=0,\dots ,q-1\}.$$

(3)

It is easy to see that for each $x,y,z\in X$, ${\rho }_1(x,y)$ is finite,

$${\rho }_1(x,y)\ge \rho (x,y),$$

(4)

$${\rho }_1(x,y)={\rho }_1(y,x),$$

$${\rho }_1(x,z)\le {\rho }_1(x,y)+{\rho }_1(y,z),$$

and if ${\rho }_1(x,y)=0$, then $x=y$. However, ${\rho }_1$ is a metric only if $(x,x)\in E(G)$ for all $x\in X$. This pseudometric ${\rho }_1$ plays an important role in this paper because it turns out that if a mapping T is G-nonexpansive (respectively, a G-strict contraction), then it is nonexpansive (respectively, a strict contraction) with respect to the pseudometric ${\rho }_1$.

Given a mapping $S:X\to X$, we define $S^0=I$, the identity self-mapping on X, $S^1=S$, and $S^{i+1}=S\circ S^i$ for all integers $i\ge 0$. For each $x\in X$ and each $r>0$, we set

$$B_{{\rho }_1}(x,r):=\{y\in X:{\rho }_1(x,y)\le r\}.$$

3. Strict Contractions

In this section, we are concerned with mappings $T\in {\mathcal{M}}_{ne}$ which are G-strict contractions. For such a mapping T, we establish the existence of a unique fixed point and show that the (inexact) iterates of T converge to this unique fixed point, uniformly on bounded subsets of the space $(X,\rho )$.

Theorem 1.

Let $T\in {\mathcal{M}}_{ne}$, $\alpha \in (0,1)$ and assume that for each $x,y\in X$ satisfying $(x,y)\in E(G)$, inequality (2) holds. Then for each $x,y\in X$, we have

$${\rho }_1(T(x),T(y))\le \alpha {\rho }_1(x,y).$$

If T is continuous as a self-mapping of $(X,\rho )$, then there exists a unique point $x_{*}\in X$ satisfying $T(x_{*})=x_{*}$ and for each $x\in X$,

$$\underset{i\to \infty }{\lim }{T}^i(x)=x_{*} in (X,\rho ).$$

Proof. 

Assume that $x,y\in X$, q is an integer, and that

$$x_i\in X,i=0,\dots ,q,x_0=x,x_q=y,(x_i,x_{i+1})\in E(G),i=0,\dots ,q-1.$$

(5)

By (2) and (5), we have

$$T(x)=T(x_0),T(y)=T(x_q),(T(x_i),T(x_{i+1}))\in E(G),i=0,\dots ,q-1,$$

and

$$\rho (T(x_i),T(x_{i+1}))\le \alpha \rho (x_i,y_i),i=0,\dots ,q-1.$$

When combined with (3), these relations imply that

$${\rho }_1(T(x),T(y))\le \sum _{i=0}^{q-1}\rho (T(x_i),T(x_{i+1}))\le \alpha \sum _{i=0}^{q-1}\rho (x_i,x_{i+1}).$$

Since the above inequalities hold for each integer $q\ge 1$ and every finite sequence ${\{x_i\}}_{i=0}^q$ satisfying (5), we conclude that

$${\rho }_1(T(x),T(y))\le \alpha {\rho }_1(x,y).$$

(6)

Assume now that T is continuous, $x\in X$ and consider the sequence of iterates ${\{T^i(x)\}}_{i=0}^{\infty }$. By (6), for each integer $i\ge 0$, we have

$${\rho }_1(T^{i+1}(x),T^{i+2}(x))\le \alpha {\rho }_1(T^i(x),T^{i+1}(x))$$

and

$$\sum _{i=0}^{\infty }{\rho }_1(T^i(x),T^{i+1}(x))<\infty .$$

When combined with (4), this implies that

$$\sum _{i=0}^{\infty }\rho (T^i(x),T^{i+1}(x))<\infty$$

and that ${\{T^i(x)\}}_{i=0}^{\infty }$ is a Cauchy sequence in $(X,\rho )$. Thus, there exists

$$x_{*}=\underset{i\to \infty }{\lim }{T}^i(x)$$

in $(X,\rho )$. Since T is assumed to be continuous, it follows that $T(x_{*})=x_{*}$. If a point $y_{*}\in X$ also satisfies $T(y_{*})=y_{*}$, then in view of (6),

$${\rho }_1(x_{*},y_{*})={\rho }_1(T(x_{*}),T(y_{*}))\le \alpha {\rho }_1(x_{*},y_{*})$$

and

$${\rho }_1(x_{*},y_{*})=0.$$

When combined with (4) this equality implies that $x_{*}=y_{*}$. This completes the proof of Theorem 1. □

Theorem 2.

Let all the assumptions of Theorem 1 hold, let the mapping T be continuous as a self-mapping of $(X,\rho )$ and let $x_{*}\in X$ be as guaranteed by Theorem 1 and satisfy

$$x_{*}=T(x_{*}).$$

Suppose that the following assumption holds.

(A1) For each $M_0>0$, there exists $M_1>0$ such that for each point $x\in B_{\rho }(\theta ,M_0)$, we have

$${\rho }_1(x,\theta )\le M_1.$$

Then $T^i(x)\to x_{*}$ as $i\to \infty$ in $(X,\rho )$, uniformly on all bounded subsets of $(X,\rho )$.

Proof. 

Let $ϵ,M_0>0$ be given. By (A1), there exists $M_1>0$ such that

$$B_{\rho }(\theta ,M_0)\subset B_{{\rho }_1}(\theta ,M_1).$$

(7)

We may assume without any loss of generality that

$$x_{*}\in B_{\rho }(\theta ,M_0).$$

(8)

Choose a natural number $n_0$ such that

$$2M_1{\alpha }^{n_0}<ϵ.$$

(9)

Next, assume that

$$x\in B_{\rho }(\theta ,M_0).$$

(10)

By (8) and (10),

$${\rho }_1(x,\theta )\le M_1,{\rho }_1(x_{*},\theta )\le M_1,$$

$${\rho }_1(x,x_{*})\le 2M_1.$$

(11)

It now follows from Theorem 1, (2), (9) and (11) that for all natural numbers $n\ge n_0$, we have

$$\rho (T^n(x),x_{*})\le {\rho }_1(T^n(x),x_{*})\le {\alpha }^n{\rho }_1(x,x_{*})\le 2{\alpha }^{n_0}{M}_1<ϵ.$$

This completes the proof of Theorem 2. □

Theorem 3.

Let all the assumptions of Theorem 2 hold and let $x_{*}\in X$ be as guaranteed by Theorem 1 and satisfy

$$x_{*}=T(x_{*}).$$

Suppose that T is uniformly continuous and bounded on bounded sets as a self-mapping of $(X,\rho )$ and let $ϵ,M>0$ be given. Then there exist $\delta >0$ and a natural number $n_0$ such that for each integer $n\ge n_0$ and every finite sequence ${\{x_i\}}_{i=0}^n\subset X$ satisfying

$$x_0\in B_{\rho }(\theta ,M)$$

and

$$\rho (x_{i+1},T(x_i))\le \delta ,i=0,\dots ,n-1,$$

the inequality $\rho (x_i,x_{*})\le ϵ$ holds for all $i=n_0,\dots ,n$.

Theorem 3 follows from Theorem 2 and Theorem 2.65 of [12], which was obtained in [21].

Denoted by $\mathcal{M}$ is the set of all mappings $S\in {\mathcal{M}}_{ne}$ which are uniformly continuous and bounded on bounded sets as self-mappings of $(X,\rho )$. We equip the space $\mathcal{M}$ with the uniformity which has the base

$$\mathcal{E}(ϵ,M)=\{(S_1,S_2)\in \mathcal{M}\times \mathcal{M}:\rho (S_1(x),S_2(x))\le ϵ \mathrm{f}\mathrm{o}\mathrm{r} \mathrm{a}\mathrm{l}\mathrm{l} x\in B(\theta ,M)\},$$

where $M,ϵ>0$. It is not difficult to see that the uniform space $\mathcal{M}$ is metrizable and complete (by a metric d).

Our next theorem follows from Theorem 2 and Theorem 2.68 of [12], which was obtained in [21].

Theorem 4.

Let all the assumptions of Theorem 2 hold and let $x_{*}\in X$ be as guaranteed by Theorem 1 and satisfy

$$x_{*}=T(x_{*}).$$

Suppose that $T\in \mathcal{M}$ and that $ϵ,M>0$ are given. Then there exist a neighborhood $\mathcal{U}$ of T in $\mathcal{M}$ and a natural number $n_0$ such that for each $C\in \mathcal{U}$, each $x\in B_{\rho }(\theta ,M)$ and each integer $n\ge n_0$, we have

$$\rho (C^n(x),x_{*})\le ϵ.$$

4. Generic Results

In this section, we assume that X is a closed subset of a complete hyperbolic space $(Y,\rho ,M)$, the definition of which we now recall.

Let $(Y,\rho )$ be a metric space and let $R^1$ denote the real line. We say that a mapping $c:R^1\to Y$ is a metric embedding of $R^1$ into Y if $\rho (c(s),c(t))=|s-t|$ for all real s and t. The image of $R^1$ under a metric embedding will be called a metric line. The image of a real interval $[a,b]$$=\{t\in R^1:a\le t\le b\}$ under such a mapping will be called a metric segment.

Assume that $(Y,\rho )$ contains a family M of metric lines such that for each pair of distinct points x and y in Y, there is a unique metric line in M which passes through x and y. This metric line determines a unique metric segment joining x and y. We denote this segment by $[x,y]$. For each $0\le t\le 1$, there is a unique point z in $[x,y]$ such that

$$\rho (x,z)=t\rho (x,y) \mathrm{a}\mathrm{n}\mathrm{d} \rho (z,y)=(1-t)\rho (x,y).$$

This point will be denoted by $(1-t)x\oplus ty$. We will say that Y, or more precisely $(Y,\rho ,M)$, is a hyperbolic space if

$$\rho (\frac{1}{2}x\oplus \frac{1}{2}y,\frac{1}{2}x\oplus \frac{1}{2}z)\le \frac{1}{2}\rho (y,z)$$

for all $x,y$ and z in Y. An equivalent requirement is that

$$\rho (\frac{1}{2}x\oplus \frac{1}{2}y,\frac{1}{2}w\oplus \frac{1}{2}z)\le \frac{1}{2}(\rho (x,w)+\rho (y,z))$$

for all $x,y,z$ and w in Y. A set $K\subset Y$ is called $\rho$-convex if $[x,y]\subset K$ for all x and y in K.

It is clear that all normed linear spaces are hyperbolic. A discussion of more examples of hyperbolic spaces and, in particular, of the Hilbert ball can be found, for example, in [4,22].

Now let X be a closed subset of a complete hyperbolic space $(Y,\rho ,M)$, let $\theta \in X$ and let assumption (A1) hold. In addition, we assume in the sequel that the following assumption also holds true.

(A2) For each $x\in X$, each $(y,z)\in E(G)$ and each $\gamma \in (0,1),$ we have

$$\gamma \theta \oplus (1-\gamma )x\in X$$

and

$$(\gamma \theta \oplus (1-\gamma )y,\gamma \theta \oplus (1-\gamma )z)\in E(G).$$

Let $T\in \mathcal{M}$ and $\gamma \in (0,1)$. Define

$$T_{\gamma }(x):=(1-\gamma )T(x)\oplus \gamma \theta ,x\in X.$$

(12)

Clearly, $T_{\gamma }\in \mathcal{M}$ and for each $x,y\in X$ such that $(x,y)\in E(G)$, we have

$$\rho (T_{\gamma }(x),T_{\gamma }(y))\le (1-\gamma )\rho (T(x),T(y))\le (1-\gamma )\rho (x,y).$$

(13)

By (12), for each $x\in X$, we have

$$\rho (T_{\gamma }(x),T(x))\le \gamma \rho (\theta ,T(x)).$$

In view of the above inequality, the set

$$\{T_{\gamma }:T\in \mathcal{M},\gamma \in (0,1)\}$$

is an everywhere dense subset of $(\mathcal{M},d)$.

Theorem 5.

There exists a set $\mathcal{F}\subset \mathcal{M}$, which is a countable intersection of open and everywhere dense sets in $(\mathcal{M},d)$ so that for each $C\in \mathcal{F}$, there exists a unique point $x_C\in X$ such that $C(x_C)=x_C$ and $C^i(x)\to x_C$ in $(X,\rho )$ as $i\to \infty$, uniformly on bounded subsets of $(X,\rho ).$

Proof. 

Let $T\in \mathcal{M}$, $\gamma \in (0,1)$ and let $n\ge 1$ be an integer. Theorem 1 and (13) imply that there exists a unique point $x_{T,\gamma }\in X$ such that

$$T_{\gamma }(x_{T,\gamma })=x_{T,\gamma }.$$

(14)

By Theorem 4, there exist an open neighborhood $\mathcal{U}(T,\gamma ,n)$ of $T_{\gamma }$ in $\mathcal{M}$ and a natural number $p(T,\gamma ,n)$ such that the following property holds:

(a) for each $C\in \mathcal{U}(T,\gamma ,n)$, each $x\in B_{\rho }(\theta ,n)$ and each integer $k\ge p(T,\gamma ,n)$, we have

$$\rho (C^k(x),x_{T,\gamma })\le 1/n.$$

Define

$$\mathcal{F}:={\cap }_{n=1}^{\infty }\cup \{\mathcal{U}(T,\gamma ,n):T\in \mathcal{M},\gamma \in (0,1)\}.$$

(15)

Clearly, $\mathcal{F}$ is a countable intersection of open and everywhere dense subsets of $(\mathcal{M},d)$. Assume now that

$$C\in \mathcal{F},$$

(16)

$x\in X$ and that n is a natural number such that

$$B(\theta ,x)\le n.$$

(17)

By (15) and (16), there are $T\in \mathcal{M}$ and $\gamma \in (0,1)$ such that

$$C\in \mathcal{U}(T,\gamma ,n).$$

(18)

Property (a), (17) and (18) imply that for each integer $k\ge p(T,\gamma ,n)$, we have

$$\rho (C^k(x),x_{T,\gamma })\le 1/n.$$

(19)

Since n is any natural number satisfying (17), we conclude that ${\{C^i(x)\}}_{i=0}^{\infty }$ is a Cauchy sequence and there exists

$$\underset{i\to \infty }{\lim }{C}^i(x) \mathrm{i}\mathrm{n} (X,\rho ).$$

In view of (19), we have

$$\rho (\underset{i\to \infty }{\lim }{C}^i(x),x_{T,\gamma })\le 1/n.$$

(20)

Since n is any sufficiently large natural number, we infer that

$$\underset{i\to \infty }{\lim }{C}^i(x)=\underset{i\to \infty }{\lim }{C}^i(y)$$

for each $y\in X$. Next, set

$$x_C=\underset{i\to \infty }{\lim }{C}^i(x).$$

(21)

Obviously,

$$C(x_C)=x_C.$$

In view of (20) and (21), we have

$$\rho (x_C,x_{T,\gamma })\le 1/n.$$

(22)

It now follows from (17) and (22) that for each point $x\in B(\theta ,n)$ and each integer $k\ge p(T,\gamma ,n)$, we have

$$\rho (C^k(x),x_C)\le 2n^{-1}.$$

Since n is any sufficiently large natural number, this completes the proof of Theorem 5.  □