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?

$\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$ 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$ 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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.