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:
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:
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):
Punkty te następnie oznacza się różnym kolorem na dwa sposoby:
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
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.
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.
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:
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.
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.
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.
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
Autor | Język programowania | Komentarz | Otwórz | Pobierz | Ocena |
Tomasz Lubiński | C# | MS Visual Studio .net | .cs | .cs | ***** / 1 |
Tomasz Lubiński | C/C++ | Borland Builder 6 | .cpp | .cpp | ***** / 2 |
Tomasz Lubiński | Delphi/Pascal | Borland Delphi 5 | .pas | .pas | ***** / 1 |
Poprawiony: 27 sierpnia 2012 18:56