Liczenie asymptoty numerycznie

Hej! Piszę sobie program do rysowania wykresów funkcji. W okienko wpisujemy wzór funkcji, np:

1/(x^2+x)

lub

1/x

i program analizując string'a liczy wartość i rysuje wykresik. A działa to tak: pętelka po 'i' od np. -500 do 500 (wartości argumentów zależą od obecnej szerokości okna), pod 'x' we wzorze podstawiam jakąś tam wartość zależną od szerokości/wysokości, aby wykres zawsze wyglądał cacy. Kolejne punkty odpowiadające wartościom funkcji łącze metodą Canvas.LineTo(). Przy działaniach generujących błąd program pomija te wartości (np. sqr(-1), 1/0). Tyle, że jeśli argument przyrasta o jakieś 0,439 to ominie 0 i wartość skrajnie ujemną (-3214) połączy mi kreską z wartością skrajnie dodatnią (+2349) i asymptota nie będzie widoczna.

W jaki sposób temu zaradzić? Co zrobić, aby asyptota była widoczna na moim wykresie?

napisac program tak, aby przeprowadzal analize wzoru, odnazl krytyczne punkty, wyznaczyl asymptoty i uwzglednial to przy przejezdzaniu -500.500 i rysowaniu..
..a tak na serio - pewnie masz staly krok kroczenia, a krok powiniein byc zmienny.. im szybciej wartosci sie zmieniaja, tym mniejszy. czyli im wieksza wartosci absolutna pochodnej w danym punkcie, tym mniejszy krok z tego punktu dalej..

Zależy też jaką klasę funkcji obejmuje twój analizator, jeżeli tylko funkcje wymierne to nie będzie problemu z obliczeniem asymptot(czyli miejsca zerowe mianownika, oczywiście dla n<5, dla wyższych rzędów nie istnieją wzory składające się ze skończonej kombinacji funkcji elementarnych), problem pojawia się jak będzie to szeroka klasa obejmująca kombinacje funkcji elementarnych. Wtedy do liczenia asymptot będziesz musiał używać metod przybliżonych. Ja już masz punkty asymtotyczne, to jeżeli dwa kolejne punkty w algorytmie aproksymacji leżą po przeciwnej stronie asymptoty wtedy nie łączysz ich linią, w algorytmie dodanie jednego ifa :-D

kaziuuu napisał(a)

czyli miejsca zerowe mianownika, oczywiście dla n<5, dla wyższych rzędów nie istnieją wzory składające się ze skończonej kombinacji funkcji elementarnych

Ale obliczyć z dużą dokładnością zawsze można;
teoretycznie z dowolną dokładnością, a dla wykresu wystarczy kilka cyfr.

Nie zawsze. Tylko jeśli liczysz zespolone miejsca zerowe wielomianu. W dziedzinie liczb rzeczywistych problem jest półrozstrzygalny, bo nie istnieje algorytm numeryczny gwarantujący zbieżność - nie wiesz ile jest miejsc zerowych i w związku z tym nie ma dobrego warunku stopu ;) Jak masz "złośliwy" wielomian to guzik nie policzysz.

Dla dowolnej postaci funkcji problem jest półrozstrzygalny zarówno w dziedzinie rzeczywistej jak i zespolonej.

Krolik napisał(a)

Nie zawsze. Tylko jeśli liczysz zespolone miejsca zerowe wielomianu. W dziedzinie liczb rzeczywistych problem jest półrozstrzygalny, bo nie istnieje algorytm numeryczny gwarantujący zbieżność - nie wiesz ile jest miejsc zerowych i w związku z tym nie ma dobrego warunku stopu ;) Jak masz "złośliwy" wielomian to guzik nie policzysz.

Dla dowolnej postaci funkcji problem jest półrozstrzygalny zarówno w dziedzinie rzeczywistej jak i zespolonej.

Zawsze można obliczyć.
Sam kiedyś robiłem algorytm obliczania pierwiastków dowolnych wielomianów (jednej zmiennej).

Obliczamy pierwiastki kolejno od zera, tz. |z1| <= |z2| <= ... to gwarantuje stabilność.

Używałem tam metody rzędu 3, która operuje od razu na zespolonych,
oraz standardowego typu complex = double,double;
i to wystarczyło, metoda dawała bardzo dobre wyniki, nawet dla bardzo gęsto ustawionych zer.
Precyzję można łatwo zwiększać - zamiast double, tworzymy własny, np. z 4096 bitów... i lecimy w kosmos. :-)

Trzeba osobno uwzględnić pierwiastki wielokrotne, i kilka innych rzeczy.

Przecież napisałem, że można dla wielomianów, jak się przejdzie na dziedzinę zespoloną. Daje to Ci jedynie pewny warunek stopu, ale i tak nadal nie możesz podać 100% gwarancji na czas obliczeń, czyli algorytm może Ci się po prostu nie zakończyć w rozsądnym czasie. Co dla mnie wystarczy, by stwierdzić, że "nie zawsze". 99,99% przypadków, kiedy działa, to nie zawsze.

Krolik napisał(a)

Przecież napisałem, że można dla wielomianów, jak się przejdzie na dziedzinę zespoloną. Daje to Ci jedynie pewny warunek stopu, ale i tak nadal nie możesz podać 100% gwarancji na czas obliczeń, czyli algorytm może Ci się po prostu nie zakończyć w rozsądnym czasie. Co dla mnie wystarczy, by stwierdzić, że "nie zawsze". 99,99% przypadków, kiedy działa, to nie zawsze.

Jest 100%, a czas jest praktycznie zerowy.
Są metody zbieżne globalnie.
Nawet w prostej metodzie Newtona - rzędu 2, otrzymujesz wynik
z dokład. do 15 cyfr zaledwie po kilku iteracjach -
w każdym kroku liczba cyfr dokładnych podwaja się.

Problemy stopu, i inne pojawiają się dopiero w układach równań nieliniowych.

Nigdy nie będziesz 100% pewien, że znalazłeś dokładnie wszystkie pierwiastki rzeczywiste wielomianu st > 5. Rozsądną metodą byłoby znalezienie wszystkich pierwiastków zespolonych - te których część zespolona leży dostatecznie blisko zera można uznać za rzeczywiste.

Tak, masz rację i dlatego to się robi na zespolonych, gdzie nie ma tego problemu. Jestem tylko ciekaw, czy istnieje algorytm, który dla dowolnego wielomianu gwarantuje znalezienie przynajmniej jednego pierwiastka zespolonego w skończonym czasie, nie mając przedtem żadnej informacji o przybliżonych położeniach pierwiastków.

Żeby to udowodnić, trzeba by chyba pokazać, że dla każdego wielomianu istnieje przynajmniej jeden pierwiastek, dla którego obszar zbieżności owego algorytmu jest "nieograniczony przestrzennie". Tzn. mam na myśli, że jeżeli wezmę dowolny obszar płaszczyzny zespolonej o polu powierzchni powiedzmy Pd, to obszar zbieżności o polu Pz w tym obszarze będzie taki, że [lim (Pz / Pd) przy Pd -> nieskonczonosc] > 0.
BTW: Z tego wynika od razu, że wymiar fraktalny tego obszaru musi być równy 2. Dla <2 wspomniana granica wyjdzie zawsze 0. Tyle warunków koniecznych, ale udowodnić lub obalić nie umiem.

Jeśli "za" potrafisz podać konkretny algorytm + dowód zbieżności globalnej (może być link), to bardzo chętnie zajrzę.

Krolik napisał(a)

Tak, masz rację i dlatego to się robi na zespolonych, gdzie nie ma tego problemu. Jestem tylko ciekaw, czy istnieje algorytm, który dla dowolnego wielomianu gwarantuje znalezienie przynajmniej jednego pierwiastka zespolonego w skończonym czasie, nie mając przedtem żadnej informacji o przybliżonych położeniach pierwiastków.

Używałem metody Laguerre'a.
Algorytm znajduje zawsze wszystkie pierwiastki w skończonym czasie -
kilka ms (dla wielomianów stopnia < 100).

Dowodu globalnej zbieżność tej metody ponoć nie ma,
metoda jest dość trudna do analizy.

Dla szczególnie zwyrodniałych przypadków spada dokładność, np.:
1.0000000000001x^{7 - 10000000000000.0x}6 + 0.00000000003x^5 +
dla takich współczynników nie obliczysz dokładnej wartości tego wielomianu,
lub pochodnych. Należałoby obliczać w wyższej precyzji...

Liczbę zer funkcji zmiennej zespolonej, znajdujących się
w dowolnym obszarze można obliczyć z teorii residuów.

Liczbę zer funkcji zmiennej zespolonej, znajdujących się
w dowolnym obszarze można obliczyć z teorii residuów.

Dzięki, to mi wystarcza. Jakoś zapomniałem o tym. Eh, dawno to było ;)