Abstract
We prove a “collage” theorem for weak contractive maps and we useit for inverse problems
Authors
Stefan M. Soltuz
Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy
Keywords
Weak contractive maps, inverse problems
Paper coordinates
Ş.M. Şoltuz, Extending the collage theorem to contractive like operators, Rev. Anal. Numer. Theor. Approx., 38 (2009) no. 2, pp. 177-181.
https://ictp.acad.ro/jnaat/journal/article/view/2009-vol38-no2-art8
About this paper
Journal
Revue d’Analyse Numerique et de Theorie de l’Approximation
Publisher Name
Romanian Academy
Print ISSN
2457-6794
Online ISSN
2501-059X
google scholar link
[1] Berinde, V.,Approximating fixed points of weak contractions using Picard iteratioon,Nonlinear Analysis Forum,9, pp. 43–53, 2004.
[2] Berinde, M.andBerinde, V.,On a general class of multi-valued weakly Picard map-pings,J. Math. Anal. Appl.,326, pp. 772–782, 2007.
[3] Kunze, H.E.andVrscay, E.R.,Solving inverse problems for ordinary differential equa-tions using the Picard contraction mapping, Inverse Problems,15, pp. 745–770, 1999.
[4] Kunze, H.E.andGomes, S.,Solving an inverse problem for Urison-type integral equa-tions using Banach’s fixed point theorem, Inverse Problems,19, pp. 411–418, 2003.
[5] Kunze, H.E., Hicken, J.E.andVrscay, E.R.,Inverse problems for ODEs using con-traction maps and suboptimality for the ‘collage method’, Inverse Problems,20, pp. 977–991, 2004
Paper (preprint) in HTML form
EXTENDING THE COLLAGE THEOREM TO CONTRACTIVE LIKE OPERATORS
Abstract
We generalize the classical "collage" theorem, due to Barnsley, to contractive like operators.
MSC 2000. 65J22, 47N40, 47H10.
Keywords. contractive like operators.
Keywords. contractive like operators.
1. INTRODUCTION
Let XX be a real Banach space, T:X rarr XT: X \rightarrow X be an operator. The following result of Barnsley, see 1, becomes "a classic".
Theorem 1. (Collage Theorem) Let x in Xx \in X be given and T:X rarr XT: X \rightarrow X a contraction with contraction factor L in(0,1)L \in(0,1), (i.e. ||Tx-Ty|| <= L||x-y||\|T x-T y\| \leq L\|x-y\|, AA x,y in X\forall x, y \in X ), and fixed point x^(**)x^{*}. Then
||x-x^(**)|| <= (1)/(1-L)||x-Tx||\left\|x-x^{*}\right\| \leq \frac{1}{1-L}\|x-T x\|
In fractal-based applications, TT produces a union of shrunken copies of xx, i.e. "a collage" of itself. The term ||x-Tx||\|x-T x\| is referred as "collage distance". Such "collages" are sufficient to be taken in finite number, in order to have a good approximation of an denoised image; fact which is very useful in Image Compression (both Analysis and Synthesis of an image). Kunze et all., see [5], 6], 7), were able to apply the Collage Theorem to inverse problems in ODE, that is to reconstruct the field of an ODE, from a given "target" (trajectory). Our aim is to generalize the above Collage result for a larger operatorial class than contractions. Recently, similar results were introduced for other operatorial classes, see [11] and [12.
The following operatorial class, satisfying (1), was introduced in [4]. Since they failed to named it, we shall do so here. It is just a convention.
Definition 2. The operator TT is contractive-like, or CLC L for short, if there exist a constant q in(0,1)q \in(0,1) and a monotone increasing and continuous function
psi:[0,oo)rarr[0,oo)\psi:[0, \infty) \rightarrow[0, \infty) with psi(0)=0\psi(0)=0 such that for each x,y in Xx, y \in X,
{:(1)||Tx-Ty|| <= q||x-y||+psi(||x-Tx||).:}\begin{equation*} \|T x-T y\| \leq q\|x-y\|+\psi(\|x-T x\|) . \tag{1} \end{equation*}
{:(1)||Tx-Ty|| <= q||x-y||+psi(||x-Tx||).:}\begin{equation*} \|T x-T y\| \leq q\|x-y\|+\psi(\|x-T x\|) . \tag{1} \end{equation*}
Let F(T)F(T) denote the fixed point set with respect to XX for the map TT. Suppose that x^(**)in F(T)x^{*} \in F(T). The following operators are called Zamfirescu operators, see [13] or [10].
Definition 3. [13] The operator T:X rarr XT: X \rightarrow X satisfies condition ZZ (or is a quasi-contraction) if and only if there exist the real numbers a,b,ca, b, c satisfying 0 < a < 1,0 < b < 1//2,0 < c < 1//20<a<1,0<b<1 / 2,0<c<1 / 2 such that for each pair x,yx, y in XX, at least one condition is true
(z_(1))||Tx-Ty|| <= a||x-y||\left(z_{1}\right)\|T x-T y\| \leq a\|x-y\|,
(z_(2))||Tx-Ty|| <= b(||x-Tx||+||y-Ty||)\left(z_{2}\right)\|T x-T y\| \leq b(\|x-T x\|+\|y-T y\|),
(z_(3))||Tx-Ty|| <= c(||x-Ty||+||y-Tx||)\left(z_{3}\right)\|T x-T y\| \leq c(\|x-T y\|+\|y-T x\|).
It has been shown in 2 (see also [3]) that conditions (z_(1))-(z_(3))\left(z_{1}\right)-\left(z_{3}\right) lead to
(z_(1))||Tx-Ty|| <= a||x-y||\left(z_{1}\right)\|T x-T y\| \leq a\|x-y\|,
(z_(2))||Tx-Ty|| <= b(||x-Tx||+||y-Ty||)\left(z_{2}\right)\|T x-T y\| \leq b(\|x-T x\|+\|y-T y\|),
(z_(3))||Tx-Ty|| <= c(||x-Ty||+||y-Tx||)\left(z_{3}\right)\|T x-T y\| \leq c(\|x-T y\|+\|y-T x\|).
It has been shown in 2 (see also [3]) that conditions (z_(1))-(z_(3))\left(z_{1}\right)-\left(z_{3}\right) lead to
{:(2)||Tx-Ty|| <= delta||x-y||+2delta||x-Tx||","AA x","y in D:}\begin{equation*}
\|T x-T y\| \leq \delta\|x-y\|+2 \delta\|x-T x\|, \forall x, y \in D \tag{2}
\end{equation*}
where
delta:=max{a,(b)/(1-b),(c)/(1-c)}.\delta:=\max \left\{a, \frac{b}{1-b}, \frac{c}{1-c}\right\} .
Set
q:=delta,psi(a):=2delta aq:=\delta, \psi(a):=2 \delta a
to obtain (1). Thus, relation (1) generalizes (2). In 4 was introduced this more general class of operators satisfying (1).
Remark 4. Set psi(t)=2t\psi(t)=2 t to see that a CL operators need not have a fixed point, as pointed in [8] or [9]. Therefore, we shall suppose implicitly throughout this paper that all CL operators involved have a fixed point.
A typical inverse problem is the following:
Problem 5. For given epsi > 0\varepsilon>0 and a "target" bar(x)\bar{x}, find T_(epsi)in CLT_{\varepsilon} \in C L such that ||( bar(x))-x_(T_(epsi))^(**)|| < epsi\left\|\bar{x}-x_{T_{\varepsilon}}^{*}\right\|<\varepsilon, where x_(T_(epsi))^(**)=T_(epsi)(x_(T_(epsi))^(**))x_{T_{\varepsilon}}^{*}=T_{\varepsilon}\left(x_{T_{\varepsilon}}^{*}\right) is the unique fixed point of the CLC L mapping T_(epsi)T_{\varepsilon}.
Problem 5. For given epsi > 0\varepsilon>0 and a "target" bar(x)\bar{x}, find T_(epsi)in CLT_{\varepsilon} \in C L such that ||( bar(x))-x_(T_(epsi))^(**)|| < epsi\left\|\bar{x}-x_{T_{\varepsilon}}^{*}\right\|<\varepsilon, where x_(T_(epsi))^(**)=T_(epsi)(x_(T_(epsi))^(**))x_{T_{\varepsilon}}^{*}=T_{\varepsilon}\left(x_{T_{\varepsilon}}^{*}\right) is the unique fixed point of the CLC L mapping T_(epsi)T_{\varepsilon}.
Randomly selecting various maps in CLC L, finding their fixed points and computing the distance from our target is an extremely tedious procedure. Consider now the following problem which we shall fit in our framework and which is very useful for practitioners, see 5 .
Problem 6. Let bar(x)in X\bar{x} \in X be a target and let delta > 0\delta>0 be given. Find T_(delta)in CLT_{\delta} \in C L, such that ||( bar(x))-T_(delta)( bar(x))|| < delta\left\|\bar{x}-T_{\delta} \bar{x}\right\|<\delta.
In other words, instead of searching for CLC L maps whose fixed points lie close to target bar(x)\bar{x}, we search for CLC L maps that send bar(x)\bar{x} close to itself.
2. MAIN RESULTS
We shall give a lower bound to approximation error in terms of the collage error.
Proposition 7. Let XX be a real Banach space and TT a CLC L map with contraction factor q in(0,1)q \in(0,1) and fixed point x^(**)in Xx^{*} \in X. Then for any x in Xx \in X,
(1)/(1+q)||x-Tx|| <= ||x^(**)-x||.\frac{1}{1+q}\|x-T x\| \leq\left\|x^{*}-x\right\| .
Proof. For any x in Xx \in X satisfying x=x^(**)x=x^{*}, the above inequality holds. If x!=x^(**),AA x in Xx \neq x^{*}, \forall x \in X, then one obtains
{:[||Tx-x|| <= ||x^(**)-x||+||x^(**)-Tx||],[=||x^(**)-x||+||Tx^(**)-Tx||],[ <= ||x^(**)-x||+q||x^(**)-x||+psi(||x^(**)-Tx^(**)||)],[ <= (1+q)||x^(**)-x||]:}\begin{aligned}
\|T x-x\| & \leq\left\|x^{*}-x\right\|+\left\|x^{*}-T x\right\| \\
& =\left\|x^{*}-x\right\|+\left\|T x^{*}-T x\right\| \\
& \leq\left\|x^{*}-x\right\|+q\left\|x^{*}-x\right\|+\psi\left(\left\|x^{*}-T x^{*}\right\|\right) \\
& \leq(1+q)\left\|x^{*}-x\right\|
\end{aligned}
From which one gets the conclusion.
Theorem 8. (Collage theorem for contractive-like maps) Let XX be a real Banach space and TT a CLC L map with contraction factor q in(0,1)q \in(0,1) and fixed point x^(**)in Xx^{*} \in X. Then for any x in Xx \in X,
Theorem 8. (Collage theorem for contractive-like maps) Let XX be a real Banach space and TT a CLC L map with contraction factor q in(0,1)q \in(0,1) and fixed point x^(**)in Xx^{*} \in X. Then for any x in Xx \in X,
||x^(**)-x|| <= (1)/(1-q)||x-Tx||\left\|x^{*}-x\right\| \leq \frac{1}{1-q}\|x-T x\|
Proof. The CLC L condition assures that the fixed point x^(**)x^{*} is unique. If x=x^(**)x=x^{*}, the above inequality holds. If x!=x^(**),AA x in Xx \neq x^{*}, \forall x \in X, then one obtains
{:[||x^(**)-x|| <= ||Tx^(**)-Tx||+||Tx-x||],[ <= q||x^(**)-x||+psi(||x^(**)-Tx^(**)||)+||Tx-x||],[=q||x^(**)-x||+||Tx-x||]:}\begin{aligned}
\left\|x^{*}-x\right\| & \leq\left\|T x^{*}-T x\right\|+\|T x-x\| \\
& \leq q\left\|x^{*}-x\right\|+\psi\left(\left\|x^{*}-T x^{*}\right\|\right)+\|T x-x\| \\
& =q\left\|x^{*}-x\right\|+\|T x-x\|
\end{aligned}
From which one gets the conclusion.
Remark 9. To summarize, we have the following bounds
Remark 9. To summarize, we have the following bounds
(1)/(1+q)||x-Tx|| <= ||x^(**)-x|| <= (1)/(1-q)||x-Tx||.\frac{1}{1+q}\|x-T x\| \leq\left\|x^{*}-x\right\| \leq \frac{1}{1-q}\|x-T x\| .
The above "Collage Theorem" allows us to reformulate the inverse Problem 5 in the particular and more convenient Problem 6.
Theorem 10. If Problem 6 has a solution, then Problem 5 has a solution too.
Proof. Let epsi > 0\varepsilon>0 and bar(x)in X\bar{x} \in X be given. For delta:=(1-q)epsi\delta:=(1-q) \varepsilon, let T_(delta)in CLT_{\delta} \in C L be such that ||( bar(x))-T_(delta)( bar(x))|| < delta\left\|\bar{x}-T_{\delta} \bar{x}\right\|<\delta. If x_(T_(delta))^(**)x_{T_{\delta}}^{*} is the unique fixed point of the CLC L mapping T_(delta)T_{\delta}, then, by Theorem 8,
||( bar(x))-x_(T_(delta))^(**)|| <= (1)/(1-q)||( bar(x))-T_(delta)( bar(x))|| <= (1)/(1-q)delta=epsi\left\|\bar{x}-x_{T_{\delta}}^{*}\right\| \leq \frac{1}{1-q}\left\|\bar{x}-T_{\delta} \bar{x}\right\| \leq \frac{1}{1-q} \delta=\varepsilon
Note that shrinking the distance between two operators, one of them from CLC L, reduces the distance between their fixed points.
Proposition 11. Let XX be a real Banach space and T_(1)in CLT_{1} \in C L with contraction factor q_(1)in(0,1)q_{1} \in(0,1) and T_(2):X rarr XT_{2}: X \rightarrow X a map such that x_(1)^(**),x_(2)^(**)in Xx_{1}^{*}, x_{2}^{*} \in X are distinct fixed points for T_(1)T_{1} and T_(2)T_{2}. Then,
||x_(1)^(**)-x_(2)^(**)|| <= (1)/(1-q_(1))s u p_(x in X)||T_(1)x-T_(2)x||\left\|x_{1}^{*}-x_{2}^{*}\right\| \leq \frac{1}{1-q_{1}} \sup _{x \in X}\left\|T_{1} x-T_{2} x\right\|
Proof. Using (1) one obtains
{:[||x_(1)^(**)-x_(2)^(**)||=||T_(1)x_(1)^(**)-T_(2)x_(2)^(**)|| <= ||T_(1)x_(1)^(**)-T_(1)x_(2)^(**)||+||T_(1)x_(2)^(**)-T_(2)x_(2)^(**)||],[ <= q_(1)||x_(1)^(**)-x_(2)^(**)||+psi(||x_(1)^(**)-T_(1)x_(1)^(**)||)+s u p_(x in X)||T_(1)x-T_(2)x||","]:}\begin{aligned}
\left\|x_{1}^{*}-x_{2}^{*}\right\| & =\left\|T_{1} x_{1}^{*}-T_{2} x_{2}^{*}\right\| \leq\left\|T_{1} x_{1}^{*}-T_{1} x_{2}^{*}\right\|+\left\|T_{1} x_{2}^{*}-T_{2} x_{2}^{*}\right\| \\
& \leq q_{1}\left\|x_{1}^{*}-x_{2}^{*}\right\|+\psi\left(\left\|x_{1}^{*}-T_{1} x_{1}^{*}\right\|\right)+\sup _{x \in X}\left\|T_{1} x-T_{2} x\right\|,
\end{aligned}
from which we get the conclusion.
Theorem 12. Let XX be a real Banach space, T:X rarr X, bar(x)=T bar(x)T: X \rightarrow X, \bar{x}=T \bar{x} and suppose there exists T_(1)in CLT_{1} \in C L with contraction factor qq, such that
Theorem 12. Let XX be a real Banach space, T:X rarr X, bar(x)=T bar(x)T: X \rightarrow X, \bar{x}=T \bar{x} and suppose there exists T_(1)in CLT_{1} \in C L with contraction factor qq, such that
s u p_(x in X)||T_(1)x-Tx|| <= epsi\sup _{x \in X}\left\|T_{1} x-T x\right\| \leq \varepsilon
Then
||( bar(x))-T_(1)( bar(x))|| <= (1+q)/(1-q)epsi\left\|\bar{x}-T_{1} \bar{x}\right\| \leq \frac{1+q}{1-q} \varepsilon
Proof. Let x^(**)=T_(1)x^(**)x^{*}=T_{1} x^{*}, and by use of Proposition 11 we obtain
||( bar(x))-x^(**)|| <= (1)/(1-q)(s u p_(x in X)||T_(1)x-Tx||)\left\|\bar{x}-x^{*}\right\| \leq \frac{1}{1-q}\left(\sup _{x \in X}\left\|T_{1} x-T x\right\|\right)
Thus,
{:[||( bar(x))-T_(1)( bar(x))|| <= ||( bar(x))-x^(**)||+||x^(**)-T_(1)( bar(x))||],[ <= ||( bar(x))-x^(**)||+||T_(1)x^(**)-T_(1)( bar(x))||],[ <= ||( bar(x))-x^(**)||+q||( bar(x))-x^(**)||+psi(||x^(**)-T_(1)x^(**)||)],[=(1+q)||( bar(x))-x^(**)||],[ <= (1+q)/(1-q)(s u p_(x in X)||T_(1)x-Tx||) <= (1+q)/(1-q)epsi.]:}\begin{aligned}
\left\|\bar{x}-T_{1} \bar{x}\right\| & \leq\left\|\bar{x}-x^{*}\right\|+\left\|x^{*}-T_{1} \bar{x}\right\| \\
& \leq\left\|\bar{x}-x^{*}\right\|+\left\|T_{1} x^{*}-T_{1} \bar{x}\right\| \\
& \leq\left\|\bar{x}-x^{*}\right\|+q\left\|\bar{x}-x^{*}\right\|+\psi\left(\left\|x^{*}-T_{1} x^{*}\right\|\right) \\
& =(1+q)\left\|\bar{x}-x^{*}\right\| \\
& \leq \frac{1+q}{1-q}\left(\sup _{x \in X}\left\|T_{1} x-T x\right\|\right) \leq \frac{1+q}{1-q} \varepsilon .
\end{aligned}
REFERENCES
[1] Barnsley, M. F., Fractals everywhere, New York: Academic Press, 1988.
[2] Berinde, V., On the convergence of the Ishikawa iteration in the class of quasi contractive operators, Acta Math. Univ. Comenianae, Vol. LXXIII, no. 1, pp. 119-126, 2004.
[3] Berinde, V., Iterative approximation of fixed points, Springer-Verlag Berlin Heidelberg, 2007.
[4] Imoru C.O. and Olatiwo, M.O., On the stability of Picard and Mann iteration processes, Carpathian J. Math., 19, pp. 155-160, 2003.
[5] Kunze H.E. and Vrscay, E.R. Solving inverse problems for ordinary differential equations using the Picard contraction mapping, Inverse Problems, 15, pp. 745-770, 1999.
[6] Kunze, H.E. and Gomes, S., Solving an inverse problem for Urison-type integral equations using Banach's fixed point theorem, Inverse Problems, 19, pp. 411-418, 2003.
[7] Kunze, H.E., Hicken, J.E and Vrscay, E.R., Inverse problems for ODEs using contraction maps and suboptimality for the 'collage method', Inverse Problems, 20, pp. 977-991, 2004.
[8] Osilike, M.O., Stability results for fixed point iteration procedures, J. Nigerian Math. Soc., 14/15, pp. 17-29, 1995/96.
[9] Osilike, M.O., Stability of the Ishikawa iteration method for quasi-contractive maps, Indian J. Pure Appl. Math., 28, no. 9, pp. 1251-1265, 1997.
[10] Rhoades, B.E., Fixed point iterations using infinite matrices, Trans. Amer. Math. Soc., 196, pp. 161-176, 1974.
[11] Şoltuz, Ş. M., Solving inverse problems via hemicontractive maps, Nonlinear Analysis, 71, pp. 2387-2390, 2009.
[12] Şoltuz, S. M., Solving inverse problems via weak-contractive maps, Rev. Anal. Numer. Theor. Approx., 37, No. 2, pp. 217-220, 2008. 뜸
[13] Zamfirescu, T., Fix Point Theorems in metric spaces, Arch. Math., 23, pp. 292-298, 1972.
[2] Berinde, V., On the convergence of the Ishikawa iteration in the class of quasi contractive operators, Acta Math. Univ. Comenianae, Vol. LXXIII, no. 1, pp. 119-126, 2004.
[3] Berinde, V., Iterative approximation of fixed points, Springer-Verlag Berlin Heidelberg, 2007.
[4] Imoru C.O. and Olatiwo, M.O., On the stability of Picard and Mann iteration processes, Carpathian J. Math., 19, pp. 155-160, 2003.
[5] Kunze H.E. and Vrscay, E.R. Solving inverse problems for ordinary differential equations using the Picard contraction mapping, Inverse Problems, 15, pp. 745-770, 1999.
[6] Kunze, H.E. and Gomes, S., Solving an inverse problem for Urison-type integral equations using Banach's fixed point theorem, Inverse Problems, 19, pp. 411-418, 2003.
[7] Kunze, H.E., Hicken, J.E and Vrscay, E.R., Inverse problems for ODEs using contraction maps and suboptimality for the 'collage method', Inverse Problems, 20, pp. 977-991, 2004.
[8] Osilike, M.O., Stability results for fixed point iteration procedures, J. Nigerian Math. Soc., 14/15, pp. 17-29, 1995/96.
[9] Osilike, M.O., Stability of the Ishikawa iteration method for quasi-contractive maps, Indian J. Pure Appl. Math., 28, no. 9, pp. 1251-1265, 1997.
[10] Rhoades, B.E., Fixed point iterations using infinite matrices, Trans. Amer. Math. Soc., 196, pp. 161-176, 1974.
[11] Şoltuz, Ş. M., Solving inverse problems via hemicontractive maps, Nonlinear Analysis, 71, pp. 2387-2390, 2009.
[12] Şoltuz, S. M., Solving inverse problems via weak-contractive maps, Rev. Anal. Numer. Theor. Approx., 37, No. 2, pp. 217-220, 2008. 뜸
[13] Zamfirescu, T., Fix Point Theorems in metric spaces, Arch. Math., 23, pp. 292-298, 1972.
Received by the editors: September 17, 2008.
- "Tiberiu Popoviciu" Institute of Numerical Analysis, Cluj-Napoca, Romania, P.O. Box 68-1, e-mail: smsoltuz@gmail.com.