Newton-Hines fractals

  • 38 Replies
  • 2007 Views

0 Members and 1 Guest are viewing this topic.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #15 on: April 11, 2019, 08:52:40 AM »
Colorful one with 31 roots and k=30.
Edit: Redid it with smooth iteration coloring.
« Last Edit: April 12, 2019, 02:41:09 AM by gerrit »

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #16 on: April 13, 2019, 08:56:14 AM »
Eye of Sauron from 3000 roots, k=2000.
Some care required in evaluating the iteration functions to avoid over/underflow: compute only \( f(z)/f'(z) \), not the polynomial itself.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #17 on: April 14, 2019, 04:02:48 AM »
Here's an example of fractals associated with modified Newton methods applied to \( F(z)=0 \) with F a rational function.

First one is true Newton. It seems that the region of convergence is bounded as soon as the degree of the denominator is at least as great as that of the numerator, otherwise it's unlimited. This example has degree (5,5), with the poles and zeros (5 colors) at regular angles but at random distance [0 1] from the origin.

A positive Hines parameter k makes the fractal smaller, but making k negative makes it bigger. At \( k=-1/2 \) it suddenly converges everywhere. Second image shows just before the discontinuity at k=-0.49. It "explodes" at k=-0.5.


Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #18 on: April 14, 2019, 04:50:09 AM »
It seems I don't follow the usual Newton fractal method visualization as described on Wikipedia. I'll describe mine.

Solving F(z)=0 with  F(z)=f(z)/g(z), f() and g() are polynomials of orders n and m. I parametrize them in my Ultra Fractal code by the roots of f and g, call them \( a_1, \ldots, a_n \) and \( b_1, \ldots, b_m \).

Newton (Hines with \( k \neq 0 \), damped with \( q \neq 1 \) ) iteration is \( z \leftarrow z - q/(F'(z)/F(z)-k/z) \). I write it in this way to show we only need F'/F. With some highschool algebra we get \( F'/F = f'/f-g'/g \). And \( f'/f = \sum_{i=1}^n \frac{1}{z-a_i} \) and similar for g. This is an important trick if you want n and m to be large as the polynomials f and g can easily under/over flow.

Now for the visualization. Initial z is picked by "pixel" and when iterating I keep track of \( r_j = 1/|z_j-z_{j-1}| \) at iteration j. I set escape radius R=1e6 and terminate when \( r_j>R \). The color index is then j. To smooth it I have saved \( r_{j-1} \) and subtract \( t = \frac{ll(r_j)-ll(R)}{ll(r_{j})-ll(r_{j-1})  } \), with "ll()" the log(log()) function. Just subtracting \( log(log(r_j))/log(2) \) does not suffice; this smooths near quadratic convergence when the iteration behaves like \( z \leftarrow z^2 \) like the Mandelbrot set, but bands for low iterations.

The final complex representation variable m (which you then use to hit a color table or something like that) I take
\( m= \frac{z}{|z|} \sqrt{j-t} \), then color it using the phase for hue and the magnitude for value and saturation after some "artsy" transfer functions.

To interactively find interesting k values I use Ultra Fractal's "explore parameter" feature, which is very nice. Below and example with just a polynomial with 11 roots. (The 11th one is small and just barely visible in the center.)

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #19 on: April 14, 2019, 11:21:33 PM »
A polynomial with \( 2^{33} \) roots, made out of 33 \( z^2+c \) iterations (at z=0 as function of c).
\( k=3.6+5.7 i \) gives it the asymmetry.

Second image:  \( 2^{1000} \) roots, zoom into "seahorse valley".
« Last Edit: April 14, 2019, 11:52:05 PM by gerrit »

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #20 on: April 17, 2019, 02:18:09 AM »
Order 311 polynomial with Hines factor k=311. k=#zeros seems to be a good value for interesting pictures.

Online pauldelbrot

  • *
  • 3f
  • ******
  • Posts: 1784
« Reply #21 on: April 17, 2019, 03:51:56 AM »
:O

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #22 on: April 24, 2019, 05:44:28 AM »
Plain Newton method applied to rational function with 55 random zeros and 55 random poles.
Second image a zoom (about 1e9 deep).

Offline Sabine62

  • *
  • Fractal Freak
  • **
  • Posts: 668
  • It's just a jump to the left...
    • sabine62.deviantart.com
« Reply #23 on: April 24, 2019, 09:09:27 AM »
Congratulations, Gerrit, beautiful results with your approach!  :thumbs:
To thine own self be true

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #24 on: April 25, 2019, 02:53:45 AM »
300 roots, giving it a spin with a large imaginary component of the Hines factor.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #25 on: May 09, 2019, 07:59:44 AM »
In some applications it's not possible to compute the derivative of the function analytically, e.g., it may be given in "black box" form, or z may be billion dimensional.

A popular method to numerically solve F(z)=0 in such cases is the secant method. It's like Newton except you approximate \(  F'(z_n) \) by  \( \frac{F(z_n)-F(z_{n-1})}{z_n-z_{n-1}} \).

To kickstart this method you need to give both z0 and z1. I use a normal Newton iteration for z1, to avoid a 4D fractal.

Below Newton's and the secant method with the previously described coloring for a function with 11 randomized zeros. (Hines factor k=0 for both.)
While Newton's method never blows up (escape to infinity), secant does. Those regions are bright red.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #26 on: May 09, 2019, 08:18:53 AM »
Secant method applied to rational function with 11 zeros and 7 poles (all random). Green is diverging. Newton looks uninteresting for this one.

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #27 on: May 11, 2019, 02:03:57 AM »
I beleive that with k=1 you get Halley's method and with k=2 Schroder's method.
it is a nice find, and I will definately add it to my collection!
https://en.wikibooks.org/wiki/Fractals/fractalzoomer#Root_Finding_Methods
Looking at that page, it seems the Schroder and Householder methods do not correspond at all to what you find elsewhere about these methods.

Halley and Steffensen and secant methods are correct on that wiki, the others I haven't checked.
« Last Edit: May 11, 2019, 04:24:49 AM by gerrit »

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #28 on: May 11, 2019, 04:32:12 AM »
Steffenson method for polynomial with 31 zeros at equispaced angles if that's a word but random distance + Nwwton for comparison (secant looks almost the same as Newton). Solid yellow = "diverging".

Offline gerrit

  • *
  • 3f
  • ******
  • Posts: 2005
« Reply #29 on: May 13, 2019, 07:30:17 AM »
Added Halley's method to my menu. This converges cubically so will require about 37% fewer iterations than Newton (log(2)/log(3)). Unfortunately it needs second derivatives which makes those fewer iterations much more expensive. I'm not aware of any practical application of this method.

For rational functions F=f/g with f and g polynomials you need only f'/f and f''/f (and for g same of course). f'/f I already gave without computing f, and
\( f''/f = 2\sum_{i<j}\frac{1}{(z-a_i)(z-a_j)} \) with \( a_i \) the roots.

Below examples for an F with 13 poles and 13 zeros (randomized) using Newton, secant, Steffensen, and Halley. Solid yellow is "diverging".


xx
Slightly extended Newton method fractals

Started by gannjondal on Fractal Mathematics And New Theories

6 Replies
341 Views
Last post September 29, 2019, 10:18:01 PM
by gerrit
clip
Mandelbrot/Newton - Has it already been done?

Started by mrrudewords on Share a fractal

2 Replies
458 Views
Last post February 09, 2019, 09:35:17 PM
by mrrudewords
xx
Newton's Garden

Started by gannjondal on Fractal Image Gallery

4 Replies
417 Views
Last post April 17, 2018, 11:22:45 PM
by spain2points
xx
Newton (gannjondal)

Started by Sabine62 on Fractal Image Gallery

0 Replies
160 Views
Last post August 15, 2018, 04:28:09 PM
by Sabine62
clip
Revisiting the 3D Newton

Started by gannjondal on Fractal Mathematics And New Theories

26 Replies
2340 Views
Last post October 01, 2018, 10:24:43 PM
by FractalDave