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.
źródło
Odpowiedzi:
Jeśli korzystasz z Matlaba, możesz wypróbować system Chebfun (zrzeczenie się: Byłem aktywnym programistą tego projektu). Może znaleźć wszystkie korzenie funkcji jednowymiarowej w zamkniętym lub otwartym przedziale, aby uzyskać precyzję maszyny.
Główną ideą narzędzia do znajdowania korzeni Chebfun jest użycie kombinacji bisekcji rekurencyjnej i macierzy kolegi, analogu macierzy towarzyszącej , na współczynnikach interpolacji funkcji celu.
Mam uproszczoną wersję kodu tutaj . Funkcja
chebrootsprzyjmuje anonimową funkcję jako swoje pierwsze wejście, skończony interwał jako drugi i trzeci argument oraz stopieńNjako czwarty i ostatni argument. Aby uzyskać rozsądne wyniki, możesz ustawićNna100.źródło
Ogólnie rzecz biorąc, jest to beznadziejna wyprawa - bez pewnych informacji o ciągłości i / lub zróżnicowaniu funkcji wszystko mogłoby się zdarzyć. Rozważmy na przykład funkcję MATLAB zdefiniowaną w przedziale od 0 do 1:
funkcja y = f (x)
y = 1,0;
jeśli (x == 0,01)
y = 0,0;
koniec
jeśli (x == 0,013)
y = 0,0;
koniec
jeśli (x == 0,753124)
y = 0,0;
koniec
Traktując tę funkcję jako pole bloku, nie ma sposobu, aby zobaczyć, że ma zera w tych trzech punktach i żadnych innych punktów w przedziale od 0 do 1 bez sprawdzania każdej liczby zmiennoprzecinkowej między 0 a 1.
źródło