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

Фрактал Ньютона — это граничное множество в комплексной плоскости , которое характеризуется методом Ньютона, примененным к фиксированному полиному $p (z) \in$ $[$ $z$ $]$ или трансцендентной функции . Это множество Жюлиа мероморфной функции $z$ $\mapsto$ $z$ $-$ $⁠$ $\mathbb {C}$ $.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}п ( з )/р′ ( z )⁠$ который дается методом Ньютона. Когда нет притягивающих циклов (порядка больше 1), он делит комплексную плоскость на области $G k$ , каждая из которых связана с корнем $ζ k$ многочлена, $k = 1, \dots, deg(p)$ . Таким образом, фрактал Ньютона похож на множество Мандельброта , и, как и другие фракталы, он демонстрирует сложный вид, возникающий из простого описания. Он имеет отношение к численному анализу , поскольку показывает, что (вне области квадратичной сходимости ) метод Ньютона может быть очень чувствителен к выбору начальной точки.

Почти все точки комплексной плоскости связаны с одним из корней $deg(p)$ заданного полинома следующим образом: точка используется как начальное значение $z 0$ для итерации Ньютона $z n + 1 := 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

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

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

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

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

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

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

Фрактал Ньютона для трех корней третьей степени $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 ⁠$ . Цвет был выбран на основе аргумента после 40 итераций.
Обобщенный фрактал Ньютона для $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$ .
$р (z) = z 6 + z 3 - 1$
$р (z) = sin z - 1$
$р (z) = sin z - 1$
$p (z) = cosh z - 1$
$p (z) = cosh z - 1$
$р (z) = z 20 - 2 z + 2$

Серия: $p (z) = zn - 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

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

$p (z) = z 2 *Sin(Z) - 1$ , a=1
$p (z) = z 2 *Sin(Z) - 1$ , a=1 (масштаб)
$p (z) = z 3 *Sin(Z) - 1$ , a=1
$p (z) = z 4 *Sin(Z) - 1$ , a=1
$p (z) = z 4 *Sin(Z) - 1$ , a=1 (масштаб)
$p (z) = z 5 *Sin(Z) - 1$ , a=1
$p (z) = z 6 *Sin(Z) - 1$ , a=1
$p (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 "Julia" сохраняет $c$ постоянным по всему изображению и инициализирует $z 0$ в пиксельных координатах. Вариант фрактала Nova "Mandelbrot" инициализирует $c$ в пиксельных координатах и устанавливает $z 0$ в критическую точку, где ^[5]

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

Обычно используемые полиномы, такие как $p (z) = z 3 - 1$ или $p (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{align}f(z)&=z^{3}-1\\f'(z)&=3z^{2}\end{align}}

Три корня функции:

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 - экспоненциальная функция для комплексных чисел }         //3*z^2 float2 Derivative ( float2 z ) { return 3 * cmul ( z , z ); // cmul — это функция, которая обрабатывает умножение комплексных чисел }

Теперь дело за малым — реализовать метод Ньютона с использованием заданных функций.

float2 roots [ 3 ] = //Корни (решения) многочлена { float2 ( 1 , 0 ), float2 ( -.5 , sqrt ( 3 ) / 2 ), float2 ( -.5 , - sqrt ( 3 ) / 2 ) }; color colors [ 3 ] = //Назначаем цвет для каждого корня { red , green , blue }              Для каждого пикселя ( x , y ) на цели выполните : { zx = масштабированная x - координата пикселя ( масштабированная так , чтобы соответствовать шкале Мандельброта X ( -2,5 , 1 ) ) zy = масштабированная y - координата пикселя ( масштабированная так , чтобы соответствовать шкале Мандельброта Y ( -2 , 1 ) )                                          float2 z = float2 ( zx , zy ); //z изначально установлено в пиксельных координатах     for ( int iteration = 0 ; iteration < maxIteration ; iteration ++ ;) { z -= cdiv ( Function ( z ), Derivative ( z )); //cdiv — функция для деления комплексных чисел             float допуск = 0.000001 ; for ( int i = 0 ; i < roots . Length ; i ++ ) { float2 разница = z - корни [ i ]; // Если текущая итерация достаточно близка к корню, раскрашиваем пиксель. if ( abs ( разница . x ) < допуск && abs ( разница . y ) < допуск ) { return colors [ i ]; // Возвращаем цвет, соответствующий корню } } } return black ; // Если решение не найдено }

Смотрите также

Ссылки

На Викискладе есть медиафайлы по теме «Фракталы Ньютона» .

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

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

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