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!

up vote 2 down vote accepted

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.

  • 1
    Would it be fair to say then, that to prevent the $x_{n}^2$ term dominating, the starting condition must have the same power of 10 as $a$ but inverse, so that $x_{n}^2\times a < 1$ – davidhood2 Mar 7 '16 at 21:12
  • Just to expand on my comment above - given the answer below regarding convergence - the word "must" is a poor choice, but would it work as a reasonable "rule of thumb"? – davidhood2 Mar 7 '16 at 21:57

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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