Frattale di Newton

Il frattale di Newton è un insieme di frontiera nel piano complesso che è caratterizzato dal metodo di Newton applicato a un polinomio $p(Z)\in \mathbb {C} [Z]$ o funzione trascendentale. È l'insieme di Julia della funzione meromorfa

z\mapsto z-{\frac {p(z)}{p'(z)}}

che è data dal metodo di Newton . Essa, quando non ci sono cicli attrattori (di ordine superiore a 1), divide il piano complesso in regioni $G_{k}$ , ognuna delle quali è associata alla radice $\zeta _{k}$ del polinomio, $k=1,\ldots ,\deg(p)$ .

In questo modo il frattale di Newton è simile all'insieme di Mandelbrot, e come altri frattali mostra un aspetto complesso che deriva da una semplice descrizione. È rilevante per l'analisi numerica perché mostra che (al di fuori della regione di convergenza quadratica) il metodo di Newton può essere molto sensibile alla scelta del punto di partenza.^[1] Molti punti del piano complesso sono associati a una delle radici $\deg(p)$ del polinomio nel modo seguente: il punto $z_{0}$ è usato come valore iniziale e i punti successivi sono dati dal metodo di Newton:

z_{n+1}:=z_{n}-{\frac {p(z_{n})}{p'(z_{n})}}

,

che produce una successione di punti $z_{1},z_{2},\ldots$ . Se la successione converge alla radice $\zeta _{k}$ , allora $z_{0}$ era un elemento della regione $G_{k}$ . Tuttavia, per ogni polinomio di grado almeno 2 ci sono punti per i quali l'iterazione di Newton non converge a nessuna radice: gli esempi sono i confini dei bacini di attrazione delle varie radici. Esistono anche polinomi per cui gli insiemi aperti di punti di partenza non convergono in nessuna radice: un semplice esempio è $z^{3}-2z+2$ , dove alcuni punti sono attratti dal ciclo 0, 1, 0, 1 ... anziché da una radice.^[1]

Un insieme aperto per il quale le iterazioni convergono verso una data radice o un ciclo di radici (che non è un punto fisso), rappresenta un insieme di Fatou per l'iterazione. L'insieme complementare all'unione di tutti questi è l'insieme di Julia. Gli insieme di Fatou infatti hanno un confine comune, ossia l'insieme di Julia. Pertanto ogni punto dell'insieme di Julia è un punto di accumulazione per ciascuno degli insiemi di Fatou. È proprio questa proprietà che causa la struttura frattale dell'insieme di Julia (quando il grado del polinomio è maggiore di 2).

Rappresentazione

Per tracciare immagini interessanti, si può prima scegliere un numero specificato $d$ di punti del piano complesso $(\zeta _{1},\ldots ,\zeta _{d})$ e calcolare i coefficienti $(p_{1},\ldots ,p_{d})$ del polinomio

p(z)=z^{d}+p_{1}z^{d-1}+\cdots +p_{d-1}z+p_{d}:=(z-\zeta _{1})\cdot \cdots \cdot (z-\zeta _{d}).

Quindi per un reticolo rettangolare $z_{mn}=z_{00}+m\,\Delta x+in\,\Delta y$ , $m=0,\ldots ,M-1$ , $n=0,\ldots ,N-1$ di punti in $\mathbb {C}$ , si individua l'indice $k(m,n)$ della radice corrispondente $\zeta _{k(m,n)}$ e si usa per riempire la griglia raster $M$ × $N$ Assegnando ad ogni punto $(m,n)$ un colore $f_{k(m,n)}$ . In più o in alternativa i colori possono essere assegnati in funzione della distanza $D(m,n)$ , definita come primo valore $D$ cosicché $|z_{D}-\zeta _{k(m,n)}|<\epsilon$ per un preassegnato $\epsilon >0$ piccolo a piacere.^[2]

Per implementare il 'frattale di Newton' è richiesta una funzione di partenza $f(z)=z^{3}-1$ e la sua derivata:

f'(z)=3z^{2}.

Le radici della funzione sono $1$ , $-{\frac {1}{2}}+{\frac {\sqrt {3}}{2}}i$ e $-{\frac {1}{2}}-{\frac {\sqrt {3}}{2}}i$ .

le funzioni sopra definite possono essere tradotte in pseudocodice come segue:

//z^3-1 
float2 Function (float2 z)
{
	return cpow(z, 3) - float2(1, 0); //cpow è una funzione esponenziale per numeri complessi
}

//3*z^2
float2 Derivative (float2 z)
{
	return 3 * cmul(z, z); //cmul è una funzione che gestisce la moltiplicazione di numeri complessi
}

Si tratta poi di implementare il metodo di Newton usando le funzioni definite.

Per ogni pixel (x, y) sul target, fai:
{
	zx = scaled x coordinate of pixel (scaled to lie in the Mandelbrot X scale (-2.5, 1))
    zy = scaled y coordinate of pixel (scaled to lie in the Mandelbrot Y scale (-1, 1))

    float2 z = float2(zx, zy); //Z è dettato in origine sulle coordinate del pixel

	float2 roots[3] = //Radici (soluzioni) del polinomio
	{
		float2(1, 0), 
		float2(-.5, sqrt(3)/2), 
		float2(-.5, -sqrt(3)/2)
	};
	
	color colors[3] =  //assegna un colore per ogni radice
	{
	    red,
	    green,
	    blue
    }
    
    int iteration = 0;

	while (iteration < maxIteration)
	{
		z -= cdiv(Function(z), Derivative(z)); //cdiv è una funzione che gestisce la divisione di numeri complessi

        float tolerance = 0.000001;
        
		for (int i = 0; i < roots.Length; i++)
		{
		    float difference = z - roots[i];
		    
			//Se la ritorsione corrente è abbastanza vicina a una radice colora il pixel.
			if (abs(difference.x) < tolerance && abs(difference.y) < tolerance)
			{
				return colors[i]; //Invia il colore corrispondente alla radice
			}
		}
		iteration++;
    }
    
    return black; //Assegna il nero se non si ha una radice
}

Esempi

Frattale di Newton per le tre radici di terzo grado ( $p(z)=z^{3}-1$ ), i colori sono assegnati in funzione del numero di iterazioni richieste
Frattale di Newton per le tre radici di terzo grado ( $p(z)=z^{3}-1$ ), i colori sono assegnati in funzione delle radici ottenute
Frattale di Newton per $p(z)=z^{3}-2z+2$ . I punti del bacino rosso non raggiungono una soluzione definita.
Frattale di Newton per un polinomio di settimo grado, colorato secondo le radici ottenute e sfumato secondo il rateo di convergenza.
Frattale di Newton per $p(z)=z^{5}-3iz^{3}-(5+2i)z^{2}+3z+1$ , colorato secondo le radici ottenute, sfumato a seconda delle iterazioni richieste.
Frattale di Newton per $\sin(x)$
Frattale di Newton generalizzato per $p(z)=z^{4+3i}-1$ , $a=2.1.$
$p(z)=z^{6}+z^{3}-1$
$p(z)=\sin(z)-1$
$p(z)=\cosh(z)-1$

Generalizzazione

Una generalizzazione dell'iterazione di Newton è: $z_{n+1}=z_{n}-a{\frac {p(z_{n})}{p'(z_{n})}},$ dove $a$ è un numero complesso.^[3] La scelta speciale $a=1$ corrisponde al frattale di Newton. I punti fissi di questa mappa sono stabili quando $a$ giace all'interno del disco di raggio 1 centrato su 1. Quando $a$ è all'esterno di questo disco, i punti fissi sono localmente instabili, tuttavia la mappa mostra ancora una struttura frattale nel senso dell'insieme di Julia. Se $p$ è un polinomio di grado $n$ , allora la sequenza $z_{n}$ è un insieme limitato a condizione che $a$ si trovi all'interno di un disco di raggio $n$ centrato su $n$ . Più in generale, il frattale di Newton è un caso speciale di frattale di Julia.