Metody numeryczne: separacja pierwiastkow

Matma / Metody numeryczne: separacja pierwiastkow

Autor	Wiadomość
Pawel F. Gora	Posted: 29 Mar 2000 10:04:08 Dana jest funkcja f(x) okreslona na zbiorze liczb rzeczywistych za pomoca znakow sumy, odejmowania, mnozenia, dzielonia, potegowania i funkcji podstawowych np. f(x)=sin(x)+4ln(x)/arctan(5x). W jaki sposob, o jezeli jest to mozliwe, mozna algebraicznie okreslic przedzialy, w ktorych moga znajdowac sie pierwiastki. Chcę brzmieć na tyle autorytatywnie, na ile to możliwe: NIE MA takiej uniwersalnej metody. Ba, można wymyślać różne patologiczne przykłady funkcji, które oszukają każdy znany algorytm praktyczny, łącznie z metodą "narysuj wykres" - bo funkcja gładka, zmieniająca się wolno, może mieć bardzo wąski pik, w obrębie którego może przejść przez zero. Robisz wykres z krokiem 0.001, a tu szerokośc piku jest 10^{-6}. Albo 10^{-20}. Ogólnie rzecz biorąc, problem numerycznego rozwiązywania algebraicznych równań nieliniowych jest bardzo złożony i nie ma nań uniwersalnych metod. Na ogół zadawalamy się znalezieniem _jednego_ pierwiastka równania, rzadko bowiem w ogóle wiemy ile pierwiastków dane równanie posiada. Wyjątkiem są równania wielomianowe, gdzie mamy bardzo silne narzędzie analityczne (podstawowe twierdzenie algebry), dlatego też znane i stosowane są efektywne algorytmy numerycznego szukania wszystkich pierwiastków równań wielomianowych (dla wielomianów niezbyt wysokich stopni rzecz jasna). aby mozna bylo w nim dana funkcje aproksymowac wielomianowo Trochę na inny temat - proszę jednak zwrócić uwagę, że aproksymacja wielomianowa nie jest najlepsza; ZNACZNIE lepsza jest aproksymacja funkcjami wymiernymi. Paweł Góra Institute of Physics, Jagellonian University, Cracow, Poland A physical entity does not do what it does because it is what it is, but is what it is because it does what it does.
Andrzej Lewandowski	Posted: 26 Mar 2000 16:47:58 On Wed, 29 Mar 2000 12:04:08 +0200, "Pawel F. Gora" Dana jest funkcja f(x) okreslona na zbiorze liczb rzeczywistych za pomoca znakow sumy, odejmowania, mnozenia, dzielonia, potegowania i funkcji podstawowych np. f(x)=sin(x)+4ln(x)/arctan(5x). W jaki sposob, o jezeli jest to mozliwe, mozna algebraicznie okreslic przedzialy, w ktorych moga znajdowac sie pierwiastki. [...] Ogólnie rzecz bior?c, problem numerycznego rozwi?zywania algebraicznych równa? nieliniowych jest bardzo z?o?ony i nie ma na? uniwersalnych metod. Na ogó? zadawalamy si? znalezieniem _jednego_ pierwiastka równania, rzadko bowiem w ogóle wiemy ile pierwiastków dane równanie posiada. Wyj?tkiem s? równania wielomianowe, gdzie mamy bardzo silne narz?dzie analityczne (podstawowe twierdzenie algebry), dlatego te? znane i stosowane s? efektywne algorytmy numerycznego szukania wszystkich pierwiastków równa? wielomianowych (dla wielomianów niezbyt wysokich stopni rzecz jasna). Niekoniecznie "niezbyt wyslokich stopni". Pogardzany przez Pana Jakubasa kalkulator TI 89 znajbuje bez problemu pierwiastki rownania 50 stopnia. Nie dziwota zreszta - ten kalkulator implementuje podzbior systemu MAPLE ktory to system jest w takich rzeczach dosyc dobry. Tak na marginesie, stopien wielomianu nie decyduje o trudnosciach znalezienia rozwiazania, a raczej uwarunkowanie pierwiastkow. Poczytac mozna na ten temat w dawno juz wydanej (po polsku rowniez) ksiazce Willkinsona "Bledy zaokraglen w procesach algebraicznych". Wiecej zas w ksiazce tegoz Willkinsona "The Algebraic Eigenvalue Problem". Podstawowe twierdzenie algebry jest dobre ale niekonstruktywne, szczegolnie jak ktos chce np. znalezc tylko rzeczywiste pierwiastki. Jest wiele metod ktore umozliwiaja lokalizacje pierwiastkow wielomianu. Przeglad mozna znalezc w ksiazce (tez dawno wydanej) Turowicza "Geometria zer wielomianow". aby mozna bylo w nim dana funkcje aproksymowac wielomianowo Troch? na inny temat - prosz? jednak zwróci? uwag?, ?e aproksymacja wielomianowa nie jest najlepsza; ZNACZNIE lepsza jest aproksymacja funkcjami wymiernymi. "Lepsza" pod jakim wzgledem?... Calkiem dobra jest aproksymacja splajnami, czyli funkcjami odcinkowo-wielomianowymi (ktos wymuslil na splajny polskie okreslenie "funkcje sklejane". Ciekawe czy sie przyjelo?..) A.L.
Marian Otremba	Posted: 29 Mar 2000 16:22:38 "Pawel F. Gora" napisał: W jaki sposob, o jezeli jest to mozliwe, mozna algebraicznie okreslic przedzialy, w ktorych moga znajdowac sie pierwiastki. NIE MA takiej uniwersalnej metody. Ba, można wymyślać różne patologiczne przykłady funkcji, które oszukają każdy znany algorytm praktyczny, łącznie z metodą "narysuj wykres"- bo funkcja gładka, zmieniająca się wolno, może mieć bardzo wąski pik, w obrębie którego może przejść przez zero. Robisz wykres z krokiem 0.001, a tu szerokośc piku jest 10^{-6}. Albo 10^{-20}. Calkowicie zgadzam się, że nie ma uniwersalnej metody. Jednak gdy nie będziemy mechanicznie stosowac algorytmów to znajdzie się sposób na znalezienie perwiastków w takiej sytuacji np zmiana punktu startowego lub zmiana metody szukania pierwiastka Na ogół zadawalamy się znalezieniem _jednego_ pierwiastka równania, rzadko bowiem w ogóle wiemy ile pierwiastków dane równanie posiada. Sądzę, że znacznie cześciej istnieje potrzeba znalezienia wszystkich pierwiastków i stąd zasadne jest zainteresowanie Krzysztofa przedziałem, w którym znajdują się pierwiastki. Odpowiedź Pawła, że nie ma takiej ogólnej metody jest niestety prawdziwa. Ze swej strony dodałbym - trzeba probować dalej i dalej (większy zakres). Pomocniczymi informacjami będą wartości I i II pochodnej. Wracając do przykładu Krzysztofa f(x)=sin(x)+4ln(x)/arctan(5x) to jest to problem bardzo łatwy bo ma tylko 1 pierwiastek. Ale gdy zmodyfikujemy ją nieco f1(x)=3sin(x)+ln(x)/arctan(5x) to pierwiastków nagle jest trzydzieści i pięć marian otremba
Eugeniusz Jakubas	Posted: 30 Mar 2000 23:20:30 On Wed, 29 Mar 2000 12:04:08 +0200, "Pawel F. Gora" Dana jest funkcja f(x) okreslona na zbiorze liczb rzeczywistych za pomoca znakow sumy, odejmowania, mnozenia, dzielonia, potegowania i funkcji podstawowych np. f(x)=sin(x)+4ln(x)/arctan(5x). W jaki sposob, o jezeli jest to mozliwe, mozna algebraicznie okreslic przedzialy, w ktorych moga znajdowac sie pierwiastki. [...] ...kalkulator TI 89 znajduje bez problemu pierwiastki rownania 50 stopnia. Nie dziwota zreszta - ten kalkulator implementuje podzbior systemu MAPLE ktory to system jest w takich rzeczach dosyc dobry. A.L. ---------------------------------------- Wezmy wiec rownanie: x^14-x^13+x^12-1=0. Kalkulator TI 89 metoda APPROXIMATE daje pierwiastki x=-5.2666178657, x=1.26318846, zas metoda AUTO x=-0.91879482, x=1. Wezmy inne rownanie: ln(x/3-4sin(x))-ln(cos(x+1))=0. Metoda APPROXIMATE otrzymujemy pierwiastek x=-0.189092882481, zas metoda AUTO pierwiastki x=8.22804, x=6.9168, x=2.6887, x=-0.189092, x=-2.99427. Dlaczego w wynikach taka niezgodnosc? Czy tak musi byc? System MAPLE moze jest dosyc dobry, ale jego okrojony podzbior w kalkulatorze moze juz taki nie byc. Nie wierze, aby system MAPLE uruchomiony na komputerze dal taka roznorodnosc wynikow. Niestety nie moge tego sprawdzic bo nie mam tego systemu. Gdybys mogl to sprawdzic i podac wyniki bardzo by mi to pomoglo w zrozumieniu wielu rzeczy. Pozdrawiam. Eugeniusz Jakubas
Andrzej Lewandowski	Posted: 27 Mar 2000 04:34:37 On Thu, 30 Mar 2000 23:20:30 GMT, "Eugeniusz Jakubas" ---------------------------------------- Wezmy wiec rownanie: x^14-x^13+x^12-1=0. Kalkulator TI 89 metoda APPROXIMATE daje pierwiastki x=-5.2666178657, x=1.26318846, zas metoda AUTO x=-0.91879482, x=1. Wezmy inne rownanie: ln(x/3-4sin(x))-ln(cos(x+1))=0. Metoda APPROXIMATE otrzymujemy pierwiastek x=-0.189092882481, zas metoda AUTO pierwiastki x=8.22804, x=6.9168, x=2.6887, x=-0.189092, x=-2.99427. Dlaczego w wynikach taka niezgodnosc? Czy tak musi byc? System MAPLE moze jest dosyc dobry, ale jego okrojony podzbior w kalkulatorze moze juz taki nie byc. Nie wierze, aby system MAPLE uruchomiony na komputerze dal taka roznorodnosc wynikow. Niestety nie moge tego sprawdzic bo nie mam tego systemu. Gdybys mogl to sprawdzic i podac wyniki bardzo by mi to pomoglo w zrozumieniu wielu rzeczy. Niestety, nie mam pod reka MAPLE a tylko REDUCE, i to starozytna, DOSowa wersje. REDUCE znajduje takie same pierwiastki jak TI 89 w modzie AUTO. W modzie APPROXIMATE pierwiastki poszukiwane sa "czysto numerycznie". W modzie AUTO pierwiastki poszukiwane sa analitycznie, z tym ze wspolczynniki zbyt skomplikowane aby je przestawic analitycznie przeksztalcane sa do postaci zmiennoprzecinkowej. W modzie EXACT obliczenia sa prowadzone calkowicie analitycznie. Niestety, TI 89 jest za slaby aby ten wielomian rozwiazac calkowicie w modzie EXACT (starozytna REDUCE zreszta tez - DOS ma za malo pamieci). W modzie APPROXIMATE daje o sobie znac uwarunkowanie pierwiastkow i bledy zaokraglen. TI 89 mowi o tym bez bicia: na dole ukazuje sie napis "questionable accuracy" sugerujacy ze otrzymane wyniki moga byc obarczone bledem. Instrukcja TI 89 mowi zreszta ze nie sa to pierwiastki, a "kandydaci do bycia pierwiastkami". I rzeczywiscie, mozne je wykorzystac jako punkty startowe do procedury solve. Gdy tak zrobimy, dostaniemy rzeczywiste pierwiastki takie jak w modzie EXACT. Niestety, TI 89 nie dostarcza narzedzi do poprawiania dokladnosci czynnikow kwadratowych (czyli poprawiania dokladnosci pierwiastkow zespolonych). Przynajmniej nic mi o tym nie wiadomo. Algorytm uzyty w modzie EXACT i AUTO oparty jest o twor zwany "baza Groebnera". Jest to dosyc hermetyczna galaz matematyki, ale za to dostarczajaca bardzo mocnych narzedzi do obliczen symbolicznych. Podsumowujac: mod AUTO jest dla obliczen najlepszy, albowiem tam gdzie sie da ( i gdzie sa odpowiednie algorytmy) obliczenia mumeryczne wspomagane sa przez obliczenia symboliczne. A.L.


° Forum ° Rejestracja ° Szukaj °