Praca magisterka – wstęp

Witam na moim nowym blogu. Zaprezentuję tu swoją pracę dyplomową

POLITECHNIKA WARSZAWSKA
Wydział Fizyki Technicznej i Matematyki Stosowanej

PRACA DYPLOMOWA

Wykonujący: Andrzej Borucki
temat:
Ocena przydatności metod eliminacji do
rozwiązywania układów równań wielomianowych

Praca została wykonana pod kierunkiem
prof. dr hab. Krzysztofa Marciniaka

Warszawa 1997

Wstęp

Czytaj dalej Praca magisterka – wstęp

Rozdział 2 – Wprowadzenie – 1/2 Krzywe Beziera

Wprowadzenie

Opis problemu

Zajmę się tutaj metodą rozwiązywania układu równań wielomianowych w 2 wymiarowej dziedzinie – trójkącie. Rozwiązywanie takich układów równań jest potrzebne m.in. gdy chcę znaleźć punkt przecięcia dwóch krzywych parametrycznych – należy wtedy odjąć odpowiadające sobie funkcje jednej krzywej od funkcji drugiej krzywej i poszukiwać punktu (0,0). Zakładam, że wierzchołki trójkąta w którym poszukuję rozwiązań mają współrzędne: (0,0),(0,1),(1,0). Nie zmniejsza to w niczym ogólności metody – inną dziedzinę należy przeskalować. Skalowanie dziedziny odbywa się poprzez podstawienie: zamiast $f(x,y)$ mamy $f(x’,y’) $,

gdzie: $x’ = a*x+b; y’ = c*x+d$

Rozwiązanie układu dwóch równań wielomianowych z dwiema niewiadomymi jest równoważne znalezieniu wszystkich wspólnych pierwiastków dwóch funkcji wielomianowych.
Czytaj dalej Rozdział 2 – Wprowadzenie – 1/2 Krzywe Beziera

Rozdział 2 – Wprowadzenie – 2/2 Trójkąty Beziera

Trójkąty Beziera

Współrzędne barycentryczne

Jako pierwszy współrzędne barycentryczne wprowadził Moebius w 1827 roku.
definicja:
Niech T będzie trójkątem z wierzchołkami A,B,C w płaszczyźnie uv. Dowolny punkt $P \in T$ można wyrazić jednoznacznie jako kombinację liniową wierzchołków tego trójkąta P=rA+sB+tC ; dodatkowo, aby była to kombinacja barycentryczna wymaga się aby r+s+t=1. Współczynniki r,s,t noszą nazwę współrzędnych barycentrycznych punktu P w zależności od A, B i C. Dla punktu należącego do trójkąta są spełnione własności :
$r \in [0,1], s \in [0,1], t \in [0,1]$
Uwaga:
Będę często przestawał rozróżniać między punktem a jego współrzędnymi barycentrycznymi – będę mówił po prostu o “punkcie (r,s,t)”
Czytaj dalej Rozdział 2 – Wprowadzenie – 2/2 Trójkąty Beziera

Rozdział 3 – Metoda podpodziału – 1/2

Metoda podpodziału

Szukanie pierwiastków metodą bisekcji

Mamy dane funkcje wielomianowe dwóch zmiennych : $f_1$ i $f_2$ .Należy przedstawić je w bazie Bernsteina. Otrzymamy dwie funkcje na trójkącie T. Funkcje te można przedstawić za pomocą siatki dwuwymiarowych punktów kontrolnych trójkątnego płatka Beziera:

$
P_{i,j,k} =
\begin{vmatrix}
f_{1_{i,j,k}}\\
f_{2_{i,j,k}}
\end{vmatrix}
$
gdzie
$
\begin{matrix}
0\leqslant i,j,k\\
i+j+k=n
\end{matrix}
$

Należy znaleźć takie punkty, dla których obie funkcje osiągają zero. Szukanie odbywa się za pomocą podziału podejrzanych trójkątów za pomocą algorytmu de Casteljau. Punkt podziału trójkąta wybieramy na najdłuższej krawędzi, w ten sposób mamy pewność, że średnica trójkątów będzie się zmniejszała; w przeciwnym razie powstawałyby coraz cieńsze trójkąty, których pole dążyłoby do zera, ale ich średnica pozostawałaby cały czas duża.
Czytaj dalej Rozdział 3 – Metoda podpodziału – 1/2

Rozdział 3 – Metoda podpodziału – 2/2

Metoda płaszczyzn ograniczających

Metodę płaszczyzn ograniczających stosujemy do ograniczenia obszaru podejrzewanego o istnienie pierwiastków. Jeżeli mamy daną funkcję $f_1$ na trójkącie A,B,C , wtedy dla punktów A,B,C funkcja przyjmuje wartości równe wartościom węzłów w tych punktach. Definiujemy płaszczyznę $Z_0$, która przechodzi przez te trzy punkty. Oprócz tego określamy dwie płaszczyzny $Z_g$ i $Z_d$, które są równoległe do $Z_0$ , przy czym pomiędzy $Z_g$ i $Z_d$ mieszczą się wartości wszystkich punktów kontrolnych funkcji na trójkącie. Oznacza to, że między płaszczyznami mieści się pokrycie wypukłe funkcji, a z własności pokrycia wypukłego mamy pewność że wszystkie wartości funkcji mieszczą się pomiędzy tymi płaszczyznami.
Czytaj dalej Rozdział 3 – Metoda podpodziału – 2/2

Rozdział 4 – Testy i podsumowanie

Testy i podsumowanie

Porównuję metodę podpodziału opisaną wcześniej z algorytmami wykorzystującymi metodę płaszczyzn ograniczających i metodę Newtona.

Metoda płaszczyzn ograniczających

  1. Liczymy równoległobok, w którym muszą znajdować się pierwiastki.
  2. Jeżeli równoległobok będzie znajdował się poza trójkątem – oznacza to, że nie ma pierwiastka w dziedzinie – usuwamy trójkąt ze zbioru trójkątów podejrzanych o zawieranie pierwiastka .
  3. Opisujemy równoległobok trójkątem;
  4. Jeżeli trójkąt opisujący nie jest dostatecznie mały (np. ma średnicę większą niż połowa trójkąta bazowego) stosujemy metodę podpodziału i dzielimy trójkąt na cztery. Uwaga – gdyby nie stosować metody podpodziału, nie było by zbieżności w przypadku, gdy w trójkącie znajdowało się kilka pierwiastków
  5. Jeżeli trójkąt opisujący jest dostatecznie mały – zmieniamy dziedzinę funkcji.

Czytaj dalej Rozdział 4 – Testy i podsumowanie

Rozdział 5 – Inne metody

Inne metody

Sherbrooke i Patrikalakis prezentują dwa algorytmy [15] na obliczanie wszystkich pierwiastków układu nieliniowych wielomianowych równań n – zmiennych leżących w n -wymiarowym boksie polegające na reprezentacji w wielomianowych bazach Bernsteina i podpodziale .
Ażeby izolować wszystkie pierwiastki w danej dziedzinie, obie metody używają różnych schematów do konstrukcji ograniczających boksów . Pierwsza metoda rzutuje wielościan na zbiór równorzędnych płaszczyzn, druga używa liniowej optymalizacji.
Badana jest również lokalna zbieżność obu metod i dowód że pierwsza jest kwadratowo zbieżna dla n=1 i liniowo zbieżna dla n>1; druga zaś jest kwadratowo zbieżna dla wszystkich n.
Przypuśćmy, że mamy układ n funkcji n zmiennych $f_1,f_2,..f_n$. Pierwiastków szukamy w n-wymiarowym boksie $S=[a_1,b_1]x[a_2,b_2]x…x[a_n,b_n]$
Mamy znaleźć wszystkie punkty $u=(u_1,u_2,..u_n)$ należące do S takie , że $f_1(u)=f_2(u)=…=f_n(u)=0$
Przez wykorzystanie transformacji afinicznej [4] $ui=a_i+x_i(b_i-a_i)$ dla każdego i od 1 do n uprościmy problem do szukania x należącego do $[0,1]^n$ takiego ,że $f_1(x)=f_2(x)=..=f_n(x)=0$
Ponieważ $f_i$ są wielomianami, wykorzystując zmianę baz można przedstawić je w bazach Bernsteina. Można wykorzystać własność, że płatek Beziera zawiera się w pokryciu wypukłym swoim punktów kontrolnych. Pierwiastki muszą należeć do przecięcia pokrycia wypukłego z płaszczyzną zerową.
Czytaj dalej Rozdział 5 – Inne metody