(Question) Newton Raphson - how long wilt it run ?

  • 10 Replies
  • 264 Views

0 Members and 1 Guest are viewing this topic.

Offline CFJH

  • *
  • Fractal Furball
  • ***
  • Posts: 273
« on: May 11, 2019, 01:38:20 PM »
Hallo

I', running a Newton-Raphson-Zoom on the following location (Attachment)
Until now, the computer is running 2 month. Current Display in kf is "Newton-Raphson 18 / 4%"
Is it possible, to approximate the still needed time to finish (I need to reboot the pc for installation) ?
Is it possible to set a "save point" ?
kf-version is 14.4 on opensuse linux via wine. CPU is a i7-2600.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1730
« Reply #1 on: May 11, 2019, 08:09:26 PM »
Hallo

I', running a Newton-Raphson-Zoom on the following location (Attachment)
Until now, the computer is running 2 month. Current Display in kf is "Newton-Raphson 18 / 4%"
Is it possible, to approximate the still needed time to finish (I need to reboot the pc for installation) ?
Is it possible to set a "save point" ?
kf-version is 14.4 on opensuse linux via wine. CPU is a i7-2600.
NR in KF takes about log2(log10(zoom)) iterations, which is fairly accurate in my experience.

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1154
    • mathr.co.uk
« Reply #2 on: May 14, 2019, 12:31:31 AM »
Is it possible to set a "save point" ?
only by running KF in a VM and snapshotting the whole VM.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1730
« Reply #3 on: May 14, 2019, 07:44:37 AM »
Is the cubic Halley's method worth considering for extremely deep NR zooms?
Usually  the extra cost of evaluating f'' is not worth it and most Newton iterations iterate just a few times.

But for deep KF zoom (say 1e30000) we need something like 15 iterations. With a cubic convergence that would be only 10 which would save about 3 weeks in the example of this thread.

And in this case the main cost of each iteration is the full-precision orbit (z) whereas the derivative(s) can be done in normal precision (with floatexp probably) so the usual downside of Halley doesn't apply.

Update is \( -1/(\frac{f'}{f} -\frac{f''}{2f'}) \).

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1154
    • mathr.co.uk
« Reply #4 on: May 14, 2019, 02:16:36 PM »
the derivative(s) can be done in normal precision
Really?  At least for Newton's method, doing the derivative in machine precision means at most 53 bits are added to the correct portion each time, instead of doubling the number of correct bits.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1730
« Reply #5 on: May 14, 2019, 04:15:55 PM »
Really?  At least for Newton's method, doing the derivative in machine precision means at most 53 bits are added to the correct portion each time, instead of doubling the number of correct bits.
That kills the idea. Can you explain why?

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1154
    • mathr.co.uk
« Reply #6 on: May 14, 2019, 04:39:25 PM »
I think I worked it out once before with help from IRC or M.SE or so, can't remember the details but I started from z → z - f / (f' (1+e)) where e = O(2-53)

If this is wrong, and the derivative really can be calculated in low precision, NR in KF could be made more efficient (CPU time, wall-clock time still limited by the Z orbit)

Even with high precision needed, higher order methods may be faster (wall-clock time reduced due to fewer root-finding steps) because of potential for concurrent evaluation of parts of the formula (total CPU time may be higher)

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1730
« Reply #7 on: May 14, 2019, 04:54:55 PM »
I was going to edit my post as it became obvious that you're right after breakfast, but you beat me to it.
Error in f/f' is determined by the most inaccurate one, of course.

So that was a bad idea but yours is good I think: If you can calculate f'' in full precision on another processor it could work.

Halley method works by locally approximating the function by an order (1,1) rational function (Pade approximant) which has 3 coefficients.

From experiments in Newton-Hines thread it seems Halley has smaller basins of attraction; I should try it on a "Mandelbrot polynomial".
« Last Edit: May 14, 2019, 05:08:16 PM by gerrit »

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1154
    • mathr.co.uk
« Reply #8 on: May 14, 2019, 05:07:00 PM »
Here is a table I just calculated.  First number is bits of accuracy in f', second number is number of steps required to converge, for the function z^2+c iterated 3 times starting from -2 (real only)

(1,33)
(2,24)
(3,18)
(4,15)
(5,12)
(6,11)
(7,10)
(8,9)
(10,8)
(13,7)
(24,6)

6 steps were requires with full accuracy.  Tested with Double.

Code: [Select]
-- Haskell
import Data.Function
import Data.List
fdf n c = if n == 0 then (0, 0) else let (z, dz) = fdf (n - 1) c in (z^2 + c, 2 * z * dz + 1)
newton bits gdg c = let (z, dz) = gdg c in c - z / (dz * (1 + 0.5 ^ bits))
converge (x:y:zs) = if x == y then [x] else x:converge (y:zs)
main = mapM_ print . map head . groupBy ((==) `on` snd) $ [ (b, length . converge . iterate (newton b (fdf 3)) . negate $ 2) | b <- [1..53] ]

Offline claude

  • *
  • 3f
  • ******
  • Posts: 1154
    • mathr.co.uk
« Reply #9 on: May 14, 2019, 06:42:49 PM »
From experiments in Newton-Hines thread it seems Halley has smaller basins of attraction; I should try it on a "Mandelbrot polynomial".

modified polynomials (dividing by polynomials with lower periods that are factors of the target period) have larger Newton basins
maybe something similar can be done for Halley

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 1730
« Reply #10 on: May 14, 2019, 09:01:12 PM »
From experiments in Newton-Hines thread it seems Halley has smaller basins of attraction; I should try it on a "Mandelbrot polynomial".
Checking again that seems to be true only for rational functions that are not polynomials. For polynomials Halley never blows up, like Newton.

The "divide by unwanted zeros" trick (https://mathr.co.uk/blog/2018-11-18_newtons_method_for_periodic_cycles.html) is neat; it works well for Misiurewicz points which I implemented a while ago.


xx
"Time Span"

Started by cricke49 on Fractal Image Gallery

0 Replies
256 Views
Last post August 02, 2018, 07:05:21 AM
by cricke49
xx
The Newton Bulb - Some fruits need to ripe long

Started by gannjondal on Fractal Image Gallery

0 Replies
94 Views
Last post March 13, 2018, 12:00:58 AM
by gannjondal
xx
Newton-Raphson zooming

Started by gerrit on Fractal Mathematics And New Theories

57 Replies
2666 Views
Last post December 12, 2017, 05:42:52 AM
by gerrit
xx
Newton-Raphson Fractal attempt in Xaos

Started by Know That Fractal! on Fractal Image Gallery

0 Replies
198 Views
Last post December 22, 2017, 01:40:55 AM
by Know That Fractal!
xx
Newton-Raphson zooming for Burning Ship

Started by claude on Fractal Mathematics And New Theories

9 Replies
567 Views
Last post January 08, 2018, 03:03:56 PM
by knighty