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

Zastosowanie

Fundamentalnym problemem w CAD jest sprawne wyliczanie wszystkich rozwiązań układu równań wielomianowych wewnątrz pewnej skończonej dziedziny.

Problem taki możemy zaobserwować w wielu różnych aplikacjach. Dla przykładu w CAD jest to często niezbędne do identyfikacji wszystkich charakterystycznych punktów krzywej przecięcia między dwoma powierzchniami, ażeby móc śledzić wszystkie gałęzie krzywej. W przeważającej większości wypadków płaszczyzny są przynajmniej kawałkami wielomianowe, musimy zatem rozwiązać układ nieliniowych (ale wielomianowych ) równań aby zidentyfikować te punkty.

Podobne problemy powstają również w planowaniu ruchów robotów, obliczaniu odległości funkcji i ekstremów, wyznaczaniu dokładnej odległości między poruszającymi się bryłami ( ślizganie się brył, wykluczanie kolizji ) oraz w wielu innych zastosowaniach CAD/CAM.

Przegląd rozwiązań

W wielu pracach badawczych z dziedziny CAD faworyzowane są trzy klasy metod do obliczania układów nieliniowych wielomianowych: technika algebraiczna , homotopia i podpodział . Metody te mogą być zaklasyfikowane jako globalne , ponieważ są przeznaczone do obliczania wszystkich pierwiastków w pewnych interesujących zakresach.

Istnieje również pewna liczba lokalnych technik numerycznych , używających niektórych wariacji iteracji Newtona – Raphsona lub numerycznej optymizacji . Metody te są bardzo dokładne i wydajne ( zbieżność kwadratowa ), mają jednak tą wadę, że wymagają dobrego przybliżenia początkowego pierwiastka oraz nie dają pewności znalezienia wszystkich pierwiastków. Przybliżenia początkowe uzyskiwane są zwykle poprzez niektóre rodzaje poszukiwań globalnych. Dobre wyniki daje połączenie metod globalnych i lokalnych. Taki hybrydowy algorytm przy szukaniu pierwiastka korzysta początkowo z metody globalnej dając początkowe przybliżenia pierwiastka, następnie znajduje dokładny pierwiastek za pomocą metody lokalnej – np. metody Newtona.

Przejrzyjmy się krótko trzem klasom metod globalnych:

Metody używające baz Gröbnera – klasa metod korzystająca z techniki geometrii algebraicznej umożliwiająca obliczenie wszystkich zespolonych pierwiastków układu równań wielomianowych. Metody te mają wiele zalet: są eleganckie, gwarantują znalezienie wszystkich zespolonych pierwiastków układu niezależnie od wymiaru zbioru rozwiązań i dobrze dostosowują się do implementacji symbolicznej. Niestety, ich wadą jest numeryczna niestabilność, która utrudnia implementację w arytmetyce zmiennopozycyjnej. Co więcej – są niewydajne, jeżeli chodzi o wykorzystanie czasu procesora i pamięci, co czyni je nieatrakcyjnymi dla wielu zastosowań. Za to często dają nam o wiele więcej informacji niż my potrzebujemy: wiele aplikacji CAD nie wymaga znalezienia wszystkich pierwiastków, a wyłącznie tych, które leżą w pewnym rzeczywistym n-boksie.

Drugą kategorią metod jest klasa technik homotopii (Garcia & Zangwill -[5]) Metody te mogą być użyte do znalezienia wszystkich zespolonych rozwiązań układów wielomianowych, jeżeli ilość pierwiastków jest skończona.

Niestety, przy bliższym przyjrzeniu, okazują się również numerycznie źle uwarunkowane. Jeśli będziemy chcieli obejść ten problemu przez implementację algorytmu w dokładnej arytmetyce wymiernej, skończy się to ogromnymi wymaganiami pamięci. Metoda homotopii, podobnie jak technika geometrii algebraicznej, dostarcza wiele informacji, których nie potrzebujemy.

Trzecią klasą są metody oparte na podpodziale . Należą do niej m.in. algorytmy PP i LP opisane przez Sherbrooke i Patrikalakisa w [15]. Techniki podpodziału bywają również często używane w rozmaitych problemach przecinania w modelowaniu geometrycznym.

Sederberg [13] rozwija adaptatywny algorytm podpodziału, który może być użyty do przecinania dwóch “planarnych” algebraicznych krzywych wyrażonych w barycentrycznych bazach Bernsteina .

Patrikalakis , Prakash i Kriezis badają użycie podpodziału krzywych algebraicznych w zastosowaniu do przecinania algebraicznych powierzchni implicite z wymierną powierzchnią wielomianową. Ich metoda polega na obliczaniu rzeczywistych punktów charakterystycznych krzywej algebraicznej reprezentowanej w bazach Bernsteina, co zwykle pociąga za sobą liczenie przecinania się dwóch lub trzech krzywych algebraicznych przez powtarzający się podpodział i minimizację . Minimizacja została użyta do zwiększenia precyzji wyliczania pierwiastków (wykazuje zbieżność kwadratową ); alternatywnie, do “oczyszczenia” pierwiastka. może być użyta iteracja Newtona-Raphsona, która jest również kwadratowo zbieżna.

Nishita [10] rozwija adaptatywną technikę podpodziału znaną jako “Bezier Clipping” do przecinania promieni z przyciętym płatkiem wielomianowym – również przekształcił problem do przecinania się dwóch krzywych algebraicznych wyrażonych w Bazach Bernsteina. Sederberg i Nishita [14] rozszerzyli tę metodę do przecinania krzywych parametrycznych z płaszczyzną parametryczną.

Należy zauważyć, że technika podpodziału ma kilka wad. Po pierwsze – nie są tak ogólne jak metody algebraiczne, ponieważ są przeznaczone do wyznaczania zero-wymiarowego zbioru rozwiązań wewnątrz n-wymiarowego podzbioru przestrzeni euklidesowej ; co więcej, mimo że szanse, że wszystkie pierwiastki zostaną znalezione zwiększają się, gdy tolerancja rozdzielczości jest zmniejszana , nie ma całkowitej pewności że wszystkie pierwiastki zostaną znalezione – w przypadku, gdy znajdują się bardzo blisko siebie .

Na koniec technika podpodziału nie dostarcza jawnych informacji na temat wielokrotności pierwiastków bez dodatkowych obliczeń.

Mimo tych przeszkód, prędkość i stabilność tych metod czyni je atrakcyjnymi dla wielu zadań, gdzie mamy do czynienia ze znajdowaniem pierwiastków.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *