查看“︁牛顿分形”︁的源代码

{{NoteTA
|G1=Math
}}
[[File:Julia_set_for_the_rational_function.png|右|缩略图|240x240像素|{{Math|''f''(''z'') {{=}} ''z''<sup>3</sup> − 1}}的牛顿分形]]
'''牛顿分形'''（{{lang-en|Newton fractal}}）是将[[牛顿法]]应用于一给定[[多项式]]{{Math|''p''(''Z'') ∈ ℂ[''Z'']}}或[[超越函數|超越函数]]而得到的[[复平面]]上的一个[[边界 (拓扑学)|边界集]]。它是由牛顿法所定义的[[亚纯函数]]{{Math|''z'' ↦ ''z'' − {{sfrac|''p''(''z'')|''p′''(''z'')}}}}的[[朱利亚集]]。当不存在吸引循环（阶数大于1）时，它将复平面划分为不同的区域{{math|''G<sub>k</sub>''}}，每个区域与多项式的根{{math|''ζ<sub>k</sub>''}}相关联，其中{{math|''k'' {{=}} 1, …, deg(''p'')}}。此时牛顿分形类似于[[曼德博集合]]，并且与其他分形一样，它将简单的数学描述变成了非常繁复的图像。从[[数值分析]]的角度而言，牛顿分形表现出牛顿法在[[收斂速度|二次收敛]]区域之外对于初始点的选择非常敏感。

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

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

为了绘制一个牛顿分形图像，可以首先选择指定数量{{Mvar|d}}的复点{{Math|(''ζ''<sub>1</sub>, …, ''ζ<sub>d</sub>'')}}并计算多项式的系数{{Math|(''p''<sub>1</sub>, …, ''p<sub>d</sub>'')}}

: <math>p(z)=z^d+p_1z^{d-1}+\cdots+p_{d-1}z+p_d:=(z-\zeta_1)(z-\zeta_2)\cdots(z-\zeta_d)</math> .

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

: <math>z_{mn} = z_{00} + m \, \Delta x + in \, \Delta y; \quad m = 0, \ldots, M - 1; \quad n = 0, \ldots, N - 1</math>

找到每个点{{Math|(''m'',''n'')}}对应的根{{Math|''ζ''<sub>''k''(''m'',''n'')</sub>}}的编号{{Math|''k''(''m'',''n'')}}，并通过为每一点分配一个颜色{{Math|''f''<sub>''k''(''m'',''n'')</sub>}}来填充这一{{Math|''M'' × ''N''}}网格。另外，颜色可以取决于距离{{Math|''D''(''m'',''n'')}}。对于某一固定的小{{Math|''ε'' > 0}}，距离{{Mvar|D}}可以定义为第一个使得{{Math|{{abs|''z<sub>D</sub>'' − ''ζ''<sub>''k''(''m'',''n'')</sub>}} < ''ε''}}成立的{{Mvar|D}}值。

== 牛顿分形的推广 ==
牛顿迭代的一种推广可表示为
: <math>z_{n+1}=z_n- a \frac{p(z_n)}{p'(z_n)} </math>

其中{{Mvar|a}}是任意复数。<ref>{{Cite web|title=Fractals derived from Newton–Raphson|url=http://www.chiark.greenend.org.uk/~sgtatham/newton/|author=Simon Tatham|access-date=2022-06-05|archive-date=2022-06-15|archive-url=https://web.archive.org/web/20220615221958/https://www.chiark.greenend.org.uk/~sgtatham/newton/}}</ref>当{{Math|''a'' {{=}} 1}}时即对应于牛顿分形。当{{Mvar|a}}位于以1为圆心、半径为1的圆盘以内时，该映射的不动点是稳定的。而当{{Mvar|a}}位于这个圆盘之外时，不动点是局部不稳定的，不过该映射仍能表现出朱利亚集的分形结构。如果{{Mvar|p}}是{{Mvar|d}}次多项式，则当是{{Mvar|a}}位于以{{Mvar|d}}为圆心、半径为{{Mvar|d}}的圆盘内时，序列{{Mvar|z<sub>n</sub>}}是[[有界集合|有界]]的。

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

<gallery>
File:FRACT008.png|{{math|''p''(''z'') {{=}} ''z''<sup>3</sup> − 1}}的牛顿分形，颜色表示需要的迭代步数
File:Newtroot 1 0 0 m1.png|{{math|''p''(''z'') {{=}} ''z''<sup>3</sup> − 1}}的牛顿分形，颜色表示最终收敛到的根
File:Newton z3-2z+2.png|{{math|''p''(''z'') {{=}} ''z''<sup>3</sup> − 2''z'' + 2}}的牛顿分形，红色区域中的点不收敛到任何根
File:Colored Newton Fractal 2.png|一个7次多项式的牛顿分形，颜色表示最终收敛到的根，深浅表示收敛速度
File:Timelapse34.jpg|{{math|''p''(''z'') {{=}} ''z''<sup>8</sup> + 15''z''<sup>4</sup> − 16}}的牛顿分形
File:Newtroot 1 0 m3i m5m2i 3 1.png|{{math|''p''(''z'') {{=}} ''z''<sup>5</sup> − 3''iz''<sup>3</sup> − (5 + 2''i'')''z''<sup>2</sup> + 3''z'' + 1}}的牛顿分形，颜色表示最终收敛到的根，深浅表示迭代步数
File:Timelapse4.jpg|{{math|''p''(''z'') {{=}} sin ''z''}}的牛顿分形，颜色表示最终收敛到的根，深浅表示迭代步数
File:Sin(x) detail.png|{{math|''p''(''z'') {{=}} sin ''z''}}的牛顿分形
File:Mnfrac1.png|{{math|''p''(''z'') {{=}} ''z''<sup>3</sup> − 1}}的广义牛顿分形（{{math|''a'' {{=}} −{{sfrac|1|2}}}}）
File:Mnfrac2.png|{{math|''p''(''z'') {{=}} ''z''<sup>2</sup> − 1}}的广义牛顿分形（{{math|''a'' {{=}} 1 + ''i''}}）
File:Mnfrac3.png|{{math|''p''(''z'') {{=}} ''z''<sup>3</sup> − 1}}的广义牛顿分形（{{math|''a'' {{=}} 2}}）
File:Mnfrac4.png|{{math|''p''(''z'') {{=}} ''z''<sup>4 + 3''i''</sup> − 1}}的广义牛顿分形（{{math|''a'' {{=}} 2.1}}）
File:Newton z6 z3.jmb.jpg|{{math|''p''(''z'') {{=}} ''z''<sup>6</sup> + ''z''<sup>3</sup> − 1}}的牛顿分形
File:Newton SINUS.jmb.jpg|{{math|''p''(''z'') {{=}} sin ''z'' − 1}}的牛顿分形
File:Newton COSH.jmb.jpg|{{math|''p''(''z'') {{=}} cosh ''z'' − 1}}的牛顿分形
</gallery>

=== 新星分形 ===
新星分形（Nova fractal）是由Paul Derbyshire于1990年代发明的一种分形。<ref>{{Cite web|title=class Standard_NovaMandel (Ultra Fractal formula reference)|url=http://formulas.ultrafractal.com/reference/Standard/Standard_NovaMandel.html|author=Damien M. Jones|access-date=2022-06-05|archive-date=2018-12-15|archive-url=https://web.archive.org/web/20181215225453/http://formulas.ultrafractal.com/reference/Standard/Standard_NovaMandel.html}}</ref><ref>{{Cite web|title=dmj's nova fractals 1995-6|url=http://www.icd.com/tsd/fractals/|author=Damien M. Jones|access-date=2022-06-05|archive-date=2017-08-20|archive-url=https://web.archive.org/web/20170820213109/http://www.icd.com/tsd/fractals/}}</ref>它也是牛顿分形的一种推广，即在每一步迭代时都增加了一个{{Mvar|c}}值： <ref>{{Cite web|title=Relaxed Newton's Method and the Nova Fractal|url=http://hpdz.net/TechInfo/Convergent.htm#Nova|author=Michael Condron|access-date=2022-06-05|archive-date=2022-03-28|archive-url=https://web.archive.org/web/20220328055947/http://hpdz.net/TechInfo/Convergent.htm#Nova}}</ref>

: <math>z_{n+1}=z_n- a \frac{p(z_n)}{p'(z_n)} + c = G(a, c, z)</math>

新星分形的“朱利亚”版本令{{Mvar|c}}为常数，并将像素坐标设为初始值{{Math|''z''<sub>0</sub>}}。而新星分形的“曼德博”版本则用像素坐标来初始化{{Mvar|c}}，并将{{Math|''z''<sub>0</sub>}}设置为一临界点，满足<ref>{{Cite web|title=Ultra Fractal Manual: Nova (Julia, Mandelbrot)|url=https://www.ultrafractal.com/help/index.html?/help/formulas/standard/nova.html|author=Frederik Slijkerman|access-date=2022-07-08|archive-date=2022-01-04|archive-url=https://web.archive.org/web/20220104132343/https://www.ultrafractal.com/help/index.html?%2Fhelp%2Fformulas%2Fstandard%2Fnova.html}}</ref>

: <math>\frac{\partial}{\partial z} G(a, c, z) = 0.</math>

例如，{{Math|''p''(''z'') {{=}} (''z'' − 1)<sup>3</sup>}}的临界点位于{{Math|''z'' {{=}} 1}}处。

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

: <math>\begin{align} f(z) &= z^3 - 1 \\ f'(z) &= 3z^2 \end{align}</math>

该函数的三个根是

: <math>z = 1,\ -\tfrac12 + \tfrac{\sqrt 3}{2}i,\ -\tfrac12 - \tfrac{\sqrt 3}{2}i</math>

该函数可以以[[伪代码]]表示如下：
<syntaxhighlight lang="c">
//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
}
</syntaxhighlight>

之后只需用给定函数实现牛顿法即可：
<syntaxhighlight lang="c">
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
}
</syntaxhighlight>

== 参考文献 ==
{{Reflist}}

{{分形}}
{{艾薩克·牛頓}}

[[Category:分形]]
[[Category:数值分析]]