Источник математической красоты

Полюбуйтесь-ка какая красота! Давайте разберëмся как она получается и почему устроена она именно таким образом.

Перед нами очередная симпатичная фрактальная структура, которыми стала полна популярная математика последние лет 30, с тех пор, как появилась вычислительная техника и цветные мониторы.

Эту картинку породил метод Ньютона — один из хорошо известных методов численного решения алгебраических уравнений. Суть его очень проста: имея некоторое приближение к точке, в которой график функции пересекает ось абсцисс, мы уточняем его, следуя касательной к графику в этой точке, и находим новое приближение там, где касательная пересекает ось Ох.

В виде формулы это уточнение записывается таким образом:

По мере повторения этих уточнений, последовательность приближений {xₙ} сходится к истинному нулю функции чрезвычайно быстро. Если, конечно, сходится. Очень легко найти такие неудачные функции и начальные точки, при которых процесс уточнения сходящимся уже не будет.

Существуют методы борьбы с этим явлением, однако, если нас интересуют не корни, а красивые картинки, то эта особенность метода Ньютона нам только на руку. Именно скорость сходимости является той величиной, которая обладает красивыми фрактальными свойствами.

К достоинствам метода Ньютона относится то, что он прекрасно работает как для вещественных так и для комплексных чисел, не требуя никаких изменений. Красивые картинки получаются именно при переходе в комплексную плоскость.

Метод создания картинок на базе метода Ньютона такой. Задаём несколько точек на плоскости, которые соответствуют комплексным числам и по ним строим многочлен:

После этого каждой точке z на комплексной плоскости ставим в соответствие функцию S(z) возвращающую число шагов, которое необходимо методу Ньютона для достижения какого-либо корня многочлена f, начиная с точки z.

Вот как выглядит добавление новых корней многочлена.

Полюбуйтесь танцем метода Ньютона под управлением семи двигающихся точек

Здесь более яркий цвет соответствует большему числу итераций, необходимых для приближения к какому-либо корню.

Рецепт для любопытных

Для того чтобы эта заметка была не только интересной, но и полезной, приведу пример кода на Julia, который порождает такой симпатичный симметричный фрактал Ньютона.

Сначала подгрузим модуль для графики

Следующая функция вычисляет многочлен, заданный корнями, и его производную в указанной точке:

При этом используется хитрая техника автоматического дифференцирования, основанная на матричном представлении арифметики дуальных чисел. Так что вычисление как функции, так и её производной происходит одновременно за один проход по списку корней.

Реализуем функцию, возвращающую число шагов, которое необходимо методу Ньютона, для приближения к пределу:

Теперь можно нарисовать красивую картинку для корней K-той степени из единицы.

Вот несколько симпатичных примеров работы этой программы:

Откуда взялся фрактал?

А теперь, самое интересное. Где же источник этой красоты? Что же такого фрактального в методе Ньютона?

Каждый корень функции f это аттрактор, то есть, точка, которая притягивает к себе остальные под действием ньютоновского шага для этой функции. При этом почти все остальные точки плоскости разбиваются на классы по тому, к какому именно корню они притянутся. Эти классы называются областями притяжения или бассейнами (как бассейн реки или озера).

Три бассейна корней третьей степени из единицы.

Я написал "почти все", потому бывают ещё точки, которые притягиваются не к какому-то из корней, а к устойчивому циклу, они образуют свои бассейны. Кроме того, возможно некоторое множество особых точек, из которых ньютоновский шаг уносит в бесконечность и не приводит никуда, оно называется множеством Жулиа. Множество всех неособых точек, называют множеством Фату. Эти множества можно определить для каждого отображения комплексной плоскости на саму себя.

Множество Жулиа для уравнения третьей степени.

Если множество Фату распадается на два бассейна, то они могут граничить между собой как угодно, гладко или фрактально, это не важно. А вот с границами трёх и более бассейнов есть нюанс. Такая граница должна состоять точек, любая малая окрестность которых содержит точки, принадлежащие всем возможным бассейнам. Такие точки на плоскости могут быть либо дискретными, либо, если их будет бесконечно много, должны организовываться в сложную фрактальную структуру, которая свой бесконечной детализованностью делает возможным существование не точки, а границы трёх или более бассейнов. Правда, эта граница будет всюду негладкой и обладать сложной топологией.

Применительно к отображению, которое представляет шаг метода Ньютона, то в точках из множества Жулиа производная функции обращается в ноль, так что окрестность такой точки под действием шага метода Ньютона, будет буквально взрываться, активно "размазываясь" по всей комплексной плоскости. Существует теорема Монтелля, общая для всех отображений комплексной плоскости на себя рациональной функцией, из которой следует, что сколь угодно малая окрестность любой точки из множества Жулиа под действием преобразования будет отображаться на все бассейны, на которые распадается множество неособых точек.

Именно по этой причине происходит "фрактализация" границы между бассейнами и хаотизация метода Ньютона вблизи особых точек.