Abstract
We prove a “collage” theorem for hemicontractive maps and we use it for inverse problems. A numerical example is given.
Authors
S.M. Soltuz
(Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy)
Keywords
Hemicontractive maps; Inverse problems.
References
See the expanding block below.
Paper coordinates
Ş.M. Şoltuz, Solving inverse problems via hemicontractive maps, Nonlinear Analysis: Theory, Methods & Applications, 71 (2009), 2387-2390.
doi: 10.1016/j.na.2009.01.071
About this paper
Publisher Name
Elsevier
Print ISSN
0362-546X
Online ISSN
Google Scholar Profile
google scholar
soon
Paper (preprint) in HTML form
Solving inverse problems via hemicontractive maps
MSC:
65J22
47N40
Keywords:
Hemicontractive maps
Inverse problems
65J22
47N40
Keywords:
Hemicontractive maps
Inverse problems
Abstract
We prove a "collage" theorem for hemicontractive maps and we use it for inverse problems. A numerical example is given. © 2009 Elsevier Ltd. All rights reserved.
1. Introduction
Let XX be a real Banach space, T:X rarr XT: X \rightarrow X be an operator. The map J:X rarr2^(X^(**))J: X \rightarrow 2^{X^{*}} given by Jx:={f inX^(**):(:x,f:)=:}{:||x||^(2),||f||=||x||},AA x in XJ x:=\left\{f \in X^{*}:\langle x, f\rangle=\right. \left.\|x\|^{2},\|f\|=\|x\|\right\}, \forall x \in X, is called the normalized duality mapping. It is easy to see that
{:(1)(:y","j(x):) <= ||x||||y||","quad AA x","y in X","AA j(x)in J(x).:}\begin{equation*}
\langle y, j(x)\rangle \leq\|x\|\|y\|, \quad \forall x, y \in X, \forall j(x) \in J(x) . \tag{1}
\end{equation*}
Definition 1. A map T:X rarr XT: X \rightarrow X is called hemicontractive if there exist k in(0,1)k \in(0,1) and q in Xq \in X with q=Tqq=T q such that for every x in Xx \in X there exists j(x-q)in J(x-q)j(x-q) \in J(x-q) satisfying
{:(2)(:Tx-Tq","j(x-q):) <= k||x-q||^(2)","quad AA x in X.:}\begin{equation*}
\langle T x-T q, j(x-q)\rangle \leq k\|x-q\|^{2}, \quad \forall x \in X . \tag{2}
\end{equation*}
Remark 2. The fixed point qq in Definition 1 is uniquely determined and, sometimes, will be denoted by x_(T)^(**)x_{T}^{*}.
Indeed, if p=Tpp=T p is another fixed point of the hemicontractive mapping TT, then
Indeed, if p=Tpp=T p is another fixed point of the hemicontractive mapping TT, then
{:[||p-q||^(2)=(:p-q","j(p-q):)],[=(:Tp-Tq","j(p-q):) <= k||p-q||^(2)","]:}\begin{aligned}
\|p-q\|^{2} & =\langle p-q, j(p-q)\rangle \\
& =\langle T p-T q, j(p-q)\rangle \leq k\|p-q\|^{2},
\end{aligned}
implying ||p-q||=0\|p-q\|=0, i.e., p=qp=q.
It is well known that TT is a contraction if there exists k in(0,1)k \in(0,1) such that ||Tx-Ty|| <= k||x-y||,AA x,y in X\|T x-T y\| \leq k\|x-y\|, \forall x, y \in X.
Remark 3. The class of contractions is a subclass of hemicontractions.
Let TT be a kk-contraction of the Banach space XX. Then TT has a unique fixed point qq and
It is well known that TT is a contraction if there exists k in(0,1)k \in(0,1) such that ||Tx-Ty|| <= k||x-y||,AA x,y in X\|T x-T y\| \leq k\|x-y\|, \forall x, y \in X.
Remark 3. The class of contractions is a subclass of hemicontractions.
Let TT be a kk-contraction of the Banach space XX. Then TT has a unique fixed point qq and
{:[(:Tx-Tq","j(x-q):) <= ||Tx-Tq||||x-q||],[ <= k||x-q||^(2)","]:}\begin{aligned}
\langle T x-T q, j(x-q)\rangle & \leq\|T x-T q\|\|x-q\| \\
& \leq k\|x-q\|^{2},
\end{aligned}
for j(x-q)in J(x-q)j(x-q) \in J(x-q).
Remark 4. The above inclusion is proper.
Indeed, note that T(x,y)=(-y,x)T(x, y)=(-y, x) is not a contraction while it is hemicontractive with q=(0,0)q=(0,0) and k=0.5k=0.5,
Indeed, note that T(x,y)=(-y,x)T(x, y)=(-y, x) is not a contraction while it is hemicontractive with q=(0,0)q=(0,0) and k=0.5k=0.5,
{:[(:T(x","y)","(x","y):)=(:(-y","x)","(x","y):)=0],[ <= (1//2)(x^(2)+y^(2))=0.5||(x","y)||^(2)]:}\begin{aligned}
\langle T(x, y),(x, y)\rangle & =\langle(-y, x),(x, y)\rangle=0 \\
& \leq(1 / 2)\left(x^{2}+y^{2}\right)=0.5\|(x, y)\|^{2}
\end{aligned}
Recently, Kunze et al. (see [1-3]) have considered a class of inverse problems for ordinary differential equations and provided a mathematical basis for solving them within the framework of Banach spaces and contractions. We shall consider the same framework of Banach spaces and the larger class of hemicontractive maps.
Notation 5. Denote by HemiLip :={T,T:X rarr X,T:=\{T, T: X \rightarrow X, T a hemicontractive map with constant k in(0,1)k \in(0,1), Lipschitzian with constant L >= 1L \geq 1 and T(X)T(X) bounded }\}.
A typical inverse problem is the following:
Problem 6. For given epsi > 0\varepsilon>0 and a "target" bar(x)\bar{x}, find T_(epsi)inT_{\varepsilon} \in HemiLip 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 hemicontractive mapping T_(epsi)T_{\varepsilon}.
Problem 6. For given epsi > 0\varepsilon>0 and a "target" bar(x)\bar{x}, find T_(epsi)inT_{\varepsilon} \in HemiLip 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 hemicontractive mapping T_(epsi)T_{\varepsilon}.
According to [1], randomly selecting various maps in HemiLip, 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.
Problem 7. Let bar(x)in X\bar{x} \in X be a target and let delta > 0\delta>0 be given. Find T_(delta)inT_{\delta} \in HemiLip 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 hemicontractive maps whose fixed points lie close to target bar(x)\bar{x}, we search for hemicontractive maps that send bar(x)\bar{x} close to itself.
In other words, instead of searching for hemicontractive maps whose fixed points lie close to target bar(x)\bar{x}, we search for hemicontractive maps that send bar(x)\bar{x} close to itself.
2. Main results
Theorem 8 (Collage Theorem for Hemicontractive Maps). Let XX be a real Banach space and TT a hemicontractive map with contraction factor k in(0,1)k \in(0,1) and fixed point x^(**)in Xx^{*} \in X. Then for any x in Xx \in X,
||x-x^(**)|| <= (1)/(1-k)||x-Tx||\left\|x-x^{*}\right\| \leq \frac{1}{1-k}\|x-T x\|
Proof. The hemicontractive condition assures that the fixed point x^(**)x^{*} exists and it 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 using (1) and (2) one obtains
{:[||x-x^(**)||^(2)=(:x-x^(**),j(x-x^(**)):)],[=(:Tx-Tx^(**),j(x-x^(**)):)+(:x-Tx,j(x-x^(**)):)],[ <= k||x-x^(**)||^(2)+(:x-Tx,j(x-x^(**)):)],[ <= k||x-x^(**)||^(2)+||x-Tx||||x-x^(**)||]:}\begin{aligned}
\left\|x-x^{*}\right\|^{2} & =\left\langle x-x^{*}, j\left(x-x^{*}\right)\right\rangle \\
& =\left\langle T x-T x^{*}, j\left(x-x^{*}\right)\right\rangle+\left\langle x-T x, j\left(x-x^{*}\right)\right\rangle \\
& \leq k\left\|x-x^{*}\right\|^{2}+\left\langle x-T x, j\left(x-x^{*}\right)\right\rangle \\
& \leq k\left\|x-x^{*}\right\|^{2}+\|x-T x\|\left\|x-x^{*}\right\|
\end{aligned}
From which one gets the conclusion.
The above "Collage Theorem" allows us to reformulate the inverse Problem 6 in the particular and more convenient Problem 7.
The above "Collage Theorem" allows us to reformulate the inverse Problem 6 in the particular and more convenient Problem 7.
Theorem 9. If Problem 7 has a solution, then Problem 6 has a solution too.
Proof. Let epsi > 0\varepsilon>0 and bar(x)in X\bar{x} \in X be given. For delta:=(1-k)epsi\delta:=(1-k) \varepsilon, let T_(delta)inT_{\delta} \in HemiLip 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 hemicontractive mapping T_(delta)T_{\delta}, then, by Theorem 8,
Proof. Let epsi > 0\varepsilon>0 and bar(x)in X\bar{x} \in X be given. For delta:=(1-k)epsi\delta:=(1-k) \varepsilon, let T_(delta)inT_{\delta} \in HemiLip 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 hemicontractive mapping T_(delta)T_{\delta}, then, by Theorem 8,
||( bar(x))-x_(T_(delta))^(**)|| <= (1)/(1-k)||( bar(x))-T_(delta)( bar(x))|| <= (1)/(1-k)delta=epsi.\left\|\bar{x}-x_{T_{\delta}}^{*}\right\| \leq \frac{1}{1-k}\left\|\bar{x}-T_{\delta} \bar{x}\right\| \leq \frac{1}{1-k} \delta=\varepsilon .
Note that shrinking the distance between two operators, one of them from HemiLip, reduces the distance between their fixed points.
Proposition 10. Let XX be a real Banach space and T_(1)inT_{1} \in HemiLip with contraction factor k_(1)in(0,1)k_{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-k_(1))s u p_(x in X)||T_(1)x-T_(2)x||\left\|x_{1}^{*}-x_{2}^{*}\right\| \leq \frac{1}{1-k_{1}} \sup _{x \in X}\left\|T_{1} x-T_{2} x\right\|
Proof. Using (2) one obtains
{:[||x_(1)^(**)-x_(2)^(**)||^(2)=(:x_(1)^(**)-x_(2)^(**),j(x_(1)^(**)-x_(2)^(**)):)=(:T_(1)x_(1)^(**)-T_(2)x_(2)^(**),j(x_(1)^(**)-x_(2)^(**)):)],[=(:T_(1)x_(1)^(**)-T_(1)x_(2)^(**),j(x_(1)^(**)-x_(2)^(**)):)+(:T_(1)x_(2)^(**)-T_(2)x_(2)^(**),j(x_(1)^(**)-x_(2)^(**)):)],[ <= k_(1)||x_(1)^(**)-x_(2)^(**)||^(2)+||x_(1)^(**)-x_(2)^(**)||||T_(1)x_(2)^(**)-T_(2)x_(2)^(**)||],[ <= k_(1)||x_(1)^(**)-x_(2)^(**)||^(2)+||x_(1)^(**)-x_(2)^(**)||(s u p_(x in X)||T_(1)x-T_(2)x||)","]:}\begin{aligned}
\left\|x_{1}^{*}-x_{2}^{*}\right\|^{2} & =\left\langle x_{1}^{*}-x_{2}^{*}, j\left(x_{1}^{*}-x_{2}^{*}\right)\right\rangle=\left\langle T_{1} x_{1}^{*}-T_{2} x_{2}^{*}, j\left(x_{1}^{*}-x_{2}^{*}\right)\right\rangle \\
& =\left\langle T_{1} x_{1}^{*}-T_{1} x_{2}^{*}, j\left(x_{1}^{*}-x_{2}^{*}\right)\right\rangle+\left\langle T_{1} x_{2}^{*}-T_{2} x_{2}^{*}, j\left(x_{1}^{*}-x_{2}^{*}\right)\right\rangle \\
& \leq k_{1}\left\|x_{1}^{*}-x_{2}^{*}\right\|^{2}+\left\|x_{1}^{*}-x_{2}^{*}\right\|\left\|T_{1} x_{2}^{*}-T_{2} x_{2}^{*}\right\| \\
& \leq k_{1}\left\|x_{1}^{*}-x_{2}^{*}\right\|^{2}+\left\|x_{1}^{*}-x_{2}^{*}\right\|\left(\sup _{x \in X}\left\|T_{1} x-T_{2} x\right\|\right),
\end{aligned}
from which we get the conclusion.
Theorem 11. 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)inT_{1} \in HemiLip 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
Theorem 11. 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)inT_{1} \in HemiLip 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+L)/(1-k)epsi\left\|\bar{x}-T_{1} \bar{x}\right\| \leq \frac{1+L}{1-k} \varepsilon
Proof. Let x^(**)=T_(1)x^(**)x^{*}=T_{1} x^{*}, and by use of Proposition 10 we obtain
||( bar(x))-x^(**)|| <= (1)/(1-k)(s u p_(x in X)||T_(1)x-Tx||)\left\|\bar{x}-x^{*}\right\| \leq \frac{1}{1-k}\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))||],[ <= ||x-x_(1)||+||T_(1)x^(**)-T_(1)( bar(x))||],[ <= (1+L)||( bar(x))-x^(**)||],[ <= (1+L)/(1-k)(s u p_(x in X)||T_(1)x-Tx||) <= (1+L)/(1-k)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\|x-x_{1}\right\|+\left\|T_{1} x^{*}-T_{1} \bar{x}\right\| \\
& \leq(1+L)\left\|\bar{x}-x^{*}\right\| \\
& \leq \frac{1+L}{1-k}\left(\sup _{x \in X}\left\|T_{1} x-T x\right\|\right) \leq \frac{1+L}{1-k} \varepsilon .
\end{aligned}
3. Application
Example 12. Let A in(0,1),B,C,D inRA \in(0,1), B, C, D \in \mathbb{R} be fixed numbers and F:[0,3]xx[0,3]rarrR^(2)F:[0,3] \times[0,3] \rightarrow \mathbb{R}^{2} be given by F(x,y)=(Ax+Bxy-Cy,Ay-Bx^(2)+Cx)F(x, y)= \left(A x+B x y-C y, A y-B x^{2}+C x\right). Then FF is Lipschitzian and hemicontractive with bounded range.
Proof. It is obvious that FF is Lipschitzian and has bounded range. In order to prove that it is hemicontractive, note that
Proof. It is obvious that FF is Lipschitzian and has bounded range. In order to prove that it is hemicontractive, note that
{:[(:F(x","y)","(x","y):)=(:(Ax+Bxy-Cy,Ay-Bx^(2)+Cx),(x,y):)],[=Ax^(2)+Bx^(2)y-Cxy+Ay^(2)-Bx^(2)y+Cxy],[=A||(x","y)||^(2).quad◻]:}\begin{aligned}
\langle F(x, y),(x, y)\rangle & =\left\langle\left(A x+B x y-C y, A y-B x^{2}+C x\right),(x, y)\right\rangle \\
& =A x^{2}+B x^{2} y-C x y+A y^{2}-B x^{2} y+C x y \\
& =A\|(x, y)\|^{2} . \quad \square
\end{aligned}
Set C=0C=0, to obtain our T_(epsi)T_{\varepsilon} function:
Example 13. Let A in(0,1),B inRA \in(0,1), B \in \mathbb{R} be fixed numbers and H:[0,3]xx[0,3]rarrR^(2)H:[0,3] \times[0,3] \rightarrow \mathbb{R}^{2} be given by H(x,y)=(Ax+Bxy,Ay-Bx^(2))H(x, y)= \left(A x+B x y, A y-B x^{2}\right). Then HH is Lipschitzian and hemicontractive with bounded range.
Example 13. Let A in(0,1),B inRA \in(0,1), B \in \mathbb{R} be fixed numbers and H:[0,3]xx[0,3]rarrR^(2)H:[0,3] \times[0,3] \rightarrow \mathbb{R}^{2} be given by H(x,y)=(Ax+Bxy,Ay-Bx^(2))H(x, y)= \left(A x+B x y, A y-B x^{2}\right). Then HH is Lipschitzian and hemicontractive with bounded range.
Remark 14. Let bar(h)\bar{h} be the "target", in order to find T_(epsi)T_{\varepsilon}. As for fitting, we shall look for an appropriate T_(delta)T_{\delta}. Then by using Matlab (i.e. fminsearch) for min||( bar(h))-T_(delta)( bar(h))||\min \left\|\bar{h}-T_{\delta} \bar{h}\right\|, by Theorem 11 we find the parameters which minimize the problem. Set in Example 13, A=0.3,B=6,T_(epsi):=HA=0.3, B=6, T_{\varepsilon}:=H and let bar(h)=( bar(x), bar(y))=H(( bar(x), bar(y)))\bar{h}=(\bar{x}, \bar{y})=H((\bar{x}, \bar{y})) on ([-1,3]xx[-1,3])([-1,3] \times[-1,3]) be the target generated by T_(epsi)T_{\varepsilon}. Use the above algorithm with T_(delta):=FT_{\delta}:=F, to obtain the HH map, i.e. (A,B,C)=(0.3000,6.0000,0.0000)(A, B, C)=(0.3000,6.0000,0.0000) starting from each point between ( 0.3000,2.0000,2.00000.3000,2.0000,2.0000 ) and ( 0.9000,8.0000,6.00000.9000,8.0000,6.0000 ) .
Remark 15. In Example 13, set A=0,B=0.5,T_(epsi):=HA=0, B=0.5, T_{\varepsilon}:=H and let bar(h)=( bar(x), bar(y))=H(( bar(x), bar(y)))\bar{h}=(\bar{x}, \bar{y})=H((\bar{x}, \bar{y})) on ([-1,3]xx[-1,3])([-1,3] \times[-1,3]) be the target generated by T_(epsi)T_{\varepsilon}. Use again the above algorithm with T_(delta):=FT_{\delta}:=F, to obtain the HH map, i.e. (A,B,C)=(0.00,0.50,0.00)(A, B, C)=(0.00,0.50,0.00) starting from each point between (0.0000,0.3000,0.0000)(0.0000,0.3000,0.0000) and (1.0000,3.0000,1.0000)(1.0000,3.0000,1.0000).
Remark 16. In Example 13, set A=0,B=1,T_(epsi):=HA=0, B=1, T_{\varepsilon}:=H and let bar(h)=( bar(x), bar(y))=H(( bar(x), bar(y)))\bar{h}=(\bar{x}, \bar{y})=H((\bar{x}, \bar{y})) on ([-1,3]xx[-1,3])([-1,3] \times[-1,3]) be the target generated by T_(epsi)T_{\varepsilon}. Use fminsearch with T_(delta):=FT_{\delta}:=F, to obtain the HH map, i.e. (A,B,C)=(0.00,1.00,0.00)(A, B, C)=(0.00,1.00,0.00) starting from each point between (0.2000,0.3000,0.2000)(0.2000,0.3000,0.2000) and (0.7000,0.5000,0.5000)(0.7000,0.5000,0.5000).
Remark 17. In Example 13, set A=1,B=0,T_(epsi):=HA=1, B=0, T_{\varepsilon}:=H and let bar(h)=( bar(x), bar(y))=H(( bar(x), bar(y)))\bar{h}=(\bar{x}, \bar{y})=H((\bar{x}, \bar{y})) on ([-1,3]xx[-1,3])([-1,3] \times[-1,3]) be the target generated by T_(epsi)T_{\varepsilon}. Note that T_(epsi)T_{\varepsilon} is not strongly pseudocontractive. Use fminsearch with T_(delta):=FT_{\delta}:=F, to obtain the HH map, i.e. (A,B,C)=(1.00,0.00,0.00)(A, B, C)=(1.00,0.00,0.00) starting from each point between (0.2000,0.2000,0.2000)(0.2000,0.2000,0.2000) and (0.7000,0.7000,0.7000)(0.7000,0.7000,0.7000).
References
[1] H.E. Kunze, E.R. Vrscay, Solving inverse problems for ordinary differential equations using the Picard contraction mapping, Inverse Problems 15 (1999) 745-770.
[2] H.E. Kunze, S. Gomes, Solving an inverse problem for Urison-type integral equations using Banach's fixed point theorem, Inverse Problems 19 (2003) 411-418.
[3] H.E. Kunze, J.E. Hicken, E.R. Vrscay, Inverse problems for ODEs using contraction maps and suboptimality for the 'collage method', Inverse Problems 20 (2004) 977-991.
[2] H.E. Kunze, S. Gomes, Solving an inverse problem for Urison-type integral equations using Banach's fixed point theorem, Inverse Problems 19 (2003) 411-418.
[3] H.E. Kunze, J.E. Hicken, E.R. Vrscay, Inverse problems for ODEs using contraction maps and suboptimality for the 'collage method', Inverse Problems 20 (2004) 977-991.
- E-mail address: smsoltuz@gmail.com.