0

Let $\{x_k\}_{k\geq 0}$ be a sequence such that $||x_{k+1}-x_*|| \leq ||x_k-x_*||$ holds for all $k=0, 1, \dots$ where $x_*, x_k \in \mathbb{R}^n$. Under what conditions it is guaranteed that $x_k\to x_*$?

My try: I know when there is no equality we can divide by $||x_0-x_*||$ and sum over all the inequalities to get an upper bound on the sum and say $x_k\to x_*$. But for some possible cases where we have equality, I do not know how to mange. Also, when $x^*$ is a bounded point, I do not how to show $\{x_k\}_{k\geq 0}$ is bounded.

Saeed
  • 175
  • 1
    What have you tried? Or where did you get stuck? – Nevzat Eren Akkaya Aug 20 '21 at 23:57
  • @Nevzat Eren Akkaya: I added my try to the question. – Saeed Aug 21 '21 at 00:17
  • You use subscript $k$ in your definition of the sequence, and then superscript later. Do you still mean subscript $k$? – tolUene Aug 21 '21 at 00:30
  • @tolUene: my bad. I edited it. – Saeed Aug 21 '21 at 00:32
  • So you mean do mean exponentiation, not just any sequence, right? In that case, you can use that $\lVert x^k \rVert \rightarrow 0$ for $\lVert x \rVert < 1$, $\lVert x^k \rVert \rightarrow 1$ for $\lVert x \rVert = 1$ and diverges otherwise (note that $x = -1$ still diverges, but the convergence of the absolute value does hold). – tolUene Aug 21 '21 at 00:34
  • @tolUene It only makes sense as sequence notation, not exponentiation – Alan Aug 21 '21 at 00:35
  • @Alan I've never seen sequences be notated with superscripts in analysis before, probably because of exactly this ambiguity. – tolUene Aug 21 '21 at 00:37
  • 1
    @tolUene: superscript means sequence not exponentiation. I will correct it. – Saeed Aug 21 '21 at 00:44
  • I actually went ahead and answered it in both interpretations, will leave the "wrong" way in just for amusement. – Alan Aug 21 '21 at 00:45

2 Answers2

1

This answer is assuming your $x^k$ is labeling the $k$'th term of the sequence, not exponentiation.

I can't imagine any criteria you could add short of actual convergence. As it is, because you have $\leq$, all you are saying is that the distance from the points in your sequence do not increase from your proposed limit. They could completely bounce around the hypersphere around the point randomly though, which is very non convergent.

Even if you switched it to a strict inequality, you could have the distances asymptotically approaching any number you want, just by spiraling inward with an exponential decay part. So pretty much the only thing in that notation that would guarantee it would be that the distances go down to 0...but that's the definition of convergence.

Alan
  • 16,582
  • can you please remove the exponent part from your answer. – Saeed Aug 21 '21 at 00:49
  • What do you mean by "but that's the definition of convergence."? are you saying it converges if we have strict inequality? – Saeed Aug 21 '21 at 00:51
  • I'm saying that the limit of the distance of the points goes to 0 is the definition of convergence. – Alan Aug 21 '21 at 00:52
1

If there exists $c<1$ such that $\|x_{k+1}-x^*\|\leqslant c\|x_k-x_*\|$, then as you said $\|x_k-x_*\|\leqslant c^k\|x_0-x^*\|$ therefore $x_k\rightarrow x_*$. If such a $c$ doesn't exist, we can't say anything. Indeed if $(x_k)$ converges to $x_*$, then $x_{\lfloor k/2\rfloor}\rightarrow x_*$ but $\|x_{\lfloor (2k+1)/2\rfloor}-x_*\|=\|x_{\lfloor 2k/2\rfloor}-x_*\|$ so such a $c$ doesn't exist for $(x_{\lfloor k/2\rfloor})$ even tough it converges to $x_*$. On the other hand, for any isometry $f:\mathbb{S}^{n-1}\rightarrow\mathbb{S}^{n-1}$, if $x_*:=0$ and $x_k:=f^k(x_0)$ for any $x_0\in\mathbb{S}^{n-1}$, then $$ \|x_{k+1}-x_*\|=\|x_k-x_*\|=1 $$ even though $(x_k)$ does not converge in general, and never converges to $0$.

Note : Even if $\|x_{k+1}-x_*\|<\|x_k-x_*\|$, it can converge to $x_*$ as seen previously, but it can also not converge to $x_*$. Take $x_{k+1}:=x_*+\left(1-\frac{1}{2^k}\right)(x_k-x_*)$, then $\|x_{k+1}-x_*\|<\|x_k-x_*\|$ for all $k$ but $$ \|x_k-x_*\|=\|x_0-x_*\|\prod_{i=0}^{k-1}\left(1-\frac{1}{2^i}\right)\underset{k\rightarrow +\infty}{\longrightarrow}\|x_0-x_*\|\prod_{i=0}^{+\infty}\left(1-\frac{1}{2^i}\right)>0 $$ thus $(x_k)$ does not converge to $x_*$.

Tuvasbien
  • 8,907