Готово
Метод Ньютона — один із найдавніших алгоритмів знаходження коренів функцій: починаючи з початкового наближення z₀, він ітерує z ← z − f(z)/f′(z) до збіжності до кореня. Застосований до полінома у комплексній площині, цей простий алгоритм породжує несподівано заплутану структуру — межа між областями, що збігаються до різних коренів, є фракталом. Для класичного випадку f(z) = z³ − 1 три корені одиниці (кубічні корені: 1, e^{2πi/3}, e^{4πi/3}) кожен притягують свій басейн, а межі між ними мають нескінченну деталізацію на будь-якому масштабі.
Кожен піксель полотна відповідає початковій точці в комплексній площині. Симуляція запускає ітерацію Ньютона з цієї точки і забарвлює піксель відповідно до того, до якого кореня вона збіглась, причому яскравість кодує швидкість збіжності. Скористайтеся вибором полінома для переходу між z³−1, z⁴−1, z⁵−1 і вищими степенями, а прокручування або щипок дозволить наближатися до межі фракталу, щоб побачити все тонші самоподібні структури.
Що таке метод Ньютона і чому він породжує фрактал?
Метод Ньютона ітерує z ← z − f(z)/f′(z) для пошуку коренів f. Для поліномів степеня ≥ 3 у комплексній площині басейни притягання (множини початкових точок, що збігаються до кожного кореня) розділені нескінченно складною межею. Ця межа є множиною Жюліа — вона має фрактальну розмірність більшу за 1 і самоподібна на всіх масштабах. Поблизу будь-якої точки межі можна знайти початкові точки, що прямують до всіх n коренів одночасно.
Що таке корені одиниці і де вони на зображенні?
Корені одиниці n-го степеня — це n розв'язків рівняння zⁿ = 1: zₖ = e^{2πik/n} для k = 0, 1, …, n−1. Вони рівномірно розташовані на одиничному колі комплексної площини. Для z³ − 1 три корені знаходяться під кутами 0°, 120° і 240°; метод Ньютона від будь-якої початкової точки збіжеться до одного з цих трьох значень або не збіжеться у хаотичній зоні межі.
Чому додавання більшої кількості коренів (вищий степінь) ускладнює фрактал?
При n коренях n басейнів борються за кожну початкову точку. Для z² − 1 межа басейнів — просто уявна вісь, що тривіально просто, як показав Артур Келі у 1879 році. При n ≥ 3 межі стають фракталами — множинами Жюліа. Складність зростає з n: більше коренів означає більше басейнів, а межа між ними стає все заплутанішою з багатшими самоподібними патернами на дрібніших масштабах.
У 1879 році Артур Келі розв'язав задачу збіжності методу Ньютона для z² − 1 (межа — просто уявна вісь), але зазначив, що z³ − 1 «являє значні труднощі». Ці труднощі і є фрактал — структура, яку не можна було візуалізувати до того часу, поки комп'ютери не змогли забарвити мільйони пікселів. Сучасне розуміння прийшло завдяки роботам Мандельброта, Хаббарда і Дуаді у 1980-х роках.
Яскравіші пікселі збіглися до свого кореня за меншу кількість ітерацій Ньютона; темніші вимагали більше. Точки поблизу межі фракталу довго коливаються між басейнами, тому виглядають темними. Точки далеко від межі збігаються швидко і виглядають яскравими. Цей метод називається кодуванням за кількістю ітерацій — аналог того, як зазвичай відображають множину Мандельброта.
Для початкових точок далеко від межі фракталу метод Ньютона збігається квадратично: кількість правильних десяткових цифр приблизно подвоюється з кожною ітерацією. Починаючи з відстані 0,1 від кореня, після одного кроку ви на відстані ~0,01, після двох ~0,0001 і так далі. Ця швидка збіжність робить метод Ньютона одним з найефективніших алгоритмів пошуку коренів у практичних застосуваннях.
В точці z = 0 похідна f′(z) = n·z^{n−1} = 0, тому крок Ньютона z − f(z)/f′(z) не визначений (ділення на нуль). На практиці симуляція зміщує z на мале значення (~10⁻¹⁰), щоб уникнути цієї сингулярності. Початок координат є «відштовхувальною нерухомою точкою» відображення Ньютона — старт поблизу нього призводить до розбіжності або стрибків, перш ніж потрапити до якогось басейну.
Так — математично межа множини Жюліа має вимірність Хаусдорфа строго між 1 і 2 (для фракталів Ньютона вона зазвичай близька до 2). На будь-якому рівні збільшення можна наближатися і відкривати нові структури, ідентичні за характером великомасштабному зображенню. Математичний об'єкт самоподібний на всіх масштабах — збільшення у 10^100 разів виявило б патерни невідмінні від огляду.
Межі басейнів методу Ньютона є множинами Жюліа для раціонального відображення N(z) = z − f(z)/f′(z). Множина Мандельброта параметризує, які множини Жюліа є зв'язними, а які — тотально незв'язними. Фрактали Ньютона — це особлива родина множин Жюліа, де раціональне відображення походить від ітерації Ньютона. Складна структура меж, що видна тут, є прямим наслідком тієї ж теорії комплексних динамічних систем, яка породжує множину Мандельброта.
Ця симуляція малює фрактал Ньютона, застосовуючи ітерацію методу Ньютона z ← z − f(z)/f′(z) до кожного пікселя комплексної площини, розглядаючи його як стартову точку. Колір пікселя показує, до якого кореня обраного полінома збігається ітерація, а яскравість — за скільки кроків це сталося. Перемикання між z³−1 і z⁸−1 змінює кількість коренів, а отже й кількість басейнів притягання, роблячи межу між ними дедалі складнішою.
n коренів полінома zⁿ−1, рівномірно розташованих на одиничному колі комплексної площини, кожен зі своїм басейном притягання. Яскраві кольори означають швидку збіжність із цієї точки; темні заплутані межі між басейнами — це і є місце, де ховається фрактальна деталізація.
Оберіть поліном (від z³−1 до z⁸−1), потім налаштуйте максимальну кількість ітерацій, допуск збіжності ε та насиченість кольору повзунками. Прокручуйте колесо миші, щоб наближати межу, і перетягуйте мишею для панорамування; кнопка «Reset view» повертає початковий кадр, а «Re-render» перемальовує з поточними налаштуваннями.
Артур Келі розв'язав випадок із двома коренями (z²−1) ще 1879 року, показавши, що межа — це просто пряма лінія, проте зауважив, що випадок із трьома коренями z³−1 «становить значні труднощі» — ця складність виявилася справжнім фракталом, який по-справжньому зрозуміли лише через століття завдяки теорії комплексної динаміки.
Для поліномів із трьома і більше коренями межа між множинами точок, що збігаються до різних коренів, є нескінченно деталізованою на будь-якому масштабі. Ця межа — різновид множини Жюліа, і саме вона утворює складні візерунки між кольоровими басейнами.
Кожен відтінок відповідає одному кореню полінома, тож колір пікселя показує, до якого кореня прийшла його стартова точка; яскравість кодує кількість ітерацій Ньютона — швидка збіжність малюється яскравіше, а повільна, наближена до межі, — темніше.
Допуск визначає, наскільки близько точка має підійти до кореня, щоб вважатися збіжною; більше значення ε приймає збіжність раніше й дає гладкіші басейни, тоді як менше вимагає більше ітерацій і показує тонший розподіл межі ціною більших обчислень.
Що більше коренів, то більше басейнів конкурують за кожну стартову точку, тож межі між ними доводиться петляти між більшою кількістю сусідів; перехід від z³−1 до z⁸−1 приблизно подвоює кількість басейнів і помітно посилює складність межі.
Такі пікселі малюються темно-сірими, а не кольором жодного кореня; зазвичай це трапляється точно на фрактальній межі або дуже близько до неї, де ітерація може довго стрибати між басейнами, перш ніж осісти, а іноді — у справжній хаотичній множині, яка взагалі не збігається.