0
$\begingroup$

I am working with the following function

enter image description here

where r= 2^(-d) and d =[1:100]

I am comparing 5 different algorithms to compute the roots of this function but the Newton Raphson method doesn't converge anymore above a certain value of r.

Column n°5 on this screenshot

enter image description here

How can I solve this issue?

Thank you in advance

$\endgroup$
  • $\begingroup$ Hey I found the issue. The initial value is too small to let NR converge so if I set the initial value to something like 0.5 it converges no problem $\endgroup$ – Yrden May 3 '18 at 7:01
0
$\begingroup$

Admitting that you look for the first positive zero of equation $$f(u)=2 \sin ^2\left(\frac{\pi}{2} \left(4 u^3-3 u^4\right)\right)-\frac 1 {2^d}$$ I am rather surprised by the value $3.1803$ given in the table for $d=2$; it effectively corresponds to the $n^{th}$ root of the equation for a very large $n$ (i gave up trying to count it !).

The key problem with Newton method is the initial guess. What we know, at least from the very first case $(d=1)$ is that the root is small. So, using Taylor expansion around $u=0$, what we have is $$2 \sin ^2\left(\frac{\pi}{2} \left(4 u^3-3 u^4\right)\right)=8 \pi ^2 u^6-12 \pi ^2 u^7+O\left(u^8\right)$$ giving as an initial underestimate $$u_0=\frac 1 {\sqrt[6]{\pi^2\, 2^{d+3}}}$$ By Darboux-Fourier theorem, we know that we shall face one overshoot of the solution since, for any $d$, $f(u_0)\times f''(u_0) <0$.

Using the method for $d=1$, the iterates are $$\left( \begin{array}{cc} n & u_n \\ 0 & 0.430127 \\ 1 & 0.542201 \\ 2 & 0.515233 \\ 3 & 0.513710 \\ 4 & 0.513705 \end{array} \right)$$ Doing the same for $d=2$ $$\left( \begin{array}{cc} n & u_n \\ 0 & 0.383200 \\ 1 & 0.459453 \\ 2 & 0.442439 \\ 3 & 0.441355 \\ 4 & 0.441351 \end{array} \right)$$ Working with illimited precision, Newton method converges without any problem (I tried up to $d=10^6$).

Working with limited precision (all numbers being declared as double precision real numbers - the $2$ in the definition of $r$ is crucial) and using as convergence criteria $\frac{|\Delta u|} u \leq 10^{-16}$, I did not face any problem at all except above $d=1017$ $(2^{-1018}\approx 3.56 \times 10^{-307})$. For $d \geq 978$, the estimate was the solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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