פרקטל ניוטון

פרקטל ניוטון, רוחב 1.5.

"שש שרשראות" נובה

"מנדלברוט" פרקטל נובה

ג'וליה קבעה את הפונקציה הרציונלית הקשורה לשיטת ניוטון עבור f(z) = z³ − 1 .

פרקטל ניוטון הוא קבוצת גבול במישור המורכב המאופיין בשיטת ניוטון המיושמת על פולינום קבוע p(Z) ∈ ℂ[Z] או פונקציה טרנסנדנטלית. זוהי קבוצת ז'וליה של הפונקציה המרומורפית z ↦ z − p(z).

כמעט כל הנקודות של המישור המורכב משויכות לאחד משורשי deg(p) של פולינום נתון באופן הבא: הנקודה משמשת כערך התחלתי z₀ עבור איטרציה של ניוטון z_{n + 1} := z_n − p(z_n)

קבוצה פתוחה שעבורה האיטרציות מתכנסות לכיוון שורש או מחזור נתון (שאיננה נקודה קבועה), היא קבוצת ז'וליה עבור האיטרציה. הסט המשלים לאיחוד של כל אלה, הוא סט ג'וליה. לקבוצות הפאטו יש גבול משותף, כלומר לסט ג'וליה. לכן, כל נקודה מקבוצת ג'וליה היא נקודת צבירה עבור כל אחת מקבוצות הפאטו. תכונה זו היא שגורמת למבנה הפרקטלי של קבוצת יוליה (כאשר מידת הפולינום גדולה מ-2).

כדי לשרטט תמונות של הפרקטל, אפשר לבחור תחילה מספר d מסוים של נקודות מורכבות (ζ₁, …, ζ_d) ולחשב את המקדמים (p₁, …, p_d) של הפולינום.

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

$z_{mn}=z_{00}+m\,\Delta x+in\,\Delta y;\quad m=0,\ldots ,M-1;\quad n=0,\ldots ,N-1$

על הנקודות ב- ℂ, מוצאים את האינדקס k(m,n) של השורש המקביל ζ_k(m,n) ומשתמשים בזה כדי למלא רשת רסטר M × N על ידי הקצאת לכל נקודה (m,n) צבע f_k(m,n). בנוסף או לחלופין הצבעים עשויים להיות תלויים במרחק D(m,n), המוגדר כערך הראשון D כך ש- z_D − ζ_k(m,n) < ε עבור כמה ε > 0.

הכללה של פרקטלים של ניוטון

הכללה של האיטרציה של ניוטון היא:

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

כאשר a הוא כל מספר מרוכב הבחירה המיוחדת a = 1 מתאימה לפרקטל ניוטון. הנקודות הקבועות של מפה זו יציבות כאשר a שוכנת בתוך הדיסקה ברדיוס 1 שבמרכזה 1. כאשר a נמצא מחוץ לדיסק זה, הנקודות הקבועות אינן יציבות מקומית, אולם המפה עדיין מציגה מבנה פרקטלי במובן של קבוצת ז'וליה. אם p הוא פולינום בדרגה d, אזי הרצף z_n מוגבל בתנאי ש-a נמצא בתוך דיסק ברדיוס d שמרכזו ב-d.

באופן כללי יותר, הפרקטל של ניוטון הוא מקרה מיוחד של קבוצת ג'וליה.

נובה פרקטל

פרקטל נובה שהומצא באמצע שנות ה-90 על ידי פול דרבישייר הוא הכללה של פרקטל ניוטון בתוספת ערך c בכל שלב:

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

גרסת "ג'וליה" של פרקטל נובה שומרת על c קבוע על פני התמונה ומאתחלת את z₀ לקואורדינטות הפיקסלים, גרסת ה"מנדלברוט" של פרקטל נובה מאתחלת c לקואורדינטות הפיקסלים ומגדירה את z₀ לנקודה קריטית, כאשר

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

פולינומים נפוצים כמו p(z) = z³ − 1 או p(z) = (z − 1)³ מובילים לנקודה קריטית ב- z = 1.

יישום

כדי ליישם את פרקטל ניוטון, יש צורך בפונקציית התחלה וכן פונקציית הנגזרת שלה:

${\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
}

ראו גם

• קבוצת ז'וליה
• קבוצת מנדלברוט

קישורים חיצוניים

מדיה וקבצים בנושא פרקטל ניוטון בוויקישיתוף

• JH Hubbard, D. Schleicher, S. Sutherland : כיצד למצוא את כל השורשים של פולינומים מורכבים בשיטת ניוטון, Inventiones Mathematicae vol. 146 (2001) - עם דיון במבנה הגלובלי של פרקטלי ניוטון
• על מספר האיטרציות לשיטת ניוטון מאת דירק שלייכר 21 ביולי 2000
• שיטת ניוטון כמערכת דינמית מאת יוהנס רוקרט
• Newton's Fractal (שניוטון לא ידע עליו כלום) מאת 3Blue1Brown, יחד עם הדגמה אינטראקטיבית של הפרקטל באתר שלו, וקוד המקור להדגמה