algorytm.org

Fraktale Newtona

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Fraktale Newtona
Ocena użytkowników:***** / 4
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 19 stycznia 2009 19:41

Niech będzie dane równanie w(z) = 0. Do obliczenia pierwiastków takiego równania możemy użyć metody Newtona, która pozwala obliczać kolejne przybliżenia rozwiązania z0, z1, z2, ... według następującego wzoru:
z_0 = p\\\\ z_{n+1} = z_n - \frac{w(z_n)}{w'(z_n)}
gdzie p jest początkowym przybliżeniem rozwiązania.

Zmieniając wartość punktu startowego p, znajdziemy różne rozwiązania takiego równania. W zależności też od jego wartości będziemy przybliżać się do rozwiązania z różną prędkością.

Fraktale Newtona otrzymuje się obliczając przybliżenia danego równania w dla kolejnych punktów p na płaszczyźnie zespolonej. Przybliżenia te oblicza się tak długo, aż spełnimy jeden z dwóch warunków:
  • zbliżymy się wystarczająco do rozwiązania: | zn+1 - zn | < d, gdzie jako wartość graniczną d przyjmuje się z reguły 0.01 lub mniej,
  • bądź osiągniemy maksymalną liczbę iteracji - wówczas oznacza to, że dany punkt p nie prowadzi do żadnego rozwiązania.


Zatem funkcję obliczającą z jaką prędkością dany punkt p dąży do rozwiązania możemy zdefiniować następująco (gdzie maxIter to maksymalna liczba iteracji jaką chcemy poświęcić na szukanie pierwiastka):

predkosc(p)
begin
  iter := 0;
  z := p;

  repeat
     iter := iter + 1;
     zp := z;
     z = z - ( W(z) / w'(z) );
  until (|zp - z| ≥ d) and (iter < maxIter)

  predkosc = iter;
end;

Przy czym należy zauważyć, że im mniejsza wartość zwrócona przez powyższą funkcję tym szybciej z danego punktu zbliżamy się do rozwiązania. Wartość równa maxIter oznacza, iż z danego punktu nie udało się dojść do żadnego z potencjalnych rozwiązań.

Punkty te następnie oznacza się różnym kolorem na dwa sposoby:
  • prędkość znalezienia rozwiązania,
  • rozwiązanie, do którego dąży dany punkt.


Przypomnijmy jeszcze działania na liczbach zespolonych jakie będziemy potrzebować podczas obliczeń. Liczba zespolona z składa się z części rzeczywistej zr oraz części urojonej zi, czyli
z = z_{r} + iz_{i}
Dodawanie definiujemy następująco:
a + b = (a_r + b_r) + i(a_i + b_i)
Odejmowanie definiujemy następująco:
a - b = (a_r - b_r) + i(a_i - b_i)
Mnożenie definiujemy następująco:
a * b = (a_r*b_r - a_i*b_i) + i(a_r*b_i + a_i*b_r)
Dzielenie definiujemy następująco:
\frac{a}{b} = \frac{a_r*b_r + a_i*b_i}{b_r*b_r + b_i*b_i} + i\frac{a_i*b_r - a_r*b_i}{b_r*b_r + b_i*b_i}
Moduł z liczby zespolonej definiujemy następująco:
|z|=\sqrt{z_{r}^{2}+z_{i}^{2}}
dlatego też w praktyce warunek |z| < d zastępuje się równoważną nierównością
z_{r}^{2}+z_{i}^{2} < 4
Pozbywamy się tutaj czasochłonnego obliczania pierwiastka kwadratowego.

Dla kolejnych punktów na płaszczyźnie, obliczamy przybliżenia rozwiązania równania zgodnie z podanym algorytmem i wzorami. Oś X oznacza wartości reczywiste, natomiast os Y wartości urojone. Przedstawiając prędkości zbliżania się do rozwiązania w(z) = z3 - 1 = 0 na płaszczyźnie (lewy górny róg ma współrzędne -1.5 + -1.5i, dolny prawy róg ma współrzędne 1.5 + 1.5i) i oznaczając je różnymi kolorami otrzymujemy wynik następujący wynik. Na obrazie poniżej kolory prędkości wyznaczono zgodnie z modelem HSV, ale można też użyć do tego celu odcieni szarości, bądź innego modelu barw.
Fraktal Newtona


Natomiast oznaczając różnymi kolorami rozwiązanie do którego prowadzi dany punkt otrzymamy zbiory przyciągania rozwiązania. Dla tego samego równania i tych samych współrzędnych co powyżej otrzymamy następujący wynik.
Fraktal Newtona


Wzór na podstawie, którego oblicza się kolejne przybliżenia rozwiązania można zmodyfikować następująco otrzymując Uogólniony Fratkal Newtona:
z_0 = p\\\\ z_{n+1} = z_n - a * \frac{w(z_n)}{w'(z_n)}
gdzie: p jest początkowym przybliżeniem rozwiązania,
a jest pewną stałą zespoloną, przy czym dla wartości większych od 1 + i0, potrzebna jest większa liczba iteracji by dojść do rozwiązania.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 1
Tomasz LubińskiC/C++Borland Builder 6
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 sierpnia 2012 18:56
Dodaj komentarz