Fractals: symmetrical roots

By Brad Rodgers (P1930) on Thursday, February 1, 2001 - 12:50 am :

I've recently been playing aroung with the fractal "Newton" using different roots.
$Newton fractal$
First off, can someone tell me the algorithm used to find this (I know how normal fractals (mandel,julia etc. work). I know it's iteration formula is

z_{n + 1} = ([p - 1] z_{n}^{p} + 1) / (p \times z_{n}^{p - 1})

where p is the polynomial degree used. I know this formula has to be different from ordinary fractals as it isn't a base color (for 1 iteration needed) along the real axis.

Second question of the same nature. I've realized that when you find the nth root of say r, then there will be n solutions each distance r^1/n away from the origin of the argand diagram, and these will be evenly spaced with 2pi /n radians between them. This means that you can very easily find all solutions to any root equation with only the real solution. But how can you prove that this property is true for all nth roots?

Thanks,

Brad

By Kerwin Hui (Kwkh2) on Thursday, February 1, 2001 - 02:24 pm :

I am not quite sure what you are asking for in the first part. I suppose what you want is the following. Suppose we have an equation f(z)=0, and we want to find a root, z, of that equation. If we start sufficiently near to the root, say at z₀ , then we can iterate by

z_n+1 =z_n -[f(z_n )/f'(z_n )]

You can see why this is plausible if you restrict yourself to the real case. Drawing a tangent at z₀ and find where it intersects the axis, and iterate the procedure should get you closer to the root. (The proper proof of this requires quite a bit of analysis, so is omitted bere.)

So, supposing that we want to find solutions to

f(z)=z^p -1=0

We work out f'(z)=p z^p-1 and so subsituting into the formula we get

z_n+1 =z_n -[z_n ^p -1]/[p z_n ^p-1 ]

which is what you have in the formula after a bit of rearranging.

The picture you get is probably produced by setting z₀ according to which pixel it is refered to, and the colour depends either on the number of iteration before finally it converges to a root, or on which root we converge to.

The second question is a lot easier to answer. We can write 1 as exp(2kpi i), where k is any integer, so we have

zⁿ = r exp(2kpi i)

and taking nth root of both side gives

z = r^1/n exp(2kpi i/n)

and this gives the justification for your statement. This is a corollary of De Moivre's Theorem.

Kerwin