Kiedy interpolacja splajnu sześciennego jest lepsza niż wielomian interpolujący?

Poniższy wątek stanowi niewielką odmianę przykładu z podręcznika. Autor wykorzystał ten przykład, aby zilustrować, że wielomian interpolujący w próbkach o równych odstępach ma duże oscylacje w pobliżu końca przedziału interpolacji. Oczywiście interpolacja splajnu sześciennego daje dobre przybliżenie w całym przedziale. Przez lata uważałem, że należy unikać interpolacji wielomianowej wysokiego rzędu w równo rozmieszczonych próbkach z przedstawionego tutaj powodu.

Jednak ostatnio znalazłem wiele przykładów sygnałów z ograniczeniem pasma, w których wielomian interpolacyjny wysokiego rzędu daje mniejszy błąd aproksymacji niż interpolacja sześcienna-splajn. Zazwyczaj wielomian interpolacyjny jest dokładniejszy w całym przedziale interpolacji, gdy częstotliwość próbkowania jest wystarczająco wysoka. Wydaje się, że dzieje się tak, gdy próbki są równo rozmieszczone z częstotliwością próbkowania co najmniej 3 razy większą niż częstotliwość Nyquista sygnału. Ponadto przewaga nad interpolacją splajnu sześciennego poprawia się wraz ze wzrostem (częstotliwość próbkowania) / (częstotliwość Nyquista).

Jako przykład porównuję interpolację sześcienno-splajnową z interpolującym wielomianem dla fali sinusoidalnej o częstotliwości Nyquista 2 Hz i częstotliwości próbkowania 6,5 Hz. Między punktami próbkowania wielomian interpolujący wygląda dokładnie tak samo jak rzeczywisty sygnał.

Poniżej porównuję błąd w dwóch przybliżeniach. Podobnie jak w pierwszym przykładzie, interpolacja wielomianowa najgorzej działa na początku i na końcu przedziału próbkowania. Jednak wielomian interpolujący ma mniej błędów niż splajn sześcienny w całym okresie próbkowania. Wielomian interpolacyjny ma również mniejszy błąd podczas ekstrapolacji w małym odstępie czasu. Czy odkryłem dobrze znany fakt? Jeśli tak, to gdzie mogę o tym przeczytać?

interpolation

— Ted Ersek
źródło

Czy przybliżasz formułę lub dane? Biorąc pod uwagę wzór, tak jak Ty, zawsze możesz używać bardziej zaawansowanych splajnów, w których uwzględniane są również pochodne wyższego rzędu. Powinieneś także sprawdzić, czy splajn sześcienny minimalizuje pewną funkcję „energii”. Spójrz na wikipedia en.wikipedia.org/wiki/Spline_interpolation . W pewnym sensie, minimalizacja krzywizny, nie da się nic lepszego. Alternatywną interpretacją jest to, że do dopasowania użyto splajnów sześciennych; nie przybliża. „Dopasowanie” oznacza pewną miarę, którą należy zoptymalizować.

— rrogers

@ rrogers, myślałem, że interpolujący wielomian byłby lepszym podejściem, gdy ktoś chce oszacować funkcję na podstawie zmierzonych próbek, a szerokość pasma sygnału jest mniejsza niż 1/6 częstotliwości próbkowania. It

— Ted Ersek

@TedErsek: Jedna uwaga jakościowa: ze względu na swój charakter funkcje wielomianowe różnią się

\pm \infty

$\pm \infty$ jako zmienna odciętej

\to \infty

$\to \infty$ . Efekt ten nasila się wraz ze wzrostem rzędu wielomianów. Zauważ, że w pierwszym przykładzie przybliżony sygnał zanika do zera pod koniec przedziału interpolacji; jest to niezgodne z asymptotycznym zachowaniem interpolanta. Drugi wykres ma strome nachylenie i niezerowe wartości w pobliżu krawędzi przedziału, dzięki czemu uzyskuje się lepsze przybliżenie. Nie bardzo teoretycznie, tylko spostrzeżenie.

— Jason R

@TedErsek Jako praktyczny bok adresujący komentarz Teda Erseka; próbowałeś racjonalnego przybliżenia wielomianu. BTW: Mam darmową kopię programu do szacowania formuły krzywej sprzed roku, który naprawdę działa całkiem nieźle. Program przeszedł z wersji beta na płatną, więc nie mam bieżącej wersji.

— rrogers

@JasonR Chciałem skierować do ciebie mój ostatni komentarz. Wracając do tematu, w każdym razie istnieją en.wikipedia.org/wiki/Chebyshev_polynomials, które zapewniają jednolite błędy (min / maks.) Aproksymacje w wielomianach, jeśli znasz tę funkcję. Ale jeśli znasz tę funkcję, zawsze możesz zsyntetyzować „dopasowany filtr”.

— rrogers

Omawiane zjawisko jest fenomenem Runge .

Maksymalna wartość bezwzględna $n$ pochodna $\sin(\omega t)$ jest $\omega^n$ . Dla funkcji Runge $\frac{1}{25t^2+1}$ maksymalna wartość bezwzględna $n$ pochodną (parzystą) jest $5^nn!,$ gdzie $n!$ oznacza silnię. To jest znacznie szybszy wzrost. Tylko jeśli pochodne rosną zbyt szybko, zwiększając $n$ , wówczas możliwe jest, że błąd interpolacji będzie rozbieżny w miarę zwiększania kolejności interpolacji. Wykładniczy w $n$ nie jest jeszcze za szybki. Spójrz na: James F. Epperson, Na przykładzie Runge , The American Mathematical Monthly , vol. 94, 1987, s. 329–341.

Jeśli funkcja ma tylko ciągłe pochodne, wówczas podejście konkurencyjne, interpolacja wielomianowa wielowymiarowa w kawałkach zawsze jest zbieżna, jeśli niewielka stała liczba jej wczesnych pochodnych jest ograniczona w przedziale zainteresowania, patrz przykład Wikipedii na temat interpolacji liniowej .

Jeśli obie metody są zbieżne, wówczas (niepodzielna) interpolacja wielomianowa ma tę zaletę, że ma wyższy stopień wielomianu, jeśli użytych jest wiele próbek, i może zapewnić lepsze przybliżenie, jak widzieliśmy na przykładzie sinusoidy. Możesz być także zainteresowany LN Trefethen, Dwa wyniki interpolacji wielomianowej w równo rozmieszczonych punktach , Journal of Approximation Theory Volume 65, Issue 3, June 1991, Pages 247-260. Zacytować:

[...] w ograniczonej pasmowo interpolacji złożonych funkcji wykładniczych $e^{i\alpha x}\, (\alpha \in \mathbb{R}),$ błąd zmniejsza się do $0$ tak jak $n \to \infty$ wtedy i tylko wtedy gdy $\alpha$ jest wystarczająco mały, aby zapewnić co najmniej sześć punktów na długość fali.

Masz 6,5 próbek na długość fali.

— Olli Niemitalo
źródło