1
$\begingroup$

I'm working on a program that draws Newton's fractal for a given polynomial. Newton's fractal is a fractal derived from Newton's root-finding method, which given some initial guess $x_0$ and function $f(x)$, the sequence

$\begin{align*}x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}\end{align*}$

will usually converge to some root of $f$. This usually works fairly well for real numbers, but over the complex numbers it breaks, and for certain initial guesses it takes longer than average to converge or never converges. Newton's fractal is what you get when you color each initial point by which root or zero it's closest to. I wrote a simple algorithm in GLSL (pretty much C but allowing programs to run on the GPU) to draw it:

  • Take $x_0$ to be the coordinates of the current pixel.
  • Apply the Newton iteration some set number of times $N$, while storing the previous iterate.
  • If $\left | x_{n+1} - x_n \right | \leq \varepsilon$ for some small $\varepsilon$ during the iteration, break. This means the point has converged.
  • Take the final value $x_N$, and calculate its argument. In GLSL this is implemented using the function atan(y,x) which returns a value between $-\pi$ and $\pi$.
  • The argument is fed into a color ramp function. The brightness is based on the number of iterations until convergence.

The issue I'm having is with oscillations. When I try to plot the fractal for $f(z)=z^4 - 1$, one of the colors oscillates back and forth between two values. Choosing sufficiently small $\varepsilon$ does work here, but for some other polynomials like $f(z)=z^8 - 15z^4 + 16$ it does not. I'm planning on making my program draw the fractal for a user-inputted polynomial, so is there some way to fix (or at least reduce) this problem for all inputs?

Here is my code: https://www.shadertoy.com/view/DdcXDr

I've tried my best to comment it all out so it's clear what each part does.

$\endgroup$
3
  • $\begingroup$ Is this oscillation remaining the same whatever the chosen definition (in the sense of pixel size) ? $\endgroup$
    – Jean Marie
    Mar 23, 2023 at 23:17
  • $\begingroup$ Yes, it seems to be. $\endgroup$
    – zenzicubic
    Mar 23, 2023 at 23:22
  • $\begingroup$ Well, obviously, some points never converge to a root, but instead are stuck in a cycle. Those fractals of yours are made of these very points. You need some criteria to detect cycles. $\endgroup$ Mar 24, 2023 at 0:24

1 Answer 1

0
$\begingroup$

It seems that for the sequences that converge to -1, some are terminated at the argument just below $\pi$ while others are terminated at the argument just above $-\pi$. It wouldn't be a problem if the variable t wasn't multiplied by $2\pi$ when you use it to set col, which appears to be your plan, but currently it is multiplied.

$\endgroup$
4
  • $\begingroup$ indeed, #define TAU (2. * PI) (add brackets so that division works as expected) and float t = atan(z.y, z.x) / TAU; (divide by $2\pi$, it will be remultiplied later) gives a much more reasonable image $\endgroup$
    – Claude
    Mar 24, 2023 at 14:52
  • $\begingroup$ Yes, that ended up fixing it. $\endgroup$
    – zenzicubic
    Mar 25, 2023 at 2:09
  • $\begingroup$ @zenzicubic No, it is simply not the case that you can classify the limit by argument alone - whether it works for some particular example or not. $\endgroup$ Mar 25, 2023 at 3:07
  • $\begingroup$ That works for simple polynomials though, and that's all that I care about. $\endgroup$
    – zenzicubic
    Mar 25, 2023 at 16:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .