Iterative Approximation of Fixed Points of Almost Contractions PDF

Preview

Summary

Ninth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing Iterative approximation of fixed points of almost contractions Vasile BERINDE Mădălina PĂCURAR Department of Mathematics Department of Statistics, Forecast and Computer Science and Mathematics Faculty of Eco...

Description

Ninth International Symposium on Symbolic and Numeric Algorithms for Scientific Computing

Iterative approximation of fixed points of almost contractions Vasile BERINDE Department of Mathematics and Computer Science North University of Baia Mare Victoriei 76, 430122 Baia Mare ROMANIA [email protected]

˘ M˘ad˘alina PACURAR Department of Statistics, Forecast and Mathematics Faculty of Economics ”Babes-Bolyai” University of Cluj-Napoca 58-60 T. Mihali St., 400591 Cluj-Napoca ROMANIA madalina [email protected]

Abstract

of T . We denote by F ix (T ) the set of all fixed points of T, i.e., F ix (T ) = {x ∈ X : x ∈ T (x)}.

In this paper we present a very general class of weakly Picard mappings. The fixed point theorems thus obtained are generalizations of the well-known contraction mapping principle for single-valued mappings and of several of its subsequent generalizations, as well as of the well-known Nadler’s fixed point theorem for multi-valued mappings and of many of its recent and very recent extensions. The fixed points are approximated by means of Picard iteration in both single and multi-valued case.

The study of fixed point theorems for multi-valued mappings has been initiated by Markin [14] and Nadler [17]. The following result, commonly referred as Nadler’s fixed point theorem, extends the well known contraction mapping principle from single valued maps to set-valued contractive maps (we shall denote T (x) by T x in the sequel). Theorem 1. (Nadler, [17]) Let (X, d) be a complete metric space and T : X → CB(X) a set-valued α-contraction, i.e., a mapping for which there exists a constant α ∈ (0, 1) such that

1. Introduction

H(T x, T y) ≤ α d(x, y), for all x, y ∈ X.

Let (X, d) be a metric space and let P(X) (C(X), CB(X) and K(X)) denote the family of all nonempty subsets of X (nonempty closed, nonempty closed and bounded, nonempty compact, respectively). For A, B ⊂ X and a ∈ X, we consider, the distance between a and B:

Then T has a fixed point. Since the pioneering works of Markin [14] and Nadler [17], an extensive literature has been developed, consisting in many theorems which deal with fixed point theorems for multi-valued mappings, see [19], [20], [11], [12], [16], [10], [13], [2] and references cited there, and especially the monographs Rus [22] and [25], for a good survey and several still open problems. Some of these theorems require the range of each point to be compact, others to be bounded (and / or closed). In some cases the contractive definitions are expressed in terms of diameters of sets, in others the contractive definitions involve the Haussdorff-Pompeiu metric, as is the case of some of the theorems stated in this section. Among the results developed in relation to Nadler’s fixed point theorem, we mention the following ones. In [19], Reich established the following fixed point theorem for the case of multi-valued mappings with compact range.

d(a, B) = inf{d(a, b) : b ∈ B} , the diameter of A and B: δ(A, B) = sup{d(a, b) : a ∈ A, b ∈ B} , and H(A, B) = max{sup{d(a, B) : a ∈ A}, sup{d(b, A) : b ∈ B}}, the Hausdorff-Pompeiu metric on CB(X) induced by d. It is known that CB(X) is a metric space equipped with the Hausdorff-Pompeiu distance function H. It is also known, see for example Lemma 8.1.4 in Rus [24], that if (X, d) is a complete metric space then (CB(X), H) is a complete metric space, too. Let T : X → P(X) be a multi-valued mapping. An element x ∈ X such that x ∈ T (x) is called a fixed point

0-7695-3078-8/08 $25.00 © 2008 IEEE DOI 10.1109/SYNASC.2007.49

(1)

Theorem 2. (Reich, [19]) Let (X, d) be a complete metric space and let T : X → K(X). Assume that there exists

387

a map ϕ : (0, ∞) → [0, 1) such that for each t ∈ (0, ∞), lim sup ϕ(r) < 1 and

(i) the map f : X → R, f (x) = d(x, T x), x ∈ X, is lower semi-continuous; (ii) there exists b ∈ (0, 1) and ϕ : (0, ∞) → [0, 1) such that for all t ∈ (0, ∞), lim sup ϕ(r) < 1 and for all x ∈

r→t+

H(T x, T y) ≤ ϕ(d(x, y))d(x, y), ∀x, y ∈ X, x 6= y. (2)

X, ∃y ∈ Ibx satisfying

Then T has a fixed point. As an affirmative answer to an open problem posed by Reich in [20] which asks wether the above theorem is also true for mappings T : X → CB(X), Mizoguchi and Takahashi [16] proved the following generalization of Nadler’s fixed point theorem (which is obtained from Theorem 3 by taking ϕ(t) = α, ∀t ∈ [0, ∞), α ∈ (0, 1)).

d(y, T y) ≤ ϕ(d(x, y))d(x, y).

(4)

Then T has a fixed point. On the other hand, the authors in [2] obtained a generalization of Nadler’s fixed point theorem in another direction than the ones of Mizoguchi and Takahashi [16], Feng and Liu [10] or Klim and Wardowski [13], which was very recently extended in [18]. In the present paper, using the concept of multi-valued almost contraction introduced and studied in [2] and [18], we shall prove some convergence theorems regarding the approximation of fixed points of a more general class of almost contractions by means of Picard iteration.

Theorem 3. (Mizoguchi and Takahashi, [16]) Let (X, d) be a complete metric space and let T : X → CB(X). Assume that there exists a map ϕ : (0, ∞) → [0, 1) such that for each t ∈ (0, ∞), lim sup ϕ(r) < 1 and r→t+

H(T x, T y) ≤ ϕ(d(x, y))d(x, y), ∀x, y ∈ X, x 6= y. Then T has a fixed point. It was noticed in [10] that if T satisfies the contraction condition (1) in Nadler’s fixed point theorem, then: (p1) The function T : X → R, f (x) = d(x, T x), x ∈ X, is lower semi-continuous; (p2) For any x ∈ X and y ∈ T x, d(y, T y) ≤ H(T x, T y).

r→t+

2 Single valued almost contractions Following [18], a single valued mapping T : X → X is called an almost contraction or (δ, L)-almost contraction iff there exist two constants, δ ∈ (0, 1) and L ≥ 0, such that

(3)

d(T x, T y) ≤ δ · d(x, y) + Ld(y, T x), ∀x, y ∈ X .

The properties (p1) and (p2) enabled Feng and Liu [10] to obtain an extension of Nadler’s fixed point theorem, for mappings T : X → C(X), in another direction than the ones obtained by Reich or Mizoguchi and Takahashi. To state their result, let us denote, for b ∈ (0, 1) and x ∈ X,

(5)

For convenience and in view of extending them further to the multi-valued case, we state Theorems 1 and 2 of [6] as the next theorem (note that in [6] and in some subsequent papers an almost contraction was named weak contraction).

Ibx = {y ∈ T x : bd(x, y) ≤ d(x, T x)} . Theorem 6. (Berinde, [6]) Let (X, d) be a complete metric space and T : X → X a (δ, L)-almost contraction. Then 1) F ix (T ) = {x ∈ X : T x = x} = 6 ∅; 2) For any x0 ∈ X, the Picard iteration {xn }∞ n=0 given by xn+1 = T xn , n = 0, 1, 2, ..., converges to some x∗ ∈ F ix (T ); 3) The following estimates

Theorem 4. (Feng and Liu, [10]) Let (X, d) be a complete metric space and let T : X → C(X). Assume that the following conditions hold: (i) the map f : X → R, f (x) = d(x, T x), x ∈ X, is lower semi-continuous; (ii) There exist b, c ∈ (0, 1), c < b, such that for each x ∈ X, ∃y ∈ Ibx satisfying d(y, T y) ≤ cd(x, y). Then T has a fixed point. Very recently, Klim and Wardowski [13] extended Theorems 1-4 for both mappings T : X → C(X) (Thorem 2.1) and T : X → K(X) (Theorem 2.2) by considering in the left hand side of the contraction condition the quantity d(y, T y) instead of H(T x, T y), thus extending Feng and Liu’s Theorem 4, too. We state here the first of these two results.

d(xn , x∗ ) ≤

δn d(x0 , x1 ) , n = 0, 1, 2, . . . 1−δ

d(xn , x∗ ) ≤

δ d(xn−1 , xn ) , n = 1, 2, . . . 1−δ

hold, where δ is the constant appearing in (5). 4) Under the additional condition that there exist θ ∈ (0, 1) and some L1 ≥ 0 such that

Theorem 5. (Klim and Wardowski, [13]) Let (X, d) be a complete metric space and let T : X → C(X). Assume that the following conditions hold:

d(T x, T y) ≤ θ · d(x, y) + L1 · d(x, T x), ∀x, y ∈ X , (6)

388

Using the definition of d(a, B) and H(A, B), it follows that, for any ǫ > 0, there exists b ∈ B such that

the fixed point x∗ is unique and the Picard iteration converges at the rate d(xn , x∗ ) ≤ θ d(xn−1 , x∗ ) ,

n ∈ N.

d(a, b) ≤ d(a, B) + ǫ ≤ H(A, B) + ǫ.

As shown in [6], [5] and [4], a lot of well known contractive conditions from literature do imply the almost (weak) contraction condition (5) and also the uniqueness contraction condition (6). Both conditions are indeed very general, because they do not ask δ + L and, respectively, θ + L1 , be less than 1, as happens in almost all fixed point theorems based on contractive conditions that involve one or more of the displacements d(x, y), d(x, T x), d(y, T y), d(x, T y), d(y, T x). Therefore, Theorems 2 includes as particular cases several important fixed point theorems in literature, amongst them we mention: the contraction mapping principle, Kannan fixed point theorem, Zamfirescu’s fixed point theorem and many other fixed point theorems, see [3] for more details and references. Moreover, Theorem 2, items 1)-3), which ensure the existence of fixed points for almost contractions, and item 4), which guarantees the existence and uniqueness of the fixed point for some special almost contractions, also provide a method for approximating these fixed points by means of the Picard iteration. For this method, both a priori and a posteriori error estimates are available, and moreover, these estimates have exactly the same form as in the particular case of the contraction mapping principle. This suggested us to call them almost contraction instead of weak cotraction, because we obtain all conclusions of the contraction mapping principle, except for the uniqueness of the fixed point. Very recently, Babu, Sandhya and Kamesvari [1] proposed a more general contractive condition in the single valued case, by replacing (5) with a more general one. A corresponding result in the multi-valued case has been announced in the paper [18]. The main aim of this paper is to prove in all details these results and some other related results.

(9)

Now, by inserting (8) in (9), we get (7). The following notion, which is fundamental in the approximation of fixed points of both single and multi-valued mappings, was introduced in Rus [23], see also Rus et al. [26] and references therein. Definition 1. Let (X, d) be a metric space and T : X → P(X) be a multivalued operator. T is said to be a multivalued weakly Picard (briefly MWP) operator iff for each x ∈ X, there exists a sequence {xn }∞ n=0 such that (i) x0 = x; (ii) xn+1 ∈ T (xn ) for all n = 0, 1, 2, ...; (iii) the sequence {xn }∞ n=0 converges and its limit is a fixed point of T . Remark. A sequence {xn }∞ n=0 satisfying conditions (i) and (ii) in Definition 1 is usually called a sequence of successive approximations of T starting from x, or a Picard iteration associated to T or a (Picard) orbit of T at the initial point x. Some of the multi-valued mappings appearing in Theorems 1-6 are WPM, as shown in [2]. The next theorem basically shows that any multivalued almost-contraction is a MWP operator, too. Theorem 7. Let (X, d) be a complete metric space and T : X → CB(X) a multivalued (θ, L)-weak contraction, i.e., a mapping satisfying H(T x, T y) ≤ θ · d(x, y) + L min{d(x, T x), d(y, T y), d(x, T y), d(y, T x)}, ∀x, y ∈ X.

(10)

Then 1) F ix (T ) 6= ∅; 2) For any x0 ∈ X, there exists an orbit {xn }∞ n=0 of T at the point x0 that converges to a fixed point u of T , for which the following estimates hold

3 Multi-valued almost contractions

d(xn , u) ≤

hn d(x0 , x1 ), n = 0, 1, 2, ... 1−h

(11)

To prove the main results in this paper, we shall need the following lemma which can be found, e.g. in [7] or [25]. Lemma 1. Let (X, d) be a metric space. Let A, B ⊂ X and q > 1. Then, for every a ∈ A, there exists b ∈ B such that d(a, b) ≤ q H(A, B). (7)

d(xn , u) ≤

h d(xn−1 , xn ), n = 1, 2, ..., 1−h

(12)

for a certain constant h < 1.

Proof. If H(A, B) = 0, then a ∈ B and (7) holds for b = a. If H(A, B) > 0, then let us denote

Proof. Let q > 1. Let x0 ∈ X and x1 ∈ T x0 . If H(T x0 , T x1 ) = 0 then T x0 = T x1 , i.e., x1 ∈ T x1 , which actually means that F ix (T ) 6= ∅. Let H(T x0 , T x1 ) 6= 0. By Lemma 1, there exists x2 ∈ T x1 such that

ǫ = (q − 1) H(A, B) > 0.

d(x1 , x2 ) ≤ qH(T x0 , T x1 ).

(8)

389

4 Generalized multi-valued almost contractions

By (10) we have d(x1 , x2 ) ≤ q[θd(x0 , x1 ) + L · 0] = qθd(x0 , x1 ), because min{d(x0 , T x0 ), d(x1 , T x1 ), d(x0 , T x1 , d(x1 , T x0 ))} = = d(x1 , T x0 ) = 0. We take q > 1 such that

The results in the previous section could be further extended by replacing the term θd(x, y) in (10) by the expression α(d (x, y))d (x, y), where α : [0, ∞) → [0, 1) is a function satisfying certain conditions, like in [9], [11], [12]. Theorem 8. Let (X, d) be a complete metric space and T : X → CB(X) a generalized multivalued (α, L)-almost contraction, i.e., a mapping for which there exists a function α : [0, ∞) → [0, 1) satisfying lim supr→t+ α(r) < 1, for every t ∈ [0, ∞), such that

h = qθ < 1 and hence d(x1 , x2 ) < hd(x0 , x1 ). If H(T x1 , T x2 ) = 0, then T x1 = T x2 , i.e., x2 ∈ T x2 . Let H(T x1 , T x2 ) 6= 0. Again by Lemma 1, there exists x3 ∈ T x2 such that

H(T x, T y) ≤ α(d(x, y))d(x, y) + L min{d(x, T x),

d(x2 , x3 ) ≤ h d(x1 , x2 ).

d(y, T y), d(x, T y), d(y, T x)}, ∀x, y ∈ X.

In this manner we obtain an orbit {xn }∞ n=0 at x0 for T satisfying d(xn , xn+1 ) ≤ h d(xn−1 , xn ), n = 1, 2, ...

Then T has at least one fixed point. Proof. The proof could be easily adapted after that of Theorem 3.1 in [2]. We do not present it here. Remark. By Theorem 8 we can obtain as particular cases several fixed point theorems in literature. One example is given by the next corollary. Corollary 1. Let (X, d) be a complete metric space and T : X → CB(X) be a generalized multivalued (α, L)almost contraction, with α : [0, ∞) → [0, 1) a monotone increasing function satisfying 0 ≤ α(t) < 1, for each t ∈ [0, ∞). If (20) is satisfied, then T has at least one fixed point. Corollary 1 generalizes Theorem 1.2 in [9] by extending the range of T from the family of all bounded proximinal subsets of X to CB(X) and also Corollary 2.2 in [9] from the contractive condition

(13)

By (13) we inductively obtain d(xn , xn+1 ) ≤ hn d(x0 , x1 )

(14)

and, respectively, d(xn+k , xn+k+1 ) ≤ hk+1 d(xn−1 , xn ), k ∈ N, n ≥ 1. (15) By (14) we then obtain d(xn , xn+p ) ≤

hn (1 − hp ) d(x0 , x1 ), n, p ∈ N 1−h

(16)

which, in view of 0 < h < 1, shows that {xn }∞ n=0 is a Cauchy sequence. Since (X, d) is complete, it follows that {xn }∞ n=0 is convergent. Let u = lim xn . n→∞

(20)

(17) H(T x, T y) ≤ α(d(x, y))d(x, y), ∀ x, y ∈ X

Then to the more general contractive condition (20). It also significantly generalizes Corollary 1 from [2]. We may further unify the fixed point theorems for multivalued mappings in Sections 1-2, by combining the contraction condition (11), on the one hand, with (4), on the other hand, in view of the inequality (3). In this way we shall obtain general fixed point theorems that extend, improve and unify a multitude of corresponding results in literature [18], [2], [3]-[6], [9], [10], [11], [12], [13], [16], [1], [19] and many others, for both single and multi-valued maps. To this end we need the following lemma.

d(u, T u) ≤ d(u, xn+1 ) + d(xn+1 , T u) ≤ ≤ d(u, xn+1 ) + H(T xn , T u) which by (10) yields d(u, T u) ≤ d(u, xn+1 ) +θd(xn , u) +L min {d(xn , T xn ), d(u, T u), d(xn , T u), d(u, T xn )} .

(18)

Letting n → ∞ in (18) and using the fact that xn+1 ∈ T xn implies by (17), d(u, T xn ) → 0, as n → ∞, we get d(u, T u) = 0.

Lemma 1. Let (X, d) be a metric space and let T : X → C(X) be a mapping. Then, for every x ∈ X with d(x, T x) > 0 and any b ∈ (0, 1), there exists y ∈ T x, y 6= x, such that b d(x, y) ≤ d(x, T x).

Since T u is closed, this implies u ∈ T u. To obtain (11) we let p → ∞ in (16). By (15) we get similarly to (16) h(1 − hp ) d(xn−1 , xn ), p ∈ N, n ≥ 1 1−h (19) and letting p → ∞ in (19) we obtain (12). d(xn , xn+p ) ≤

Proof. Since T x is nonempty and closed, d(x, T x) > 0

390

implies that there exists y ∈ T x, y 6= x. Using the definition of d(x, T x), it follows that, for any ǫ > 0, there exists y ∈ T x such that

and such that d(x3 , T x3 ) ≤ ϕ(d(x2 , x3 ))d(x2 , x3 ), ϕ(d(x2 , x3 )) < b. (27) By (26) and (27) we have

d(x, y) ≤ d(x, T x) + ǫ.
Now, by taking ǫ = 1b − 1 d(x, T x) > 0, we get the desired inequality.

d(x2 , T x2 ) − d(x3 , T x3 ) ≥ bd(x2 , x3 ) − ϕ(d(x2 , x3 ))· ·d(x2 , x3 ) = [b − ϕ(d(x2 , x3 ))]d(x2 , x3 ) > 0.

Theorem 9. Let (X, d) be a complete metric space and let T : X → C(X). Assume that the following conditions hold: (i) the map f : X → R, f (x) = d(x, T x), x ∈ X, is lower semi-continuous; (ii) there exist L ≥ 0, b ∈ (0, 1) and ϕ : (0, ∞) → [0, b) such that for all t ∈ (0, ∞), lim sup ϕ(r) < b

By combining (27) and (26), we obtain d(x2 , x3 ) ≤

·d(x1 , x2 ) < d(x1 , x2 ). By induction, assuming xn , n > 1, being obtained in the previous way, there exists xn+1 ∈ T xn , xn 6= xn+1 , such that b d(xn , xn+1 ) ≤ d(xn , T xn ) (28)

(21)

r→t+

and for all x ∈ X, ∃y ∈ Ibx satisfying

and also satisfying

d(y, T y) ≤ α(d(x, y))d(x, y) + L min{d(x, T x), d(y, T y), d(x, T y), d(y, T x)}.

d(xn+1 , T xn+1 ) ≤ ϕ(d(xn , xn+1 ))d(xn , xn+1 ), (22)

ϕ(d(xn , xn+1 )) < b.

Then T has a fixed point.

d(xn , T xn ) − d(xn+1 , T xn+1 ) ≥ bd(xn , xn+1 )− −ϕ(d(xn , xn+1 )) · d(xn , xn+1 ) = = [b − ϕ(d(xn , xn+1 ))]d(xn , xn+1 ) > 0

(30)

d(xn , xn+1 ) < d(xn , xn−1 ).

(31)

and

(23)

We can assume in the following that we have y ∈ Ibx , y 6= x, otherwise y = x ∈ T x will be a fixed point of T and the proof is done. Let x1 ∈ X be arbitrary but fixed with d(x1 , T x1 ) > 0. By (23) and assumption (ii), there exists x2 ∈ T x1 , x2 6= x1 , satisfying the inequality b d(x1 , x2 ) ≤ d(x1 , T x1 )

(29)

In a similar way, by (29) and (28), we get

Proof. If there exists x ∈ X such that d(x, T x) = 0, then x ∈ T x, i.e., x is a fixed point of T . Since the range of T is closed, for each b ∈ (0, 1) and any x ∈ X, with d(x, T x) > 0, it follows by Lemma 2 that there exists y ∈ T x such that y ∈ Ibx , that is, b d(x, y) ≤ d(x, T x).

1 1 d(x2 , T x2 ) ≤ ϕ(d(x1 , x2 ))]· b b

Now, by (30) and (31), it follows that {d(xn , T xn )} and d(xn , xn+1 ) are decreasing sequences of positive numbers and hence are both convergent. By assumption (20), it follows that there exists s ∈ [0, b) such that lim sup ϕ(d(xn , xn+1 )) = s. n→∞

(24)

Then, for any b0 ∈ (q, b), there exists a rank n0 ∈ N such that ϕ(d(xn , xn+1 )) < b0 , ∀n > n0 . (32)

and, by (21), d(x2 , T x2 ) ≤ ϕ(d(x1 , x2 ))d(x1 , x2 ), ϕ(d(x1 , x2 )) < b, (25) since d(x2 , T x1 ) = 0. By (24) and (25) we get

By using (30) and denoting a = b − b0 , it follows that d(xn , T xn ) − d(xn+1 , T xn+1 ) ≥ ad(xn , xn+1 ), ∀n > n0 . (33) Using now (28), (29) and (32), for any n > n0 , we have

d(x1 , T x1 ) − d(x2 , T x2 ) ≥ bd(x1 , x2 ) − ϕ(d(x1 , x2 ))· ·d(x1 , x2 ) = [b − ϕ(d(x1 , x2 ))]d(x1 , x2 ) > 0.

d(xn+1 , T xn+1 ) ≤ ϕ(d(xn , xn+1 )) ≤

...