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!
Best Answer
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.