Muszę znaleźć wszystkie pierwiastki funkcji skalarnej w danym przedziale. Funkcja może mieć nieciągłości. Algorytm może mieć dokładność ε (np. Jest ok, jeśli algorytm nie znajdzie dwóch wyraźnych pierwiastków bliższych niż ε).
Czy taki algorytm istnieje? Czy mogłabyś mi o tym napisać?
W rzeczywistości mam funkcję znajdowania zera w danym przedziale za pomocą algorytmu Brenta oraz funkcję znajdowania minimum w danym przedziale. Korzystając z tych dwóch funkcji, zbudowałem własny algorytm, ale zastanawiałem się, czy istnieje lepszy algorytm. Mój algorytm jest taki:
Zaczynam od interwału [a,b]i funkcji f. Jeśli sign(f(a+ε)) ≠ sign(f(b-ε))wiem, że jest co najmniej jedno zero między ai b, i znajduję z = zero(]a,b[). Sprawdzam, czy znaprawdę jest zero (może to być nieciągłość), szukając wartości z-εi z+ε. Jeśli tak, dodaję go do listy znalezionych zer. Jeśli f(a+ε)i f(b-ε)oba są pozytywne, szukam m = min(]a, b[). Jeśli f(m)nadal jest pozytywny, szukam, m = max(]a,b[)ponieważ może istnieć nieciągłość między ai b. Robię coś przeciwnego, jeśli f(a+ε)i f(b-ε)były negatywne.
Teraz, od miejsca, w którym znalazłem ( zlub m) buduję stos zawierający zera, nieciągłości i punkty przegięcia mojej funkcji. Po pierwszej iteracji wygląda teraz stos [a, z, b]. Zaczynam od nowa algorytm od interwałów ]a,z[i ]z,b[. Kiedy między dwoma punktami ai bekstrema ma ten sam znak niż oba końce przedziału i nie ma nieciągłości w obu ekstremie, usuwam interwał ze stosu. Algorytm kończy się, gdy nie ma już interwałów.