Iteration with bounded converging sequence as input

175 Views Asked by At

Consider the sequence of vectors $( x_k )_{k=0}^{\infty}$ such that $x_k \in X \subset \mathbb{R}^n$ for all $k$, where $X$ is compact, and $x_k \rightarrow \bar{x} \in X$.

Consider a vector $y_0 \in Y$ and a Lipschitz continuous function $f : \mathbb{R}^n \times \mathbb{R}^n \rightarrow Y \subset \mathbb{R}^n$, where $Y$ is compact, with the following property. For all $z \in X$, there exists $y \in Y$ such that the sequence of vectors $\left( y_{k+1}:= f(y_k, z) \right)_{k=0}^{\infty}$ is such that $y_k \rightarrow y$.

Prove or disprove the following statement: $$\exists \bar{y} \in Y : \ y_{k+1} := f( y_k, x_k ) \rightarrow \bar{y} \in Y$$

Comments: I have tried to take $\bar{k}$ large enough, so that $x_k \in \bar{x} + \epsilon B$ for all $k \geq \bar{k}$. But then I am not sure how to exploit the Lipschitz continuity of $f$ to claim that $y_k$ stays close to $f(\bar{y},\bar{x})$. Clearly, if the sequence $(y_k)_k$ converges to some $\bar{y} \in Y$, then $\bar{y} = f(\bar{y}, \bar{x})$.

1

There are 1 best solutions below

4
On BEST ANSWER

This is not true. Here is an example.

Define the compact sets $X$ and $Y$ as \begin{align} X &= \left\{2, \frac{3}{4}+\frac{\sqrt{5}}{4}\right\} \: \: \: \: \mbox{(so this set has only 2 elements)}\\ Y &= [-100,100] \: \: \: \: \mbox{(big enough so its endpoints are never reached)} \end{align} Define $f:\mathbb{R}^2\rightarrow\mathbb{R}$ as $$ f(y,z) = \left[y((1-y)g(z)+z)\right]_{-100}^{100} $$ where $[a]_{-100}^{100}$ denotes the projection of $a$ onto the interval $[-100,100]$ and $g(z)$ is the affine function that satisfies:
$$ g(z) = \left\{ \begin{array}{ll} 2 &\mbox{ if $z =2$} \\ \frac{-z}{1-z} & \mbox{ if $z = \frac{3}{4} +\frac{\sqrt{5}}{4}$} \end{array} \right. $$ With this construction we have $g(z) = \frac{-z}{1-z}$ for all $z \in X$. Of course, $g(z)$ is still an affine function of $z$ when viewed as a function over $z \in \mathbb{R}$. Overall, this function $f(y,z)$ is Lipschitz continuous over $(y,z) \in \mathbb{R}^2$.


Define $y_0=1$. Then for any $z \in X$: \begin{align} y_1 &= f(y_0,z)= f(1,z) = z \\ y_2 &= f(y_1, z) = f(z,z) = z\left((1-z)\frac{-z}{1-z}+z\right)=0\\ y_3 &= f(y_2,z) = f(0,z) = 0\\ y_k &= 0 \: \: \forall k \geq 3 \end{align}

Thus, this satisfies the desired property that for all $z \in X$, the iteration $y_0=1$ and $y_{k+1} = f(y_k,z)$ yields $\lim_{k\rightarrow\infty} y_k=0$.


Now consider the sequence $\{x_k\}_{k=0}^{\infty} = \{3/4 + \sqrt{5}/4, 2, 2, 2, 2, \ldots \}$, which clearly converges to $\overline{x}=2$ in the limit. Again assuming $y_0=1$ we get: \begin{align} y_1 &= f(y_0,x_0)= f(1,x_0) = x_0\\ y_2 &= f(y_1,x_1) = f(x_0,2) = \frac{5}{4} + \frac{\sqrt{5}}{4}\\ y_3 &= f(y_2, x_2) = f(y_2, 2) = \frac{5}{4} - \frac{\sqrt{5}}{4}\\ y_4 &= f(y_3, x_3) = f(y_3, 2) = y_2 \\ y_5 &= y_3 \\ y_6 & = y_2 \end{align} and so on, so we oscillate between $y_2$ and $y_3$ without converging.