牛顿分形

牛顿分形（英语：Newton fractal）是将牛顿法应用于一给定多项式 $p (Z) \in ℂ[Z]$ 或超越函数而得到的复平面上的一个边界集。它是由牛顿法所定义的亚纯函数 $z ↦ z − .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}p(z)/p′(z)$ 的朱利亚集。当不存在吸引循环（阶数大于1）时，它将复平面划分为不同的区域 $G k$ ，每个区域与多项式的根 $ζ k$ 相关联，其中 $k = 1, \dots, deg(p)$ 。此时牛顿分形类似于曼德博集合，并且与其他分形一样，它将简单的数学描述变成了非常繁复的图像。从数值分析的角度而言，牛顿分形表现出牛顿法在二次收敛区域之外对于初始点的选择非常敏感。

f (z) = z 3 - 1

的牛顿分形

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

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

为了绘制一个牛顿分形图像，可以首先选择指定数量 $d$ 的复点 $(ζ 1, \dots, ζ d)$ 并计算多项式的系数 $(p 1, \dots, 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 \times 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$ 是任意复数。^[1]当 $a = 1$ 时即对应于牛顿分形。当 $a$ 位于以1为圆心、半径为1的圆盘以内时，该映射的不动点是稳定的。而当 $a$ 位于这个圆盘之外时，不动点是局部不稳定的，不过该映射仍能表现出朱利亚集的分形结构。如果 $p$ 是 $d$ 次多项式，则当是 $a$ 位于以 $d$ 为圆心、半径为 $d$ 的圆盘内时，序列 $z n$ 是有界的。

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

$p (z) = z 3 - 1$ 的牛顿分形，颜色表示需要的迭代步数
$p (z) = z 3 - 1$ 的牛顿分形，颜色表示最终收敛到的根
$p (z) = z 3 - 2 z + 2$ 的牛顿分形，红色区域中的点不收敛到任何根
一个7次多项式的牛顿分形，颜色表示最终收敛到的根，深浅表示收敛速度
$p (z) = z 8 + 15 z 4 - 16$ 的牛顿分形
$p (z) = z 5 - 3 iz 3 - (5 + 2 i) z 2 + 3 z + 1$ 的牛顿分形，颜色表示最终收敛到的根，深浅表示迭代步数
$p (z) = sin z$ 的牛顿分形，颜色表示最终收敛到的根，深浅表示迭代步数
$p (z) = sin z$ 的牛顿分形
$p (z) = z 3 - 1$ 的广义牛顿分形（ $a = - 1 / 2$ ）
$p (z) = z 2 - 1$ 的广义牛顿分形（ $a = 1 + i$ ）
$p (z) = z 3 - 1$ 的广义牛顿分形（ $a = 2$ ）
$p (z) = z 4 + 3 i - 1$ 的广义牛顿分形（ $a = 2.1$ ）
$p (z) = z 6 + z 3 - 1$ 的牛顿分形
$p (z) = sin z - 1$ 的牛顿分形
$p (z) = cosh z - 1$ 的牛顿分形

新星分形

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

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

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

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

例如， $p (z) = (z - 1) 3$ 的临界点位于 $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
}

参考文献

^ Simon Tatham. Fractals derived from Newton–Raphson. [2022-06-05]. （原始内容存档于2022-06-15）.
^ Damien M. Jones. class Standard_NovaMandel (Ultra Fractal formula reference). [2022-06-05]. （原始内容存档于2018-12-15）.
^ Damien M. Jones. dmj's nova fractals 1995-6. [2022-06-05]. （原始内容存档于2017-08-20）.
^ Michael Condron. Relaxed Newton's Method and the Nova Fractal. [2022-06-05]. （原始内容存档于2022-03-28）.
^ Frederik Slijkerman. Ultra Fractal Manual: Nova (Julia, Mandelbrot). [2022-07-08]. （原始内容存档于2022-01-04）.

[1] Simon Tatham. Fractals derived from Newton–Raphson. [2022-06-05]. （原始内容存档于2022-06-15）.

[2] Damien M. Jones. class Standard_NovaMandel (Ultra Fractal formula reference). [2022-06-05]. （原始内容存档于2018-12-15）.

[3] Damien M. Jones. dmj's nova fractals 1995-6. [2022-06-05]. （原始内容存档于2017-08-20）.

[4] Michael Condron. Relaxed Newton's Method and the Nova Fractal. [2022-06-05]. （原始内容存档于2022-03-28）.

[5] Frederik Slijkerman. Ultra Fractal Manual: Nova (Julia, Mandelbrot). [2022-07-08]. （原始内容存档于2022-01-04）.

[1]

[2]

[3]

[4]

[5]