Ньютон фрактал

— Фрактал Ньютона это граничное множество на комплексной плоскости , которое характеризуется методом Ньютона, примененным к фиксированному многочлену $p (z) \in$ $\mathbb {C}$ $[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{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);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)$ . В этом отношении фрактал Ньютона подобен множеству Мандельброта и, как и другие фракталы, имеет сложный внешний вид, возникающий из-за простого описания. Это актуально для численного анализа , поскольку показывает, что (за пределами области квадратичной сходимости ) метод Ньютона может быть очень чувствителен к выбору начальной точки.

Почти все точки комплексной плоскости связываются с одним из $корней deg(p)$ данного полинома следующим образом: точка используется в качестве начального значения $z 0$ для итерации Ньютона $z n + 1 := z n - ⁠ p (z n) / p' (z n) ⁠$ , что дает последовательность точек $z 1, z 2, \dots,$ Если последовательность сходится к корню $ζ k$ , то $z 0$ был элементом области $G k$ . Однако для каждого многочлена степени не ниже 2 существуют точки, для которых итерация Ньютона не сходится ни к одному корню: примерами являются границы бассейнов притяжения различных корней. Существуют даже многочлены, для которых открытые множества начальных точек не сходятся ни к одному корню: простой пример - $z 3 - 2 z + 2$ , где некоторые точки притягиваются циклом $0, 1, 0, 1\dots,$ а не корнем.

Открытое множество, для которого итерации сходятся к заданному корню или циклу (который не является фиксированной точкой), является множеством Фату для итерации. Дополнительным набором к объединению всех этих элементов является набор Джулии. Множества Фату имеют общую границу — множество Жюлиа. Следовательно, каждая точка множества Жюлиа является точкой накопления каждого из множеств Фату. Именно это свойство обусловливает фрактальную структуру множества Жюлиа (когда степень многочлена больше 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

очков в $\mathbb {C}$ , находят индекс $k (m, n)$ соответствующего корня $ζ k (m, n)$ и используют его для заполнения $растровой сетки M \times N$ , присваивая каждой точке $(m, n)$ цвет $f k (m, н)$ . Дополнительно или альтернативно цвета могут зависеть от расстояния $D (m, n)$ , которое определяется как первое значение $D$ такое, что $| z D - ζ k (м, п) | < ε$ для некоторых заранее фиксированных малых $ε > 0$ .

Обобщение фракталов Ньютона.

Обобщением итерации Ньютона является

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

где $а$ — любое комплексное число . ^[1] Специальный выбор $a = 1$ соответствует фракталу Ньютона. Неподвижные точки этой карты стабильны, когда $a$ лежит внутри диска радиуса 1 с центром в 1. Когда $a$ находится вне этого диска, неподвижные точки локально неустойчивы, однако карта все еще демонстрирует фрактальную структуру в смысле множества Жюлиа . Если $p$ — многочлен степени $d$ , то последовательность $z n$ ограничена при условии, что $a$ находится внутри круга радиуса $d$ с центром в $d$ .

В более общем смысле фрактал Ньютона — это частный случай множества Жюлиа .

Фрактал Ньютона для трех корней степени 3 $p (z) = z 3 - 1$ , окрашенный в соответствии с количеством требуемых итераций
Фрактал Ньютона для трех корней степени 3 $p (z) = z 3 - 1$ , окрашенный по достижении корня
Фрактал Ньютона для $p (z) = z 3 - 2 z + 2$ . Точки в красных тазах не доходят до корня.
Фрактал Ньютона для полинома 7-го порядка, раскрашенный по достигнутому корню и заштрихованный по скорости сходимости.
Фрактал Ньютона для $p (z) = z 8 + 15 з 4 - 16$
Фрактал Ньютона для $p (z) = z 5 - 3 из 3 - (5 + 2 я) z 2 + 3 z + 1$ , окрашено в соответствии с достигнутым корнем, заштриховано количеством требуемых итераций.
Фрактал Ньютона для $p (z) = sin z$ , раскрашен по достигнутому корню, заштрихован по количеству требуемых итераций
Еще один фрактал Ньютона для $p (z) = sin z$
Обобщенный фрактал Ньютона для $p (z) = z 3 - 1$ , $а = - ⁠ 1/2 ⁠ $ . Цвет был выбран на основе аргумента после 40 итераций.
Обобщенный фрактал Ньютона для $p (z) = z 2 - 1$ , $а знак равно 1 + я$ .
Обобщенный фрактал Ньютона для $p (z) = z 3 - 1$ , $а знак равно 2$ .
Обобщенный фрактал Ньютона для $p (z) = z 4 + 3 я - 1$ , $а знак равно 2,1$ .
$п (z) знак равно z 6 + я 3 - 1$
$п (z) = грех z - 1$
$п (z) = грех z - 1$
$п (z) = шош z - 1$
$п (z) = шош z - 1$
$п (z) знак равно z 20 -2з + 2$

Серия: $п (z) = z н - 1$

$п (z) знак равно z 3 - 1$ , а=1
$п (z) знак равно z 3 - 1$ , а=2
$п (z) знак равно z 4 - 1$ , а=1
$п (z) знак равно z 4 - 1$ , а=2
$п (z) знак равно z 5 - 1$ , а=1
$п (z) знак равно z 5 - 1$ , а=2
$п (z) знак равно z 6 - 1$ , а=1
$п (z) знак равно z 7 - 1$ , а=1
$п (z) знак равно z 8 - 1$ , а=1
$п (z) знак равно z 10 - 1$ , а=1

Другие фракталы, в которых умножаются потенциальные и тригонометрические функции. $п (z) знак равно z н *Грех(з) - 1$

$п (z) знак равно z 2 *Sin(Z) - 1$ , а=1
$п (z) знак равно z 2 *Sin(Z) - 1$ , a=1 (масштаб)
$п (z) знак равно z 3 *Sin(Z) - 1$ , а=1
$п (z) знак равно z 4 *Sin(Z) - 1$ , а=1
$п (z) знак равно z 4 *Sin(Z) - 1$ , a=1 (масштаб)
$п (z) знак равно z 5 *Sin(Z) - 1$ , а=1
$п (z) знак равно z 6 *Sin(Z) - 1$ , а=1
$п (z) знак равно z 6 *Sin(Z) - 1$ , a=1 (масштаб)

Нова фрактал

Фрактал Нова, изобретенный в середине 1990-х годов Полом Дербиширом. ^[2]^[3] представляет собой обобщение фрактала Ньютона с добавлением значения $c$ на каждом шаге: ^[4]

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

Вариант фрактала Nova «Джулия» сохраняет $константу c$ по изображению и инициализирует $z 0$ координатами пикселей. Вариант фрактала Нова «Мандельброта» инициализирует $c$ координатами пикселя и устанавливает $z 0$ в критическую точку, где ^[5]

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

Часто используемые полиномы, такие как $p (z) = z 3 - 1$ или $п (z) = (z - 1) 3$ привести к критической точке при $z = 1$ .

Анимированный фрактал "Джулия" Нова для $p (z) = z 3 - 1$ , где $c$ меняется от −1 до 1, раскрашивается по достигнутому корню.
Анимированный фрактал "Джулия" Нова для $p (z) = z 3 - 1$ с $c = ⁠ 1 / 2 ⁠ e iφ$ и $φ$ меняется от 0 до 2 $π$ , раскрашенных по достигнутому корню.

Выполнение

Чтобы реализовать фрактал Ньютона, необходимо иметь как стартовую функцию, так и ее производную функцию:

{\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
}

См. также

Ссылки

^ Саймон Тэтэм. «Фракталы, полученные от Ньютона – Рафсона» .
^ Дэмиен М. Джонс. «класс Standard_NovaMandel (ссылка на формулу ультрафрактала)» .
^ Дэмиен М. Джонс. «Новые фракталы dmj 1995-6» .
^ Майкл Кондрон. «Расслабленный метод Ньютона и новый фрактал» .
^ Фредерик Слейкерман. «Руководство по ультрафракталам: Нова (Юлия, Мандельброт)» .

Дальнейшее чтение

Дж. Хаббард, Д. Шлейхер, С. Сазерленд : Как найти все корни комплексных многочленов методом Ньютона , Inventiones Mathematicae vol. 146 (2001) - с обсуждением глобальной структуры фракталов Ньютона.
О количестве итераций метода Ньютона , Дирк Шлейхер, 21 июля 2000 г.
Метод Ньютона как динамическая система Йоханнеса Рюкерта
«Фрактал Ньютона» (о котором Ньютон ничего не знал) от 3Blue1Brown вместе с интерактивной демонстрацией фрактала на его сайте и исходным кодом для демонстрации.

[1] Саймон Тэтэм. «Фракталы, полученные от Ньютона – Рафсона» .

[2] Дэмиен М. Джонс. «класс Standard_NovaMandel (ссылка на формулу ультрафрактала)» .

[3] Дэмиен М. Джонс. «Новые фракталы dmj 1995-6» .

[4] Майкл Кондрон. «Расслабленный метод Ньютона и новый фрактал» .

[5] Фредерик Слейкерман. «Руководство по ультрафракталам: Нова (Юлия, Мандельброт)» .

[1]

[2]

[3]

[4]

[5]

v т и сэр Исаак Ньютон
Publications	Fluxions (1671) De Motu (1684) Principia (1687) Opticks (1704) Queries (1704) Arithmetica (1707) De Analysi (1711)
Other writings	Quaestiones (1661–1665) "standing on the shoulders of giants" (1675) Notes on the Jewish Temple (c. 1680) "General Scholium" (1713; "hypotheses non fingo" ) Ancient Kingdoms Amended (1728) Corruptions of Scripture (1754)
Contributions	Calculus fluxion Impact depth Inertia Newton disc Newton polygon Newton–Okounkov body Newton's reflector Newtonian telescope Newton scale Newton's metal Spectrum Structural coloration
Newtonianism	Bucket argument Newton's inequalities Newton's law of cooling Newton's law of universal gravitation post-Newtonian expansion parameterized gravitational constant Newton–Cartan theory Schrödinger–Newton equation Newton's laws of motion Kepler's laws Newtonian dynamics Newton's method in optimization Apollonius's problem truncated Newton method Gauss–Newton algorithm Newton's rings Newton's theorem about ovals Newton–Pepys problem Newtonian potential Newtonian fluid Classical mechanics Corpuscular theory of light Leibniz–Newton calculus controversy Newton's notation Rotating spheres Newton's cannonball Newton–Cotes formulas Newton's method generalized Gauss–Newton method Newton fractal Newton's identities Newton polynomial Newton's theorem of revolving orbits Newton–Euler equations Newton number kissing number problem Newton's quotient Parallelogram of force Newton–Puiseux theorem Absolute space and time Luminiferous aether Newtonian series table
Personal life	Woolsthorpe Manor (birthplace) Cranbury Park (home) Early life Later life Apple tree Religious views Occult studies Scientific Revolution Copernican Revolution
Relations	Catherine Barton (niece) John Conduitt (nephew-in-law) Isaac Barrow (professor) William Clarke (mentor) Benjamin Pulleyn (tutor) John Keill (disciple) William Stukeley (friend) William Jones (friend) Abraham de Moivre (friend)
Depictions	Newton by Blake (monotype) Newton by Paolozzi (sculpture) Isaac Newton Gargoyle Astronomers Monument
Namesake	Newton (unit) Newton's cradle Isaac Newton Institute Isaac Newton Medal Isaac Newton Telescope Isaac Newton Group of Telescopes XMM-Newton Sir Isaac Newton Sixth Form Statal Institute of Higher Education Isaac Newton Newton International Fellowship
Categories	Isaac Newton

v т и Фракталы
Characteristics	Fractal dimensions Assouad Box-counting Higuchi Correlation Hausdorff Packing Topological Recursion Self-similarity
Iterated function system	Barnsley fern Cantor set Koch snowflake Menger sponge Sierpinski carpet Sierpinski triangle Apollonian gasket Fibonacci word Space-filling curve Blancmange curve De Rham curve Minkowski Dragon curve Hilbert curve Koch curve Lévy C curve Moore curve Peano curve Sierpiński curve Z-order curve String T-square n-flake Vicsek fractal Hexaflake Gosper curve Pythagoras tree Weierstrass function
Strange attractor	Multifractal system
L-system	Fractal canopy Space-filling curve H tree
Escape-time fractals	Burning Ship fractal Julia set Filled Newton fractal Douady rabbit Lyapunov fractal Mandelbrot set Misiurewicz point Multibrot set Newton fractal Tricorn Mandelbox Mandelbulb
Rendering techniques	Buddhabrot Orbit trap Pickover stalk
Random fractals	Brownian motion Brownian tree Brownian motor Fractal landscape Lévy flight Percolation theory Self-avoiding walk
People	Michael Barnsley Georg Cantor Bill Gosper Felix Hausdorff Desmond Paul Henry Gaston Julia Helge von Koch Paul Lévy Aleksandr Lyapunov Benoit Mandelbrot Hamid Naderi Yeganeh Lewis Fry Richardson Wacław Sierpiński
Other	"How Long Is the Coast of Britain?" Coastline paradox Fractal art List of fractals by Hausdorff dimension The Fractal Geometry of Nature (1982 book) The Beauty of Fractals (1986 book) Chaos: Making a New Science (1987 book) Kaleidoscope Chaos theory