Метод Ньютона як Фрактал: Басейни Притягання у Комплексній Площі (Newton's Method Fractal: Basins of Attraction in the Complex Plane)

Метод Ньютона, застосований до кожного пікселя

Метод Ньютона знаходить корінь функції f шляхом повторного слідування похідній лінії вниз до точки, де вона перетинає нуль: починаючи з оцінки z, наступна оцінка становить z - f(z)/f'(z). Для реальної функції це швидко збігається біля кореня та може поводитися непередбачувано далеко від нього. Застосовуйте той самий ітеративний процес із комплексних початкових значень z = x + iy, і коліруйте кожен піксельний початок, до якого сходиться його ітерація, і ви отримаєте Ньютонову фракталь — зображення басейнів притягання кожного кореня, з усіма звичайними гарантіями збіжності, які руйнуються вражаюче вздовж меж басейну.

Ітерація та конкретний поліном

Для найпростішого цікавого випадку, f(z) = z² - 1, який має n коренів (де n – кількість коренів), оновлення Ньютона спрощується до:

z_(k+1) = z_k - (z_k² - 1) / (n * z_k²) = ((n - 1) * z_k² + 1) / (n * z_k²) Кожен піксель площини є незалежним початковим значенням z₀. Ітеруйте певну кількість разів (зазвичай 30-60, достатньо для збіжності майже всюди, крім прямо на межі), перевірте, до якого з n коренів найближче кінцеве значення, і зафарбуйте піксель цим кольором. Забарвлення шляхом кількості ітерацій до збіжності, а не рівномірним кольором, перетворює плоскі басейни на смугасті контурні кільця, які розкривають фрактальну структуру, що ховається всередині області, яка здається одноманітною.

z_(k+1) = z_k - (z_kⁿ - 1) / (n·z_kⁿ⁻¹)
        = ((n-1)·z_kⁿ + 1) / (n·z_kⁿ⁻¹)

Чому межі є фрактальними

Поруч із коренем метод Ньютона квадратично збігається — кількість правильних знаків приблизно подвоюється на кожному кроці, тому глибоко всередині басейну картина гладка та нудна. Цікаву структуру повністю складають межі між бассейнами. Оскільки ітераційне функцію z - f(z)/f'(z) є раціональною картою сфери Рімана, її множина Юли (межа, де близькі початкові точки розходяться до різних атракторів) має самосвідбну, нескінченно деталізовану структуру, характерну для складної динаміки: збільште масштаб будь-якої граничної точки і ви знайдете менші копії того ж переплету з трьох або більше басейнів, назавжди.

Це особливий випадок давньої та дивовижної факти з складної динаміки: межа між бассейнами привабежності будь-якої раціональної карти з трьох або більше відмінних атракторів постійного значення є зв’язаною або має нескінченну кількість компонентів, і в випадку методу Ньютона для загального кубічного, всі три басейни відомо мають спільний край — кожна гранична точка одночасно знаходиться настільки близько до всіх трьох басейнів, лише не до двох з них, справді тривимірна патологія, що живе в 2D карти.

Розгляд випадків, коли метод Ньютона не збігається

Не кожна початкова точка стабілізується. Якщо похідна f'(z) дорівнює нулю в процесі ітерації, то оновлення розсипається; більш часто початкова точка потрапляє у періодичний цикл, який не досягає жодного кореня - для z^199 - 2z + 2, справжнє початкове значення z0 = 0 відомім чином циклічно переходить між 1 та 0 без жодної збіжності, класичний приклад, що суперечить наївним твердженням про збіжність. Фрактальна картинка позначує такі точки (або точки, які не збігаються протягом бюджету ітерацій) характерним кольором «відсутність збіжності», зазвичай чорним, і ці точки є тими місцями, де межі басейну найтовщі та найбільш перекручені.

Розслаблений Ньютон та перемикання поліномів

Демпфування (розслаблення) фактор λ змінює оновлення до z_(k+1) = z_k - λ·f(z)/f'(z). При λ=1 ви отримаєте стандартний Ньютон; менше λ сповільнює збіжність, але може зменшити або змінити форму фрактальної межі, а складне λ обертає басейн забарвлення повністю, оскільки змінюється напрямок, на якому кожний крок дозволено рухатися відносно дотичної лінії. Перемикання полінома з zⁿ-1 до чогось несиметричного, як z³-2z+2, видаляє симетрію обертання коренів-одиниць і виробляє помітно інший, менш симетричний клубок басейнів - демо випускає можливість перемикатися між ними та перемальовувати їх наживо.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Newton's Method Fractal і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.