牛顿分形

牛顿分形（）是将牛顿法应用于一给定多项式或超越函数而得到的复平面上的一个边界集。它是由牛顿法所定义的亚纯函数的朱利亚集。当不存在吸引循环（阶数大于1）时，它将复平面划分为不同的区域，每个区域与多项式的根相关联，其中。此时牛顿分形类似于曼德博集合，并且与其他分形一样，它将简单的数学描述变成了非常繁复的图像。从数值分析的角度而言，牛顿分形表现出牛顿法在二次收敛区域之外对于初始点的选择非常敏感。

将复平面上的某一点作为牛顿法迭代的初始点，可以通过迭代得到一个点序列。如果这一序列收敛于根，则将划入区域。如此便能将复平面上的这一点与多项式的某一个根相对应。不过值得注意的是，对于二次以上的多项式，都存在一些点会使得牛顿迭代无法收敛到任何根上，例如不同根的吸引域的边界。甚至存在一些多项式，某些开集中的任意初始点都无法收敛到任何根上。一个简单的例子是，某些点会被吸引到循环0、1、0、1……中，而不被任何根所吸引。

如果以一个开集中的任意点为初始点，迭代最终都收敛于某一根或循环，则该集合是这一牛顿迭代的法图集。一个法图集对应于一个根或循环。所有这些法图集的并集与朱利亚集为互补集。这一朱利亚集即是法图集的共同边界。因此，朱利亚集中的每个点都是每个法图集的一个聚点。正是由于这一性质导致了朱利亚集的分形结构（当多项式的次数大于2时）。

为了绘制一个牛顿分形图像，可以首先选择指定数量的复点并计算多项式的系数

  .

于是，对于复平面上的一个矩形网格



找到每个点对应的根的编号，并通过为每一点分配一个颜色来填充这一网格。另外，颜色可以取决于距离。对于某一固定的小，距离可以定义为第一个使得成立的值。

 牛顿分形的推广 
牛顿迭代的一种推广可表示为


其中是任意复数。当时即对应于牛顿分形。当位于以1为圆心、半径为1的圆盘以内时，该映射的不动点是稳定的。而当位于这个圆盘之外时，不动点是局部不稳定的，不过该映射仍能表现出朱利亚集的分形结构。如果是次多项式，则当是位于以为圆心、半径为的圆盘内时，序列是有界的。

更一般地，牛顿分形是朱利亚集的一个特例。

 新星分形 
新星分形（Nova fractal）是由Paul Derbyshire于1990年代发明的一种分形。它也是牛顿分形的一种推广，即在每一步迭代时都增加了一个值： 



新星分形的“朱利亚”版本令为常数，并将像素坐标设为初始值。而新星分形的“曼德博”版本则用像素坐标来初始化，并将设置为一临界点，满足



例如，的临界点位于处。

 实现 
为了用计算机实现牛顿分形，需要有一个起始函数及其导函数：



该函数的三个根是



该函数可以以伪代码表示如下：
//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
}

 参考文献 

Category:分形
Category:数值分析