Matjas
pijak
Dołączył: 24 Maj 2006
Posty: 225
Przeczytał: 0 tematów
|
Wysłany: Sob 19:11, 20 Paź 2007 Temat postu: |
|
|
Dla przypomnienia definicja:
Kod: | Niech f, g : X -> Y będą ciągłe.
Ciągłe odwzorowanie H : X x [0,1] -> Y takie, że dla dowolnego x:
1) H(x,0) = f(x)
2) H(x,1) = g(x)
nazywamy homotopią f i g |
Istotą ciągłości jest to, że niewielka zmiana argumentu powoduje niewielką zmianę wartości funkcji. Zatem niewielka zmiana argumentu t niewiele zmieni H(x,t).
Spostrzeżenia, które uzasadniają metodę:
1) skoro dla t1 i t2 „bliskich” funkcje H(٠, t1) i H(٠, t2) są do siebie „podobne”, to ich miejsca zerowe leżą „blisko siebie” (Są to funkcje zmiennej x! t1 i t2 są parametrami. Jeśli x1 jest miejscem zerowym H(٠, t1), to miejsce zerowe H(٠, t2) zapewne znajduje się stosunkowo blisko x1).
2) dla f i g ciągłych homotopią jest dla przykładu:
H(x,t) = t f(x) + (1 - t) g(x)
3) dla funkcji i(x) = f(x) – f(0) miejscem zerowym niewątpliwie jest x = 0.
Metoda wygląda teraz tak:
Rozważamy homotopię: H(x,t) = t f(x) + (1 - t) (f(x) – f(0))= f(x) + (1 - t) f(0)
a = 0
for t = 0 by 0.001 to 1
{znajdź miejsce zerowe H(t,x) metodą Newtona przyjmując jako punkt startowy a; wynik podstaw do a}
Po wykonaniu tej pętli a przechowuje miejsce zerowe f. Po co to wszystko? Mianowicie w metodzie Newtona mamy ten problem, że nie wiemy, który punkt wybrać jako początkowy do iteracji. Tutaj zaś mamy: H(x,0) = f(x) – f(0), czyli miejsce zerowe jakiejś funkcji (dość silnie związanej z naszą) dostajemy gratis. Skoro tak, to teraz "lekko" zmieniamy rozważaną funkcję na H(x,0.001). Zapuszczamy Newtona i znajdując miejsce zerowe H(x,0.001) przesuwamy się lekko w stronę miejsca zerowego f(x). I tak małymi kroczkami docieramy wreszcie do miejsca zerowego f(x) (przypominam, że w naszym przykładzie H(x,1) = f(x)).
W zadaniu problemem jest to, że rozważana funkcja jest z R^2 w R^2. To z kolei komplikuje metodę Newtona, mamy bowiem wzór:
x_n+1 = x_n - [Df]^-1*f(x)
gdzie x_n+1 jest wektorem, x_n też, a Df jest macierzą pochodnej! f(x) jest również wektorem. Sugeruję więc napisać sobie klasę vector do obsługi wektorów dwuwymiarowych, klasę matrix do obsługi macierzy (w tym odwracania) i tym się bawić.
A o kolejnych zadaniach wcale nie marzę, więc jak dla mnie brak wiadomości o nowych zadaniach to dobra wiadomość :)
P.S. W poniedziałek mam seminarium SeMPowe o tej metodzie, więc drogie Sempy, nie zdziwcie się, jak zobaczycie część powyższych notatek :)
|
|