Jak mogę numerycznie rozróżnić nierównomiernie próbkowaną funkcję?

21

Standardowe wzory różnic skończonych są użyteczne do obliczenia liczbowego pochodnej w oczekiwaniu, że masz wartości funkcji w równomiernie rozmieszczonych punktach, tak że jest stałą. Co się stanie, jeśli mam nierównomiernie rozmieszczone punkty, tak że różni się od jednej pary sąsiednich punktów do następnej? Oczywiście nadal mogę obliczyć pierwszą pochodną jako , ale czy istnieją formuły numerycznego zróżnicowania przy wyższych rzędach i dokładności, które można dostosować do zmian wielkości siatki?h ≡ x k + 1 - x k h f ′ ( x ) ≈ 1f(xk)h≡xk+1−xkhf′(x)≈1hk[f(xk+1)−f(xk)]

finite-difference discretization David Z
źródło
7
Zawsze możesz zbudować (fragmentarycznie) wielomianowy interpolant przechodzący przez punkty, a następnie rozróżnić.
JM
Lub możesz zrekonstruować formuły różnic skończonych bez uproszczenia . Często trzeba to zrobić w celu integracji, ale prawdopodobnie sugestia JM jest bardziej stabilna. h=xk+1−xk
rcollyer,
Co to za funkcja?
mbq,
Przykładem, który wywołał to pytanie, jest funkcja próbkowana przy logarytmicznie rozmieszczonych wartościach , ale obliczenie drugiej pochodnej danych przekształconych logem daje śmieszne wyniki i chciałem to sprawdzić. Poza tym pomyślałem, że zadam tak ogólne pytanie, jak to możliwe. xk=x0δk
David Z
1
Jeśli chodzi o mnie, coś, co działa tylko dla pierwszej i drugiej pochodnej, byłoby idealnie dobrą odpowiedzią na pytanie. Napisałem pytanie tak, jak to zrobiłem, aby umożliwić ogólną odpowiedź, jeśli ktoś ją posiada, ale oczywiście w praktyce najbardziej przydatne są pierwsza i druga pochodna.
David Z

Odpowiedzi:

21

Komentarz JM ma rację: możesz znaleźć interpolujący wielomian i go rozróżnić. Istnieją inne sposoby uzyskiwania takich wzorów; zazwyczaj wszystkie prowadzą do rozwiązania systemu van der Monde dla współczynników. Takie podejście jest problematyczne, gdy szablon różnic skończonych zawiera dużą liczbę punktów, ponieważ matryce Vandermonde stają się źle uwarunkowane. Fornberg opracował bardziej stabilne liczbowo podejście , które wyjaśniono jaśniej i ogólnie w drugiej jego pracy.

Oto prosty skrypt MATLAB, który implementuje metodę Fornberga do obliczania współczynników przybliżenia różnic skończonych dla dowolnej pochodnej rzędu z dowolnym zestawem punktów. Dobre wyjaśnienie znajduje się w rozdziale 1 tekstu LeVeque na temat metod różnic skończonych .

Trochę więcej o formułach FD: Załóżmy, że masz siatkę 1D. Jeśli użyjesz całego zestawu punktów siatki do ustalenia zestawu formuł FD, uzyskana metoda jest równoważna znalezieniu interpolującego wielomianu przez całą siatkę i rozróżnieniu tego. To podejście jest nazywane kolokacją spektralną. Alternatywnie, dla każdego punktu siatki można określić formułę FD, używając tylko kilku sąsiadujących punktów. Tak się dzieje w tradycyjnych metodach różnic skończonych.

Jak wspomniano w komentarzach poniżej, użycie skończonych różnic bardzo wysokiego rzędu może prowadzić do oscylacji (zjawisko Runge), jeśli punkty nie zostaną starannie wybrane.

David Ketcheson
źródło
3
Z drugiej strony, kiedy używasz interpolujących wielomianów, zawsze musisz pamiętać takie rzeczy, jak zjawisko Runge'a, które może się zdarzyć z twoimi danymi, jeśli twoje dane są wystarczająco przewrotnie skonfigurowane. Powiedziałbym, że częściowe wielomiany mogą być mniej podatne na to ...
JM
1
Zastanawiam się, czy prace Koeva i technika Fornberga mogą być powiązane?
David Ketcheson,
1
Co ciekawe, wydaje się, że istnieje podobieństwo między formułami Fornberga a wcześniejszymi formułami opracowanymi przez Lyness i Moler na podstawie klasycznej metody Neville'a do generowania interpolującego wielomianu. W rzeczywistości mogą to być te same formuły w różnych notacjach, ale nie sprawdziłem dokładnie.
JM
2
Interpolacja wielomianowa z wieloma punktami wymaga specjalnego uwarunkowania rozkładów punktów. Zasadniczo w przypadku nierównomiernych rozkładów punktowych nie zaleca się wykonywania interpolacji, a następnie różnicowania wielomianu interpolacyjnego, ponieważ może on być wysoce oscylacyjny (pomyśl „zjawisko Runge” jak wspomniano w JM). W zależności od potrzeb lepszym pomysłem może być użycie splajnów sześciennych, które dla wielu praktycznych celów mogą dostarczyć dobrych odpowiedzi na problem aproksymacji pochodnych aproksymacyjnych.
Allan P. Engsig-Karup,
1
Niezła odpowiedź. Tylko dla informacji, ten dokument przedstawia alternatywne podejście do Fornberga. Kieruje się tą samą zasadą, ale podaje inny algorytm.
davidhigh,
2

Powyższe odpowiedzi są świetne, jeśli chodzi o podanie kodu do użycia, ale nie są tak dobre, jeśli chodzi o teorię. Jeśli chcesz zagłębić się w interpolację wielomianów, spójrz na to teoretyczne traktowanie z kilkoma konkretnymi przykładami:

Singh, Ashok K. i BS Bhadauria. „Wzory różnic skończonych dla nierównych podstępów przy użyciu wzoru interpolacji Lagrange'a”. International Journal of Mathematics and Analysis 3.17 (2009): 815–827. ( Link do pliku PDF )

Autorzy używają interpolacji Lagrangian (patrz artykuł na Wikipedii ) do obliczania wielomianów interpolacyjnych 3-punktowych, 4-punktowych i 5-punktowych, a także ich pierwszej, drugiej i trzeciej pochodnej. Mają także wyrażenia dotyczące błędu obcięcia, co należy wziąć pod uwagę przy stosowaniu dowolnego schematu różnic skończonych. Mają także ogólny wzór do obliczania interpolujących wielomianów za pomocą N punktów.

Wielomian interpolujący Lagrangiana jest użyteczny, ponieważ one i ich pochodne mogą być bardzo dokładne w dziedzinie, w której interpolujesz, i nie zakładają równych odstępów siatki. Ze względu na naturę wielomianów interpolujących Lagrangian nigdy nie możesz mieć więcej rzędów pochodnych niż punktów siatki.

Myślę, że to dobrze odpowiada na twoje pytanie, ponieważ cytowany przeze mnie artykuł ma formuły dla schematów skończonych różnic arbitralnie wysokiego rzędu, które z natury są dla nierównych siatek i są ograniczone tylko liczbą punktów siatki, które są zawarte w szablonie. Artykuł zawiera również ogólną formułę błędu obcięcia, która pomoże ci ocenić wielomian interpolacyjny Lagrangiana względem innych schematów, które możesz wziąć pod uwagę. Praca autora powinna dać takie same wyniki jak metoda Fornberga. Ich wkład polega na zestawieniu kilku przykładów i oszacowaniu błędu, który może okazać się przydatny.

Odkryłem, że zarówno cytowany przeze mnie artykuł, jak i praca Fornberga są przydatne w moich własnych badaniach.

jvriesem
źródło
1
przepraszam, że muszę to stwierdzić, ale cytowane przez ciebie odniesienia wyglądają dziwnie - używają okropnych formuł i rozwiązują tylko kilka specjalnych przypadków. Natomiast Fornberg rozwiązał ogólny problem, podając prosty algorytm już w latach 80-tych. Zobacz tutaj
davidhigh
kolejna praca rozwiązująca ogólny problem jest tutaj
davidhigh
2
i ostatni komentarz, by zlekceważyć ten artykuł. W „doskonałym traktowaniu teoretycznym” nie możesz mieć 9 referencji, z których 7 odnosi się do twojej własnej pracy, a jedna do ogólnej książki do analizy numerycznej. Przynajmniej nie, jeśli sam nie wymyśliłeś tematu, czego nie zrobili ci autorzy.
davidhigh
Masz całkowitą rację. Nie powiedziałbym, że formuły są okropne, choć można je poprawić. Przypadki specjalne są raczej przyjemne jako testy / porównania i podają ogólną formułę, która musi być taka sama jak Fornberga.
jvriesem
1
@jvriesem Należy pamiętać, że cytowany artykuł ma niewłaściwy znak w trzecim semestrze w równaniu. (15b)
Tarek
-4

Najprostszą metodą jest użycie przybliżeń różnic skończonych.

Prostym dwupunktowym oszacowaniem jest obliczenie nachylenia pobliskiej linii siecznej przez punkty (x, f (x)) i (x + h, f (x + h)). [1] Wybór małej liczby h, h oznacza małą zmianę x, i może być dodatnia lub ujemna. Nachylenie tej linii to

f(x+h)−f(x)h

To wyrażenie jest ilorazem różnicy Newtona.

Nachylenie tej siecznej linii różni się od nachylenia linii stycznej o wielkość, która jest w przybliżeniu proporcjonalna do h. Gdy h zbliża się do zera, nachylenie linii siecznej zbliża się do nachylenia linii stycznej. Dlatego prawdziwa pochodna f at x jest granicą wartości ilorazu różnicy, gdy linie sieczne zbliżają się coraz bardziej do bycia linią styczną

evion2011
źródło
1
Wydaje mi się, że nie doceniasz, ponieważ David Zaslavsky specjalnie wspomniał o formule ilorazu różnicy, a pytanie dotyczy tego, czy istnieją jakieś lepsze przybliżenia.
Dan
7
Również dlatego, że jest to bezpośrednie kopiowanie i wklejanie z Wikipedii , z wyjątkiem łącza do spamu, które pierwotnie było częścią odpowiedzi.
David Z