Φράκταλ του Νεύτωνα

Το φράκταλ του Νεύτωνα προς $p(z)=\!\,z^{3}-1$

Το φράκταλ του Νεύτωνα σε μια μη σταθερή μερομορφική συνάρτηση $p$ που απεικονίζει τους μιγαδικούς αριθμούς στον εαυτό της είναι ένα υποσύνολο του συνόλου των μιγαδικών αριθμών. Για την ακρίβεια, είναι το σύνολο Julia ${\mathcal {J}}_{f}$ στη συνάρτηση

$f\colon z\mapsto f(z)=z-{\frac {p(z)}{p'(z)}},$

η οποία περιγράφει την μέθοδο Νεύτωνα για την εύρεση των μηδενικών της συνάρτησης $p$. Η ίδια η μέθοδος Νεύτωνα κατασκευάζει μια ακολουθία από μια αρχική τιμή $z_{0}$ με τον κανόνα αναδρομής $z_{k+1}=f(z_{k})$. Ανάλογα με την αρχική τιμή $z=z_{0}$, η τροχιά του $z$ μπορεί να είναι

$z,\;f(z),\;f^{2}(z),\;f^{3}(z),\,\ldots$

παρουσιάζουν αρκετά διαφορετική συμπεριφορά.

Σημείωση: Εδώ ο εκθέτης αναφέρεται στην $f$ ως συνάρτηση και όχι στην τιμή της συνάρτησης. $f^{\,n}$ σημαίνει έτσι την $n$-πλάσια επαναληπτική εφαρμογή της $f$ στο $z$ (ή την n n-οστή επαναληπτική της $f$), τυπικά λοιπόν $f^{\,0}(z)=z,\,f^{\,n+1}(z)=f(f^{\,n}(z))$.

Για τη δυναμική σε ένα περιβάλλον $z$ υπάρχουν ακριβώς δύο δυνατότητες:

1. υπάρχει μια γειτονιά του $z$ τέτοια ώστε η ακολουθία των αποστάσεων $\|z-w\|,\;\|f(z)-f(w)\|,\;\|f^{2}(z)-f^{2}(w)\|,\,\ldots$ είναι περιορισμένη, ή
2. για οποιαδήποτε (έστω και μικρή) γειτονιά $U$ του $z$, οι εικόνες επικαλύπτονται $U,\;f(U),\;f^{2}(U),\;f^{3}(U),\,\ldots$ ολόκληρο το μιγαδικό επίπεδο συμπεριλαμβανομένου του σημείου άπειρο (δηλαδή ολόκληρη η σφαίρα αριθμών Ρίμαν).

Τα σημεία στην πρώτη περίπτωση σχηματίζουν το σύνολο Φατού ${\mathcal {F}}_{f}$ του $f$, τα σημεία στη δεύτερη περίπτωση το σύνολο Julia ${\mathcal {J}}_{f}$. Ειδικότερα, στο σύνολο Φατού μπορεί να τύχει η ακολουθία των αποστάσεων να συγκλίνει στο μηδέν, οπότε οι τροχιές των σημείων $w$ προσεγγίζουν την τροχιά του $z$. Αν το $p$ έχει τουλάχιστον τρία μηδενικά, το σύνολο Julia ${\mathcal {J}}_{f}$ είναι πάντα ένα "Φράκταλ", επομένως το ${\mathcal {J}}_{f}$ μερικές φορές ονομάζεται και "φράκταλ του Νεύτωνα του $p$".

Σημασία για τη μέθοδο Νεύτωνα

Αν η αρχική τιμή της επανάληψης Νεύτωνα είναι κοντά σε ένα μοναδικό μηδέν του $p$, τότε η μέθοδος συγκλίνει τετραγωνικά προς αυτό το μηδέν (δηλαδή, ο αριθμός των σωστών δεκαδικών ψηφίων διπλασιάζεται μακροπρόθεσμα σε κάθε βήμα). Στην περίπτωση ενός πολλαπλού μηδενός, η μέθοδος Νεύτωνα εξακολουθεί να συγκλίνει γραμμικά. Τα μηδενικά βρίσκονται πάντα στο σύνολο Φατού.

Ωστόσο, όσο πιο κοντά είναι η αρχική τιμή στο σύνολο Julia, τόσο πιο μη διαχειρίσιμο είναι το αποτέλεσμα της μεθόδου Νεύτωνα:

• Ακόμη και αρχικές τιμές που απέχουν πολύ από ένα μηδέν μπορούν να συγκλίνουν προς αυτό, ακόμη και αν άλλα μηδενικά είναι πολύ πιο κοντά στην αρχική τιμή (στην περίπτωση 1).
• Υπάρχουν αρχικές τιμές που δεν συγκλίνουν στο μηδέν, αλλά μόνο σε έναν περιοδικό κύκλο (στην περίπτωση 1). Ένα τέτοιο παράδειγμα είναι το πολυώνυμο $z^{3}-2z+2$. Εδώ υπάρχουν αρχικές τιμές που συλλαμβάνονται από τον ελκτικό κύκλο {0,1}, έτσι ώστε ολόκληρες περιοχές στο επίπεδο δεν συγκλίνουν προς κάποιο μηδέν.
• Αν η αρχική τιμή βρίσκεται στο ίδιο το σύνολο Julia, τότε δεν συγκλίνει στο μηδέν (στην περίπτωση 2).

Παραδόξως, το σύνολο Julia (το φράκταλ του Νεύτωνα) μπορεί επίσης να έχει θετική μέτρηση στο σχέδιο: αυτό σημαίνει ότι οι τυχαίες αρχικές τιμές βρίσκονται στο σύνολο Julia και επομένως δεν συγκλίνουν προς ένα μηδέν (ή έναν άλλο ελκτικό κύκλο του $f$) (αυτή η συμπεριφορά εμφανίζεται μόνο σε λίγες περιπτώσεις και επίσης αποδείχθηκε μόλις πριν από λίγα χρόνια, αλλά είναι αρκετά πιθανή). Έτσι, ακόμη και αν το φράκταλ του Νεύτωνα είναι ένα μηδενικό σύνολο, μπορεί να υπάρχουν ολόκληρα πεδία στα οποία η μέθοδος δεν συγκλίνει σε ένα μηδενικό.

Η εν λόγω δήλωση ισχύει επίσης για τις ορθολογικές συναρτήσεις πραγματικών τιμών. Και πάλι, το πολυώνυμο $z^{3}-2z+2$ χρησιμεύει ως παράδειγμα. Επειδή έχει πραγματικούς συντελεστές, οι τιμές επανάληψης του Νεύτωνα για πραγματικές αρχικές τιμές παραμένουν πραγματικής αξίας. Καθώς ο πραγματικός άξονας διέρχεται από περιοχές μη σύγκλισης, υπάρχουν διαστήματα για τα οποία δεν υπάρχει σύγκλιση. Υπάρχει άπειρος αριθμός τέτοιων διαστημάτων.

• 
  p(z) = z³ - 1, a=1
• 
  p(z) = z³ - 1, a=2
• 
  p(z) = z⁴ - 1, a=1
• 
  p(z) = z⁴ - 1, a=2
• 
  p(z) = z⁵ - 1, a=1
• 
  p(z) = z⁵ - 1, a=2
• 
  p(z) = z⁶ - 1, a=1
• 
  p(z) = z⁷ - 1, a=1
• 
  p(z) = z⁸ - 1, a=1
• 
  p(z) = z¹⁰ - 1, a=1

Παράδειγμα φράκταλ

Παράδειγμα 1

Figure 1: Newton fractal to $z^{3}-2z+2$

Στο Σχήμα 1 παρουσιάζεται το φράκταλ Νεύτωνα (με λευκό χρώμα) στο $z^{3}-2z+2$, με χρωματική κωδικοποίηση ανάλογα με το ρυθμό σύγκλισης και τα τρία μηδενικά. Οι αρχικές τιμές που βρίσκονται στις περιοχές που έχουν σχεδιαστεί με μπεζ χρώμα συγκλίνουν στο ίδιο μηδέν (σε ανοιχτό μπεζ χρώμα στην εικόνα στα αριστερά), κατ' αναλογία για τις πράσινες και μπλε περιοχές. Τα μηδενικά για τις πράσινες και τις μπλε περιοχές βρίσκονται συμμετρικά προς τον οριζόντιο άξονα συμμετρίας στα δεξιά της εικόνας. Όσο πιο γρήγορα συγκλίνει μια αρχική τιμή στο μηδέν της, τόσο πιο ανοιχτόχρωμη είναι. Οι τιμές στις άπειρες κόκκινες περιοχές δεν συγκλίνουν στο μηδέν, αλλά συλλαμβάνονται από τον ελκυστικό κύκλος $\{0,1\}$. Το φράκταλ του Νεύτωνα - αναγνωρίσιμο στην εικόνα ως φωτεινή δομή - δεν είναι οριοθετημένο. Στις τρεις κατευθύνσεις που μπορούν να αναγνωριστούν, εκτείνεται στο ∞.

Εικόνα 2: Newton fractal σε πολυώνυμο με 7 τυχαία επιλεγμένα μηδενικά

Παράδειγμα 2

Στο Σχήμα 2 παρουσιάζεται το φράκταλ του Νεύτωνα σε ένα πολυώνυμο με 7 τυχαία επιλεγμένα μηδενικά (λευκές κουκκίδες), το εύρος αντιπροσωπεύει $-1<\operatorname {Re} (z),\operatorname {Im} (z)<1$. Παραδείγματος χάριν, το ίδιο το φράκταλ, η ακμή της κίτρινης περιοχής. Ομοίως, είναι η ακμή της πράσινης περιοχής, η ακμή της τυρκουάζ περιοχής, κ.λπ. Αυτή η ιδιότητα είναι κοινή για όλα τα σύνολα Julia. (Τα χρώματα κόκκινο και ροζ χρησιμοποιήθηκαν δύο φορές- παρ' όλα αυτά, τα όρια της κόκκινης και της ροζ περιοχής, αντίστοιχα, αντιστοιχούν επίσης στο φράκταλ του Νεύτωνα).

Γενίκευση των φράκταλ του Νεύτωνα

Άλλα φράκταλ όπου πολλαπλασιάζονται δυναμικές και τριγωνομετρικές συναρτήσεις. p(z) = zⁿ*Sin(z) - 1

• 
  p(z) = z²*Sin(Z) - 1, a=1
• 
  p(z) = z²*Sin(Z) - 1, a=1 (zoom)
• 
  p(z) = z³*Sin(Z) - 1, a=1
• 
  p(z) = z⁴*Sin(Z) - 1, a=1
• 
  p(z) = z⁴*Sin(Z) - 1, a=1 (zoom)
• 
  p(z) = z⁵*Sin(Z) - 1, a=1
• 
  p(z) = z⁶*Sin(Z) - 1, a=1
• 
  p(z) = z⁶*Sin(Z) - 1, a=1 (zoom)

Φράκταλ Nova

Το φράκταλ Nova εφευρέθηκε στα μέσα της δεκαετίας του 1990 από τον Πολ Ντέρμπισαϊρ, είναι μια γενίκευση του φράκταλ του Νεύτωνα με την προσθήκη μιας τιμής c σε κάθε βήμα:

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

Η παραλλαγή "Julia" του φράκταλ Nova διατηρεί το c σταθερό σε όλη την εικόνα και αρχικοποιεί το z₀ στις συντεταγμένες των εικονοστοιχείων. Η παραλλαγή "'Μάντελμπροτ" του φράκταλ Nova αρχικοποιεί το c στις συντεταγμένες εικονοστοιχείου και θέτει το z₀ σε ένα κρίσιμο σημείο, όπου

${\frac {\partial }{\partial z}}G(a,c,z)=0.$

Συνήθως χρησιμοποιούμενα πολυώνυμα όπως p(z) = z³ − 1 ή p(z) = (z − 1)³ οδηγούν σε κρίσιμο σημείο στο z = 1.

• 
  Κινούμενο φράκταλ "Julia" Nova για p(z) = z³ − 1 με c για τη μετάβαση από −1 to 1, χρωματισμένο από τη ρίζα που έχει επιτευχθεί.
• 
  Κινούμενο φράκταλ "Julia" Nova για p(z) = z³ − 1 με c = 1/2e^iφ και φ για τη μετάβαση από 0 to 2π, χρωματισμένο από τη ρίζα που έχει επιτευχθεί.

Εφαρμογή

Για να υλοποιηθεί το φράκταλ του Νεύτωνα, είναι απαραίτητο να υπάρχει μια αρχική συνάρτηση καθώς και η παράγωγη συνάρτηση της:

${\begin{aligned}f(z)&=z^{3}-1\\\ f'(z)&=3z^{2}\end{aligned}}$

Οι τρεις ρίζες της συνάρτησης είναι

$z=1,\ -{\tfrac {1}{2}}+{\tfrac {\sqrt {3}}{2}}i,\ -{\tfrac {1}{2}}-{\tfrac {\sqrt {3}}{2}}i$

Οι παραπάνω συναρτήσεις μπορούν να μεταφραστούν σε ψευδοκώδικα ως εξής:

//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
}

Τώρα είναι απλώς θέμα εφαρμογής της μεθόδου Νεύτωνα χρησιμοποιώντας τις δεδομένες συναρτήσεις.

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 (-2, 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
}

Δείτε επίσης

• Σύνολο Μάντελμπροτ
• Σύνολο Julia
• Οικοδομήσιμο Σύμπαν