牛頓分形

牛頓分形（英語：Newton fractal）是將牛頓法應用於一給定多項式p(Z) ∈ ℂ[Z]或超越函數而得到的複平面上的一個邊界集。它是由牛頓法所定義的亞純函數z ↦ z − p(z)/p′(z)的朱利亞集。當不存在吸引循環（階數大於1）時，它將複平面劃分為不同的區域G_k，每個區域與多項式的根ζ_k相關聯，其中k = 1, …, deg(p)。此時牛頓分形類似於曼德博集合，並且與其他分形一樣，它將簡單的數學描述變成了非常繁複的圖像。從數值分析的角度而言，牛頓分形表現出牛頓法在二次收斂區域之外對於初始點的選擇非常敏感。

f(z) = z³ − 1的牛頓分形

將複平面上的某一點作為牛頓法迭代z_{n + 1} := z_n − p(z_n)/p'(z_n)的初始點z₀，可以通過迭代得到一個點序列z₁, z₂, …,。如果這一序列收斂於根ζ_k，則將z₀劃入區域G_k。如此便能將複平面上的這一點與多項式的某一個根相對應。不過值得注意的是，對於二次以上的多項式，都存在一些點會使得牛頓迭代無法收斂到任何根上，例如不同根的吸引域的邊界。甚至存在一些多項式，某些開集中的任意初始點都無法收斂到任何根上。一個簡單的例子是z³ − 2z + 2，某些點會被吸引到循環0、1、0、1……中，而不被任何根所吸引。

如果以一個開集中的任意點為初始點，迭代最終都收斂於某一根或循環，則該集合是這一牛頓迭代的法圖集。一個法圖集對應於一個根或循環。所有這些法圖集的併集與朱利亞集為互補集。這一朱利亞集即是法圖集的共同邊界。因此，朱利亞集中的每個點都是每個法圖集的一個聚點。正是由於這一性質導致了朱利亞集的分形結構（當多項式的次數大於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$

找到每個點(m,n)對應的根ζ_k(m,n)的編號k(m,n)，並通過為每一點分配一個顏色f_k(m,n)來填充這一M × N網格。另外，顏色可以取決於距離D(m,n)。對於某一固定的小ε > 0，距離D可以定義為第一個使得|z_D − ζ_k(m,n)| < ε成立的D值。

牛頓分形的推廣

牛頓迭代的一種推廣可表示為

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

其中a是任意複數。當a = 1時即對應於牛頓分形。當a位於以1為圓心、半徑為1的圓盤以內時，該映射的不動點是穩定的。而當a位於這個圓盤之外時，不動點是局部不穩定的，不過該映射仍能表現出朱利亞集的分形結構。如果p是d次多項式，則當是a位於以d為圓心、半徑為d的圓盤內時，序列z_n是有界的。

更一般地，牛頓分形是朱利亞集的一個特例。

• 
  p(z) = z³ − 1的牛頓分形，顏色表示需要的迭代步數
• 
  p(z) = z³ − 1的牛頓分形，顏色表示最終收斂到的根
• 
  p(z) = z³ − 2z + 2的牛頓分形，紅色區域中的點不收斂到任何根
• 
  一個7次多項式的牛頓分形，顏色表示最終收斂到的根，深淺表示收斂速度
• 
  p(z) = z⁸ + 15z⁴ − 16的牛頓分形
• 
  p(z) = z⁵ − 3iz³ − (5 + 2i)z² + 3z + 1的牛頓分形，顏色表示最終收斂到的根，深淺表示迭代步數
• 
  p(z) = sin z的牛頓分形，顏色表示最終收斂到的根，深淺表示迭代步數
• 
  p(z) = sin z的牛頓分形
• 
  p(z) = z³ − 1的廣義牛頓分形（a = −1/2）
• 
  p(z) = z² − 1的廣義牛頓分形（a = 1 + i）
• 
  p(z) = z³ − 1的廣義牛頓分形（a = 2）
• 
  p(z) = z^{4 + 3i} − 1的廣義牛頓分形（a = 2.1）
• 
  p(z) = z⁶ + z³ − 1的牛頓分形
• 
  p(z) = sin z − 1的牛頓分形
• 
  p(z) = cosh z − 1的牛頓分形

新星分形

新星分形（Nova fractal）是由Paul Derbyshire於1990年代發明的一種分形。它也是牛頓分形的一種推廣，即在每一步迭代時都增加了一個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)³的臨界點位於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
}