פרקטל ניוטון

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

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

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

ג'וליה קבעה את הפונקציה הרציונלית הקשורה לשיטת ניוטון עבור תבנית:נוסחה .

פרקטל ניוטון הוא קבוצת גבול במישור המורכב המאופיין בשיטת ניוטון המיושמת על פולינום קבוע תבנית:נוסחה או פונקציה טרנסנדנטלית. זוהי קבוצת ז'וליה של הפונקציה המרומורפית תבנית:נוסחה.

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

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

כדי לשרטט תמונות של הפרקטל, אפשר לבחור תחילה מספר תבנית:Mvar מסוים של נקודות מורכבות תבנית:נוסחה ולחשב את המקדמים תבנית:נוסחה של הפולינום.

$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\mathrm{\Delta }x+in\mathrm{\Delta }y;m=0,\dots ,M-1;n=0,\dots ,N-1$

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

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

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

$z_{n+1}=z_n-a\frac{p(z_n)}{p^{\prime }(z_n)}$

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

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

נובה פרקטל

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

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

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

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

פולינומים נפוצים כמו תבנית:נוסחה או תבנית:נוסחה מובילים לנקודה קריטית ב- תבנית:נוסחה.

יישום

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

$\begin{array}{cc}f(z)& =z^3-1\\ f^{\prime }(z)& =3z^2\end{array}$

שלושת השורשים של הפונקציה הם:

$z=1,-\frac{1}{2}+\frac{\sqrt{3}}{2}i,-\frac{1}{2}-\frac{\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, יחד עם הדגמה אינטראקטיבית של הפרקטל באתר שלו, וקוד המקור להדגמה