Newton-Raphson - how is x(n) > 0

Question

Hi this contains the question that I am trying to solve.

The first line of the last paragraph is what I am having trouble with. I don't see immediately how is x(n) > 0

Thank you for any help.

Answer 1

Considering $y_n=\frac1{x_n^2}$ one gets the recursion \begin{align} y_{n+1}=\frac1{x_n^2(1-x_n^2/2)^2} &=\frac{1}{x_n^2}\Bigl(1+x_n^2+\frac34x_n^4+…+\frac{k+1}{2^k}x_n^{2k}+… \Bigr)\\ &=y_n+1+x_n^2\Bigl(\frac34+\frac12 x_n^2+\frac{5}{16}x_n^4+…\Bigr) \end{align} by the square of the geometric series. This results in, for $0<x_n<\frac12$, $$ y_n+1 < y_{n+1} < y_n+1+\frac34\frac{x_n^2}{1-\frac23x_n^2}<y_n+2 $$ or $$ y_0+n<y_n<y_0+2n\iff \frac{10^{-4}}{\sqrt{1+10^{-8}·2n}}\le x_n\le \frac{10^{-4}}{\sqrt{1+10^{-8}·n}} $$ To get the lower bound for $x_n$ below $\frac{x_0}2=\frac12·10^{-4}$ one needs $10^8+2n>4·10^8$ or $n>1.5·10^8$ which indeed is larger than 100 million. The actual index to reach that value will be closer to the crossing of the upper bound, or around $n=300·10^6$

---

Or perhaps without power series $$ y_{n+1}=\frac{y_n^2}{y_n-\frac12}=y_n+1+\frac1{4y_n-2} $$ which again immediately gives, assuming $y_0\ge1$, $y_n\ge y_0+n$ and using that $$ y_0+n\le y_n\le y_0+n+\frac{n}{4y_0-2} $$ which will give a tighter lower bound for the $n$ in the example.

Answer 2

The easy seeing happens in the next sentence: We have $x_{n+1}=x_n(1-x_n^2/2)$, so if we know $0<x_n<\sqrt 2$, we have $0<1-x_n^2/2<1$ and can infer $0<x_{n+1}<x_n<\sqrt 2$.