4
$\begingroup$

Suppose $x_0=x_1=1$, define $y_k=x_k+\frac{1}{2}(x_k-x_{k-1})$ and $x_{k+1}=y_k-\eta y_k^3$ where $\eta\in(0,1/8)$. If we know $x_k\to 0$ as $k\to\infty$. How to show that $x_k=\Theta(1/\sqrt{k})$?

It suffices to show that $x_k^{-2}=\Theta(k)$. By Taylor expansion, we have $$x_{k+1}^{-2} = (y_k-\eta y_k^3)^{-2} = y_k^{-2}(1-\eta y_k^2)^{-2} = y_k^{-2}(1+2\eta y_k^2+o(y_k^2)) = y_k^{-2}+2\eta+o(1)$$ It seems that $x_{k+1}^{-2}$ and $y_k^{-2}$ form a linearly increases sequence. If here $y_k^{-2}$ is replaced by $x_k^{-2}$, then we obtain exactly $x_k^{-2}=\Theta(k)$. However, $y_k^{-2}\ne x_k^{-2}$, and I got stuck at this step. Can someone give a hint?

Improve this question
$\endgroup$
5
  • $\begingroup$ Are you interested in the case where $\eta$ is close to $\frac{1}{8}$? I'm pretty sure I have a proof but it works better if $\eta<\frac{1}{12}$, if $\eta$ is close to $\frac{1}{8}$ it seems like a more complicated argument would be needed $\endgroup$
    – Saúl RM
    Commented Oct 12, 2022 at 22:57
  • $\begingroup$ In fact I think the delicate part is proving that $x_k>0$ for all $k$ and that $\frac{x_{k+1}}{x_k}\to 0$, which seem like they should be obvious at first glance. The condition $\eta<\frac{1}{8}$ is to ensure that the sequence $x_k$ doesn't become negative? $\endgroup$
    – Saúl RM
    Commented Oct 12, 2022 at 23:13
  • $\begingroup$ Thanks for your reply. I can prove $x_{k+1}/x_k\in(0,1)$ for sufficiently large $k$, which means that eventually $x_k$ will not change sign and $|x_k|$ will be decreasing (it is possible to be negative). If we want $x_k=\Theta(1/\sqrt{k})$, then we need to show $x_{k+1}/x_k\to 1$. However, I can only show $x_{k+1}/x_k$ converges to either $1$ or $1/2$, using the result in mathoverflow.net/questions/432262/convergence-of-a-sequence. I don't know how to exclude the possibility that $x_{k+1}/x_k\to 1/2$, and it that is true, then the convergence rate of $x_k$ would be linear convergence. $\endgroup$
    – Jean Legall
    Commented Oct 13, 2022 at 3:52
  • $\begingroup$ For $\eta=1/8$, I run numerical experiments and it seems that the whole sequence $x_k$ is positive and decreasing. Furthermore, as $k\to\infty$, I found that $kx_k^2\to 2$. It would still be very helpful if you can write your proof for $\eta<1/12$. @SaúlRM $\endgroup$
    – Jean Legall
    Commented Oct 13, 2022 at 4:03
  • $\begingroup$ I see. In the end I didn't need $\eta<\frac{1}{12}$, it can be improved to $\frac{1}{8}$ with one more line of argument. I wrote my answer supposing that $x_k>0$ for all $k$, although that is not obvious to me $\endgroup$
    – Saúl RM
    Commented Oct 13, 2022 at 14:32

1 Answer 1

Reset to default
1
$\begingroup$

Suppose that we already know that $x_k>0\forall k$. Clearly $(x_k)$ and $(y_k)$ are decreasing sequences which converge to $0$. Then we can prove that $b_k:=\frac{x_{k}}{x_{k-1}}\to 1$. To do it note first that $b_k\in[0,1]\forall k$ and

$$b_{k+1}=\frac{y_k-\eta y_k^3}{x_k}=\frac{x_k+\frac{1}{2}(x_k-x_{k-1})-\eta y_k^3}{b_kx_{k-1}}=\frac{3}{2}\frac{x_k}{b_kx_{k-1}}-\frac{1}{2b_k}-\eta\frac{y_k^3}{b_kx_{k-1}}=$$

$$=\frac{3}{2}-\frac{1}{2b_k}-\eta\frac{y_k^3}{b_kx_{k-1}}>\frac{3}{2}-\frac{1}{2b_k}-\eta\frac{x_k^3}{b_kx_{k-1}}=\frac{3}{2}-\frac{1}{2b_k}-\eta x_k^2.$$

So $b_{k+1}>\frac{3}{2}-\frac{1}{2b_k}-\eta x_k^2$. Now note that $x_k<1-\frac{3}{2}\eta$ for all $k\geq3$, so that $b_{k+1}>\frac{3}{2}-\frac{1}{2b_k}-\eta(1-\frac{3}{2}\eta)^2>\frac{3}{2}-\frac{1}{2b_k}-\frac{1}{8}(1-\frac{3}{16})^2=\frac{2903}{2048}-\frac{1}{2b_k}\sim1.407-\frac{1}{2b_k}$.

Using this you can prove by induction that $b_k>0.7$ for all $k$ (as base case you need to check $b_2,b_3>0.7$). Using that fact and that:

  • $b_{k+1}>\frac{3}{2}-\frac{1}{2b_k}-x_k^2$

  • $x_k\to0$

it's not difficult to prove that $b_k\to 1$.

Now let's prove that $x_k=\Theta(\frac{1}{\sqrt{k}})$. To do it we will compare it with the sequence $a_k=\frac{1}{10\sqrt{k}}$. Note that we have $a_{k+1}<a_k-10a_k^3$. So if we prove that for big enough $k$ we have $x_{k+1}>x_k-10x_k^3$, then our series will decrease slower than $a_k$ and we will be done.

This is equivalent to proving $\frac{x_k-x_{k+1}}{x_k^3}<10$ for big enough $k$. So let's study $c_k:=\frac{x_k-x_{k+1}}{x_k^3}$. Of course $c_k$ is always positive, and we have

$$c_{k}=\frac{x_k-x_{k+1}}{x_k^3}=\frac{x_k-y_k+\eta y_k^3}{b_k^3x_{k-1}^3}=\frac{\frac{1}{2}(x_{k-1}-x_k)+\eta y_k^3}{b_k^3x_{k-1}^3}=\frac{1}{2b_k^3}c_{k-1}+\frac{\eta}{b_k^3}\left(\frac{y_k}{x_{k-1}}\right)^3.$$ Now using that $b_k\to 1$ and $\frac{y_k}{x_{k-1}}\to1$, the inequality implies that for big $k$ we have $c_k<0.7c_{k-1}+1$. So for big enough $k$ we have $c_k<10$, as we wanted.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .