Newton Raphson - Reciprocal Square Root Convergence

Question

I'm attempting to use Newton Raphson method to calculate the square root of fixed point numbers.

The mathematics I understand - and, using this question I easily managed the normal;

$x_{n+1} = \frac{1}{2}(x_n+\frac{a}{x_n})$ to generate $\sqrt{a}$

And then, because I will be using this algorithm for computing, decided to try for the more complex reciprocal algorithm that uses only multiplication:

$x_{n+1} = x_n(1.5 - 0.5 a x_n^2)$ to generate $\frac{1}{\sqrt{a}}$

Which, to check, I also derived normally from the Newton Raphson equation shown in the question linked above.

However, whilst the first equation converges as expected, the second, does not, although I cannot find anywhere the rules for this convergence. For example:

$a = 100$, and $ x_0 = 16$

$x_1 = 16(1.5 - 0.5\times 100 \times 16^2) = -204776$ $x_2 = -204776(1.5 - 0.5\times 100 \times (-204776)^2) = -2.62\times10^9$

As I'm sure you'd agree - this is not converging to 10 - clearly I'm doing something wrong and yet I followed the normal Newton Raphson procedure in deriving it, and it works for the simpler formula. What are the conditions for this one?

Thanks very much!

Answer 1

The Newton-Raphson method converges only if the starting pont is "sufficiently near" the desired root. In your case the "desired root" is ${1\over\sqrt{a}}$. Therefore I suggest you rewrite your recursion formula (which I have not checked) in terms of the new variable $t_n:=x_n-{1\over\sqrt{a}}$ and analyze for which starting values $t_0$ you can guarantee $t_n\to0$. Maybe it helps to assume $a=1$ in order to obtain a first overview.

Answer 2

Since $$ \sqrt{a}x_{n+1}-1=\sqrt{a}x_n-1+0.5\sqrt{a}x_n(1+\sqrt{a}x_n)(1-\sqrt{a}x_n) \\ =(\sqrt{a}x_n-1)(1-0.5\sqrt{a}x_n(1+\sqrt{a}x_n)) \\ =-(1+0.5\sqrt{a}x_n)(\sqrt{a}x_n-1)^2 $$ you will get quadratic convergence if $$ \frac12<\sqrt{a}x_0<\frac32 \text{ or } \frac14<ax_0^2<\frac94, $$ so that $|1+0.5\sqrt{a}x_0|<\frac74<2$ and $\frac74|\sqrt{a}x_0-1|<\frac78<1$. Which then implies $$ |\sqrt{a}x_n-1|<\frac47\left(\frac74|\sqrt{a}x_0-1|\right)^{2^n}<\frac12\left(\frac78\right)^{2^n-1} $$ Your parameter and initial value fall far away from that condition.