Frattale di Newton

Rappresentazione di un frattale ottenuto con il metodo 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. 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.

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.

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. 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.

Voci correlate

• Auto similarità
• Frattale
• Insieme di Julia
• Lista di frattali per dimensione di Hausdorff
• Metodo di Newton

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul frattale di Newton