Newton fractal - Newton fractal

Julia a stabilit funcția rațională asociată metodei lui Newton pentru .

{\ displaystyle f (z) = z ^ {3} -1}

Newton fractal este un set de delimitare în planul complex care se caracterizează prin metoda lui Newton aplicată la un fix polinomială sau funcția transcendentală . Este setul Julia a funcției meromorfe , care este dată de metoda lui Newton. Când nu există cicluri atractive (de ordin mai mare de 1), acesta împarte planul complex în regiuni , fiecare dintre acestea fiind asociată cu o rădăcină a polinomului ,. În acest fel, fractala Newton este similară cu setul Mandelbrot și, ca și alte fractale, prezintă un aspect complicat care rezultă dintr-o descriere simplă. Este relevantă pentru analiza numerică, deoarece arată că (în afara regiunii convergenței pătratice ) metoda Newton poate fi foarte sensibilă la alegerea punctului său de pornire. ${\ displaystyle p (Z) \ in \ mathbb {C} [Z]}$ ${\ displaystyle z \ mapsto z - {\ tfrac {p (z)} {p '(z)}}}$ ${\ displaystyle G_ {k}}$ ${\ displaystyle \ zeta _ {k}}$ ${\ displaystyle k = 1, \ ldots, \ deg (p)}$

Multe puncte ale planului complex sunt asociate cu una dintre rădăcinile polinomului în felul următor: punctul este folosit ca valoare de pornire pentru iterația lui Newton , rezultând o secvență de puncte Dacă secvența converge la rădăcină , atunci a fost un element al regiunea . Cu toate acestea, pentru fiecare polinom de grad cel puțin 2 există puncte pentru care iterația Newton nu converge la nicio rădăcină: exemplele sunt limitele bazinelor de atracție ale diferitelor rădăcini. Există chiar polinoame pentru care seturile deschise de puncte de pornire nu reușesc să convergă la orice rădăcină: un exemplu simplu este , în care unele puncte sunt atrase de ciclul 0, 1, 0, 1 ... mai degrabă decât de o rădăcină. ${\ displaystyle \ deg (p)}$ ${\ displaystyle z_ {0}}$ ${\ displaystyle z_ {n + 1}: = z_ {n} - {\ frac {p (z_ {n})} {p '(z_ {n})}}}$ ${\ displaystyle z_ {1}, z_ {2}, \ ldots,}$ ${\ displaystyle \ zeta _ {k}}$ ${\ displaystyle z_ {0}}$ ${\ displaystyle G_ {k}}$ ${\ displaystyle z ^ {3} -2z + 2}$

Un set deschis pentru care iterațiile converg către o anumită rădăcină sau ciclu (care nu este un punct fix), este un set Fatou pentru iterație. Setul complementar la unirea tuturor acestora este setul Julia. Mulțimile Fatou au graniță comună, și anume mulțimea Julia. Prin urmare, fiecare punct al mulțimii Julia este un punct de acumulare pentru fiecare dintre mulțimile Fatou. Această proprietate este cea care determină structura fractală a mulțimii Julia (când gradul polinomului este mai mare de 2).

Pentru a trasa imagini interesante, se poate alege mai întâi un număr specificat de puncte complexe și să se calculeze coeficienții polinomului ${\ displaystyle d}$ ${\ displaystyle (\ zeta _ {1}, \ ldots, \ zeta _ {d})}$ ${\ displaystyle (p_ {1}, \ ldots, p_ {d})}$

{\ displaystyle 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})}

.

Apoi , pentru un grilaj dreptunghiular , , de puncte în , o găsește indicele rădăcinii corespunzătoare și o utilizează pentru a umple un x grila raster atribuind fiecărui punct o culoare . În plus sau alternativ, culorile pot depinde de distanță , care este definită ca fiind prima valoare astfel încât pentru unele mici fixate anterior . ${\ displaystyle z_ {mn} = z_ {00} + m \, \ Delta x + în \, \ Delta y}$ ${\ displaystyle m = 0, \ ldots, M-1}$ ${\ displaystyle n = 0, \ ldots, N-1}$ ${\ displaystyle \ mathbb {C}}$ ${\ displaystyle k (m, n)}$ ${\ displaystyle \ zeta _ {k (m, n)}}$ ${\ displaystyle M}$ ${\ displaystyle N}$ ${\ displaystyle (m, n)}$ ${\ displaystyle f_ {k (m, n)}}$ ${\ displaystyle D (m, n)}$ ${\ displaystyle D}$ ${\ displaystyle | z_ {D} - \ zeta _ {k (m, n)} | <\ epsilon}$ ${\ displaystyle \ epsilon> 0}$

Generalizarea fractalelor Newton

O generalizare a iterației lui Newton este

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

unde este orice număr complex. Alegerea specială corespunde fractalului Newton. Punctele fixe ale acestei hărți sunt stabile atunci când se află în interiorul discului de rază 1 centrat la 1. Când se află în afara acestui disc, punctele fixe sunt instabile la nivel local, totuși harta prezintă încă o structură fractală în sensul mulțimii Julia . Dacă este un polinom de grad , atunci secvența este delimitată cu condiția să se afle în interiorul unui disc de rază centrat la . ${\ displaystyle a}$ ${\ displaystyle a = 1}$ ${\ displaystyle a}$ ${\ displaystyle a}$ ${\ displaystyle p}$ ${\ displaystyle d}$ ${\ displaystyle z_ {n}}$ ${\ displaystyle a}$ ${\ displaystyle d}$ ${\ displaystyle d}$

Mai general, fractala lui Newton este un caz special al unui set Julia .

Fractal Newton pentru trei rădăcini de gradul 3 ( ), colorat după numărul de iterații necesare ${\ displaystyle p (z) = z ^ {3} -1}$
Fractal Newton pentru trei rădăcini de gradul 3 ( ), colorat după rădăcină atinsă ${\ displaystyle p (z) = z ^ {3} -1}$
Newton fractal pt . Punctele din bazinele roșii nu ajung la o rădăcină. ${\ displaystyle p (z) = z ^ {3} -2z + 2}$
Fractal Newton pentru un polinom de ordinul 7, colorat de rădăcina atinsă și umbrită de rata convergenței.
Newton fractal pt ${\ displaystyle x ^ {8} + 15x ^ {4} -16}$
Fractal Newton pentru , colorat după rădăcină atins, umbrit după numărul de iterații necesare. ${\ displaystyle p (z) = z ^ {5} -3iz ^ {3} - (5 + 2i) z ^ {2} + 3z + 1}$ ${\ displaystyle - (5 + 2i) z ^ {2} + 3z + 1}$
Fractal Newton pentru , colorat după rădăcină atins, umbrit după numărul de iterații necesare ${\ displaystyle p (z) = \ sin (z)}$
Un alt fractal Newton pentru ${\ displaystyle \ sin (x)}$
Fractal Newton generalizat pentru , Culoarea a fost aleasă pe baza argumentului după 40 de iterații. ${\ displaystyle p (z) = z ^ {3} -1}$ ${\ displaystyle a = -0.5.}$
Fractal Newton generalizat pentru , ${\ displaystyle p (z) = z ^ {2} -1}$ ${\ displaystyle a = 1 + i.}$
Fractal Newton generalizat pentru , ${\ displaystyle p (z) = z ^ {3} -1}$ ${\ displaystyle a = 2.}$
Fractal Newton generalizat pentru , ${\ displaystyle p (z) = z ^ {4 + 3i} -1}$ ${\ displaystyle a = 2.1.}$
${\ displaystyle p (z) = z ^ {6} + z ^ {3} -1}$
${\ displaystyle p (z) = \ sin (z) -1}$
${\ displaystyle p (z) = \ cosh (z) -1}$

Nova fractală

Fractala Nova inventată la mijlocul anilor 1990 de Paul Derbyshire este o generalizare a fractalei Newton cu adăugarea unei valori la fiecare pas: ${\ displaystyle c}$

{\ displaystyle z_ {n + 1} = z_ {n} -a {\ frac {p (z_ {n})} {p '(z_ {n})}} + c = G (a, c, z) }

Varianta „Julia” a fractalei Nova se menține constantă peste imagine și se inițializează la coordonatele pixelilor. Varianta „Mandelbrot” a fractalei Nova inițializează la coordonatele pixelilor și se setează într-un punct critic, unde . Polinoamele utilizate frecvent ca sau duc la un punct critic la . ${\ displaystyle c}$ ${\ displaystyle z_ {0}}$ ${\ displaystyle c}$ ${\ displaystyle z_ {0}}$ ${\ displaystyle {\ frac {\ partial} {\ partial z}} G (a, c, z) = 0}$ ${\ displaystyle p (z) = z ^ {3} -1}$ ${\ displaystyle p (z) = (z-1) ^ {3}}$ ${\ displaystyle z = 1}$

Fractală animată "Julia" nova pentru cu c mergând de la -1 la 1, colorată de rădăcină atinsă. ${\ displaystyle p (z) = z ^ {3} -1}$
Fractală animată "Julia" nova pentru cu și φ mergând de la 0 la 2π, colorată de rădăcină atinsă. ${\ displaystyle p (z) = z ^ {3} -1}$ ${\ displaystyle c = 0.5e ^ {i \ phi}}$

Implementare

Pentru a implementa Newton Fractal, este necesar să aveți o funcție de pornire, precum și funcția sa derivată:

{\ displaystyle f (z) = z ^ {3} -1}

{\ displaystyle f '(z) = 3z ^ {2}}

Rădăcinile funcției sunt

{\ displaystyle z = 1, -0,5 \ pm {\ sqrt {3}} / 2i}

Funcțiile definite mai sus pot fi traduse în pseudocod după cum urmează:

//z^3-1 
float2 Function (float2 z)
{
	return cpow(z, 3) - float2(1, 0); //cpow is an exponential function for complex numbers
}

//3*z^2
float2 Derivative (float2 z)
{
	return 3 * cmul(z, z); //cmul is a function that handles multiplication of complex numbers
}

Acum este doar o chestiune de implementare a metodei Newton folosind funcțiile date.

float2 roots[3] = //Roots (solutions) of the polynomial
{
	float2(1, 0), 
	float2(-.5, sqrt(3)/2), 
	float2(-.5, -sqrt(3)/2)
};
	
color colors[3] =  //Assign a color for each root
{
    red,
    green,
    blue
}

For each pixel (x, y) on the target, do:
{
	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 is originally set to the pixel coordinates

	for (int iteration = 0;
	     iteration < maxIteration;
	     iteration++;)
	{
		z -= cdiv(Function(z), Derivative(z)); //cdiv is a function for dividing complex numbers

        float tolerance = 0.000001;
        
		for (int i = 0; i < roots.Length; i++)
		{
		    float2 difference = z - roots[i];
		    
			//If the current iteration is close enough to a root, color the pixel.
			if (abs(difference.x) < tolerance && abs (difference.y) < tolerance)
			{
				return colors[i]; //Return the color corresponding to the root
			}
		}
		
    }
    
    return black; //If no solution is found
}

Vezi si

Referințe

Lecturi suplimentare

JH Hubbard, D. Schleicher, S. Sutherland : How to Find All Roots of Complex Polynomials by Newton's Method , Inventiones Mathematicae vol. 146 (2001) - cu o discuție asupra structurii globale a fractalelor Newton
Despre numărul de iterații pentru metoda lui Newton de Dierk Schleicher 21 iulie 2000
Metoda lui Newton ca sistem dinamic de Johannes Rueckert

Languages

In other projects