Jaki jest najlepszy sposób na znalezienie nieciągłości funkcji czarnej skrzynki?

20

Zasugerowano, że może to być lepsze miejsce na to pytanie niż Mathematics Stack Exchange, gdzie go wcześniej zadałem .

Załóżmy, że ktoś ma funkcję czarnej skrzynki, którą można ocenić w dowolnym miejscu (tanio) w określonym przedziale i nie ma hałasu (z wyjątkiem ziarnistości zmiennoprzecinkowej, powiedzmy). Jaki byłby najlepszy sposób na znalezienie nieciągłości tej funkcji? Nie wiem, ile może być nieciągłości i może ich nie być. $[a,b]$

Mogę wymyślić kilka prostych metod (jednolite pobieranie próbek, doprecyzowanie, gdzie występują duże różnice między próbkami, ...), ale może jest lepszy sposób?

Funkcja jest „rozsądna”, ponieważ można założyć, że ma ona co najwyżej skończenie wiele nieciągłości, to samo dla wyższych pochodnych, nie mam nic przeciwko, jeśli pominięto małe patologiczne nieciągłości ... (aplikacja jest automatycznym wykreślaniem funkcji 1d) .

-

Dziękujemy wszystkim, którzy odpowiedzieli, szczególnie Pedro; metoda opisana w Pachón, Platte i Trefethen wydaje się być dla mnie najlepszym podejściem, więc idę teraz, aby ją wdrożyć

interpolation signal-processing

— n00b
źródło

Muszę się zastanawiać, czy którakolwiek z proponowanych metod poradzi sobie z

\frac{1}{x} - ⌊ \frac{1}{x} ⌋

$\frac1{x}-\left\lfloor\frac1{x}\right\rfloor$

— JM

@JM: Dodam wykres tej funkcji po zakończeniu implementacji.

— n00b

@ n00b: Ta koncepcja może być przydatna. : mathoverflow.net/q/165038/14414

— Rajesh Dachiraju

18

Jeśli korzystasz z Matlaba, możesz być zainteresowany projektem Chebfun . Chebfun przyjmuje funkcję, pobiera próbki i próbuje przedstawić ją jako interpolant wielomianowy. Jeśli Twoja funkcja ma nieciągłości, Chebfun powinien być w stanie ją wykryć za pomocą splitting onpolecenia. Możesz znaleźć kilka przykładów tutaj .

Jeśli interesują Cię podstawowe algorytmy, dobrym odniesieniem jest artykuł Pachóna , Platte i Trefethena „ Piecewise Smooth Chebfuns ”.

— Pedro
źródło

Dzięki Pedro, znam Chebfun, który jest świetny, ale ogromny (i wiąże się z ogromnymi kosztami ukrytymi dzięki licencji Matlab). Naprawdę szukam małego ścisłego algorytmu dla tego problemu, który sam bym zaimplementował.

— n00b

@ n00b: Dobra uwaga. Dodałem odniesienie do artykułu opisującego podstawowe algorytmy, np. Do wykrywania krawędzi.

— Pedro

Ach, świetnie! Nie widziałem tego artykułu i, wbrew moim oczekiwaniom, wydaje się, że wyszukiwarka nieciągłości Chebfun tak naprawdę nie używa Chebfunów - więc wydaje się, że jest to niezwykle użyteczne. Przeczytam go uważnie i sprawdzę odpowiedni kod ....

— n00b

11

Podejrzewam, że algorytm chebfun musi wydawać się bardziej praktyczny, ale należy wspomnieć o jeszcze jednym sposobie wykrywania nieciągłości, a mianowicie o dyskretnej transformacie falkowej. Możesz dowiedzieć się, jak to działa, przeglądając tę stronę dokumentacji Mathematica , patrz sekcja> Aplikacje> Wykryj nieciągłości i krawędzie.

$f$

— faleichik
źródło

8

Metody ważone zasadniczo nieoscylacyjne (WENO) wykorzystują „wskaźniki gładkości” do wykrywania nieciągłości w metodach o skończonej objętości i różnicy. Z opisu Chebfuna, który podał Pedro, wydaje się, że ogólna idea jest taka sama: skonstruuj zestaw interpolujących wielomianów i użyj ich do obliczenia pewnej miary gładkości.

Patrz GS Jiang i CW Shu, Skuteczne wdrażanie ważonych schematów ENO, J.Comput.Phys., Vol. 126, s. 202--228, 1996.

— Matthew Emmett
źródło

5

Wraz z @Pedro przyjrzałbym się algorytmom wykrywania krawędzi. Nieciągłość jest nieskończonością pochodnej, więc zastanów się nad coraz bardziej drobną siatką i kierowaniem na interesujące regiony.

Przybliżenie skończonej różnicy do pochodnej funkcji ciągłej powinno zmniejszać się w miarę udoskonalania siatki. Porównanie wyniku skończonej różnicy dla pochodnej między siatkami może następnie ujawnić rozbieżności w gradiencie, które sygnalizują nieciągłości.

$f(x) = \mathrm{sign}(x) \sqrt{|x|}$ $x=0$ $h_x \rightarrow 0$

— Phil H.
źródło

1

Jedną z subtelności problemu jest to, że chociaż nieciągłość może być postrzegana jako posiadająca nieskończoność w pochodnej, odwrotność nie jest prawdą - znak funkcji (x) * sqrt (| x |) jest idealnie ciągły przy x = 0, ale pochodna jest tam nieskończona

— n00b

Nie zgadzam się również z komentarzem, że „każda funkcja ciągła powinna być płynna w wystarczająco małej skali”. Gładkość ma związek z ciągłymi pochodnymi; ciągłość pierwotnej funkcji jest warunkiem koniecznym, ale niewystarczającym.

— Geoff Oxberry

1

@GeoffOxberry: usunął tę instrukcję. Jest to rozsądny wynik w FD, ale nie analityczny.

— Phil H