🌀 Fraktal Newtona

W 1879 roku Arthur Cayley rozwiązał zbieżność metody Newtona dla z² − 1 (granica to po prostu oś urojona), ale zauważył, że z³ − 1 „stwarza znaczne trudności”. Ta trudność to właśnie fraktal — struktura, której nie dało się zwizualizować, dopóki komputery nie mogły pokolorować milionów pikseli. Współczesne zrozumienie przyszło dzięki pracy Mandelbrota, Hubbarda i Douady'ego w latach 80. XX wieku, wykorzystującej teorię zespolonych układów dynamicznych.

Jaśniejsze piksele zbiegły do swojego pierwiastka w mniejszej liczbie iteracji Newtona; ciemniejsze wymagały ich więcej. Punkty blisko granicy fraktala oscylują między basenami przez wiele kroków, zanim się ustabilizują, przez co są ciemne. Punkty daleko od granicy zbiegają szybko i wyglądają jasno. Ta technika kolorowania według liczby iteracji nazywana jest metodą „czasu ucieczki”, analogicznie do sposobu, w jaki zwykle renderuje się zbiór Mandelbrota.

Dla punktów startowych z dala od granicy fraktala metoda Newtona zbiega kwadratowo: liczba poprawnych cyfr dziesiętnych mniej więcej podwaja się z każdą iteracją. Zaczynając 0,1 od pierwiastka, po jednym kroku jesteś ~0,01 od niego, po dwóch ~0,0001 i tak dalej. Ta szybka zbieżność sprawia, że metoda Newtona jest jednym z najskuteczniejszych algorytmów znajdowania pierwiastków w praktyce, wykorzystywanym w kalkulatorach, odbiornikach GPS i praktycznie wszystkich bibliotekach obliczeń naukowych.

W z = 0 pochodna f′(z) = n·z^{n−1} = 0, więc krok Newtona z − f(z)/f′(z) jest niezdefiniowany (dzielenie przez zero). W praktyce symulacja przesuwa z o znikomą wartość (∼10⁻¹⁰), aby uniknąć tej osobliwości. Początek układu jest „odpychającym punktem stałym” odwzorowania Newtona — start w jego pobliżu powoduje, że iteracja rozbiega się lub skacze nieregularnie, zanim ostatecznie wyląduje w jakimś basenie.

Tak — matematycznie granica zbioru Julii ma wymiar Hausdorffa ściśle między 1 a 2 (dla fraktali Newtona jest zwykle bliski 2). Na dowolnym poziomie powiększenia można przybliżyć obraz, aby odkryć nową strukturę o charakterze identycznym z obrazem w dużej skali. W praktyce rozdzielczość symulacji ogranicza widoczne szczegóły, ale obiekt matematyczny jest samopodobny w każdej skali — powiększenie 10^100 razy ujawniłoby wzory nieodróżnialne od widoku ogólnego.

Zrelaksowana metoda Newtona zastępuje standardowy krok wzorem z ← z − a·f(z)/f′(z), gdzie a jest parametrem relaksacji. Przy a = 1 otrzymujemy klasyczną metodę Newtona. Wartości a ≠ 1 zniekształcają baseny i mogą tworzyć chaotyczne obszary, w których nigdy nie osiąga się żadnego pierwiastka. Nadmierna relaksacja (a > 1) przyspiesza zbieżność dla dobrze zachowujących się punktów startowych, ale rozszerza chaotyczną granicę. Preset wielomianu „chaos” z³ − 2z + 2 ma przyciągające cykle 2-okresowe, które na stałe wychwytują niektóre trajektorie.

Granice basenów metody Newtona są zbiorami Julii dla odwzorowania wymiernego N(z) = z − f(z)/f′(z). Zbiór Mandelbrota parametryzuje, które zbiory Julii są spójne, a które całkowicie niespójne. Fraktale Newtona to specjalna rodzina zbiorów Julii, w której odwzorowanie wymierne pochodzi z iteracji Newtona. Bogata struktura granicy widoczna tutaj — z przeliczalnie wieloma „płatami” i nieskończoną rekurencją — jest bezpośrednią konsekwencją tej samej teorii dynamiki zespolonej, która tworzy zbiór Mandelbrota.