Jak znaleźć wszystkie zera funkcji za pomocą numpy (i scipy)?

Question

Załóżmy, że mam funkcję f(x) zdefiniowaną między a i b. Ta funkcja może mieć wiele zer, ale także wiele asymptot. Muszę pobrać wszystkie zera tej funkcji. Jaki jest najlepszy sposób na zrobienie tego?

Faktycznie, moja strategia jest następująca:

1. oceniam moja funkcja w danej liczby punktów
2. wykryć, czy nastąpiła zmiana znaku
3. znajdę zero między punktami które zmieniają się zalogować

4. zweryfikować czy zero znaleźć jest naprawdę zero, lub jeśli jest to asymptota

   U = numpy.linspace(a, b, 100) # evaluate function at 100 different points 
   c = f(U) 
   s = numpy.sign(c) 
   for i in range(100-1): 
       if s[i] + s[i+1] == 0: # oposite signs 
        u = scipy.optimize.brentq(f, U[i], U[i+1]) 
        z = f(u) 
        if numpy.isnan(z) or abs(z) > 1e-3: 
         continue 
        print('found zero at {}'.format(u)) 
   

Algorytm ten wydaje się działać, z wyjątkiem widzę dwa potencjalne problemy:

1. To nie wykryje, że zero nie przechodzi oś X (na przykład, w zależności jak f(x) = x**2) Jednakże, Nie sądzę, aby mogło wystąpić z funkcją, którą oceniam.
2. Jeśli punkty dyskretyzacji są za daleko, może być ich więcej niż jedno, a algorytm może go nie znaleźć.

Czy masz lepszą strategię (wciąż wydajną), aby znaleźć wszystkie zera funkcji?

---

Nie sądzę, że to ważne pytanie, ale dla tych, którzy są ciekawi, mam do czynienia z charakterystycznymi równań propagacji fal w światłowodzie. Funkcja wygląda (gdzie V i ell są wcześniej zdefiniowane, a ell jest dodatnia):

def f(u): 
    w = numpy.sqrt(V**2 - u**2) 

    jl = scipy.special.jn(ell, u) 
    jl1 = scipy.special.jnjn(ell-1, u) 
    kl = scipy.special.jnkn(ell, w) 
    kl1 = scipy.special.jnkn(ell-1, w) 

    return jl/(u*jl1) + kl/(w*kl1) 

Answer 1

Głównym problemem, który widzę z tym, jest fakt, że można rzeczywiście znaleźć wszystkie korzenie --- jak już wspomniano w komentarzach, nie zawsze jest to możliwe. Jeśli jesteś pewien, że twoja funkcja nie jest całkowicie patologiczna (sin(1/x) była już wspomniana), następną jest Twoja tolerancja na brak korzenia lub kilku z nich. Inaczej mówiąc, chodzi o to, do jakiej długości jesteś przygotowany, aby upewnić się, że niczego nie przegapiłeś --- według mojej najlepszej wiedzy, nie ma ogólnej metody wyodrębnienia dla ciebie wszystkich korzeni, więc będziesz musiał Zrób to sam. To, co pokazujesz, jest już rozsądnym pierwszym krokiem. Kilka komentarzy:

• Metoda Brenta jest tu naprawdę dobrym wyborem.
• Przede wszystkim zajmij się rozbieżnościami. Ponieważ w swojej funkcji masz przecinki w mianowniku, możesz najpierw rozwiązać swoje korzenie - lepiej je sprawdzić np. W Abramowiczach i Stegunach (Mathworld link). To będzie lepsze niż użycie siatki ad hoc, z której korzystasz.
• Co możesz zrobić, gdy znajdziesz dwa korzenie lub rozbieżności, x_1 i x_2, ponownie uruchom wyszukiwanie w przedziale [x_1+epsilon, x_2-epsilon]. Kontynuuj, dopóki nie zostaną znalezione żadne korzenie (metoda Brenta zbiegnie się z z korzenia, pod warunkiem że istnieje).
• Jeśli nie możesz wyliczyć wszystkich rozbieżności, możesz być nieco bardziej ostrożny w sprawdzaniu, czy kandydat rzeczywiście jest rozbieżnością: biorąc pod uwagę x, nie sprawdzaj tylko, czy f(x) jest duży, sprawdź, czy np. |f(x-epsilon/2)| > |f(x-epsilon)| dla kilku wartości epsilon (1e-8, 1e-9, 1e-10, coś w tym stylu).
• Jeśli chcesz mieć pewność, że nie masz korzeni, które dotykają tylko zera, poszukaj ekstremum funkcji, a dla każdego ekstremum, x_e, sprawdź wartość f(x_e).

Answer 2

Dlaczego jesteś ograniczony do numpy? Scipy posiada pakiet, który robi dokładnie to, co chcesz:

http://docs.scipy.org/doc/scipy/reference/optimize.nonlin.html

Jedna lekcja nauczyłem: programowanie numeryczne jest trudne, więc nie rób tego :)

---

W każdym razie, jeśli nie jesteś już gotowy do zbudowania algorytmu samemu, strona z dokumentem na scipy I link (trwa wieczność, aby załadować, btw) daje listę algorytmów na początek. Jedną z metod, którą stosowałem wcześniej, jest dyskretyzacja funkcji w stopniu koniecznym dla twojego problemu. (To znaczy, dostrój \ delta x tak, aby był znacznie mniejszy niż rozmiar charakterystyczny dla twojego problemu.) Pozwala ci to szukać funkcji funkcji (takich jak zmiany w znaku). ORAZ można bardzo łatwo obliczyć pochodną segmentu linii (prawdopodobnie od przedszkola), więc twoja dyskretyzowana funkcja ma dobrze zdefiniowaną pierwszą pochodną. Ponieważ dostrojony dx jest mniejszy niż charakterystyczny rozmiar, gwarantujemy, że nie przeoczysz żadnych funkcji funkcji, które są ważne dla twojego problemu.

Jeśli chcesz wiedzieć, co oznacza "wielkość charakterystyczna", poszukaj jakiegoś parametru swojej funkcji za pomocą jednostek długości lub 1/długości. Oznacza to, że dla pewnej funkcji f (x), załóżmy, że x ma jednostki długości, a f nie ma jednostek. Następnie szukaj rzeczy, które mnożą x. Na przykład, jeśli chcesz dyskretyzować cos (\ pi x), parametr mnożący x (jeśli x ma jednostki długości) musi mieć jednostki 1/długość. Zatem charakterystyczny rozmiar cos (\ pi x) wynosi 1/\ pi. Jeśli zmniejszysz dyskrecjację znacznie mniej, nie będziesz mieć żadnych problemów. Oczywiście, ta sztuczka nie zawsze działa, więc możesz potrzebować trochę majsterkowania.