Dlaczego punkty o równych odstępach zachowują się źle?

24

Opis eksperymentu:

W interpolacji Lagrange'a dokładne równanie jest próbkowane w punktach (rząd wielomianu ) i interpolowane w 101 punktach. Tutaj zmienia się od 2 do 64. Za każdym razem , przygotowywane są wykresy błędów , i . Okazuje się, że gdy ta funkcja jest próbkowany z punktów równo rozmieszczonych na błędu spada początkowo (zdarza się do jest mniejsza niż około 15 lub więcej), po czym błąd wzrasta wraz z dalszym wzrostem w . $N$ $N - 1$ $N$ $L_1$ $L_2$ $L_\infty$ $N$ $N$

Podczas gdy początkowe próbkowanie odbywa się w punktach Legendre-Gaussa (LG) (pierwiastki wielomianów Legendre) lub w punktach Legendre-Gaussa-Lobatto (LGL) (pierwiastki wielomianów Lobatto), błąd spada do poziomu maszyny i nie zwiększyć, gdy jest dalej zwiększane. $N$

Moje pytania są

Co dokładnie dzieje się w przypadku punktów o równych odstępach?

Dlaczego wzrost kolejności wielomianowej powoduje wzrost błędu po określonym punkcie?

Czy to oznacza również, że jeśli użyję punktów o równych odstępach do rekonstrukcji WENO / ENO (używając wielomianów Lagrange'a), to w obszarze gładkim dostaję błędy? (cóż, są to tylko pytania hipotetyczne (dla mojego zrozumienia), naprawdę nie ma sensu rekonstruować wielomianu rzędu 15 lub więcej dla schematu WENO)

Dodatkowe Szczegóły:

Przybliżona funkcja:

$f(x) = \cos(\frac{\pi}{2}~x)$ , $x \in [-1, 1]$

$x$ podzielone na równych punktów (a później LG) punktów. Funkcja interpolowana jest za każdym razem w 101 punktach. $N$

Wyniki:

a) Punkty o równych odstępach (interpolacja dla ): $N = 65$

wprowadź opis zdjęcia tutaj

b) Punkty o równych odstępach (wykres błędu, skala logu):

wprowadź opis zdjęcia tutaj

a) Punkty LG (interpolacja dla ): $N = 65$
b) Punkty LG (wykres błędu, skala logu):

wprowadź opis zdjęcia tutaj

— Subodh
źródło

26

Problem z nierównomiernymi punktami polega na tym, że wielomian błędu interpolacji, tj

f (x) - P_{n} (x) = \frac{f^{(n + 1)} (ξ)}{(n + 1)!} \prod_{i = 0}^{n} (x - x_{i}), ξ \in [x_{0}, x_{n}]

$f(x) - P_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x - x_i),\quad \xi\in[x_0,x_n]$

zachowuje się odmiennie, różne grupy węzłów . W przypadku punktów o nierównej powierzchni wielomian wysadza się na krawędziach. $x_i$

Jeśli używasz punktów Gaussa-Legendre'a, wielomian błędu jest znacznie lepiej zachowywany, tzn. Nie wysadza na krawędziach. Jeśli korzystasz z węzłów Czebyszewa , ten wielomian równoważy się, a błąd interpolacji jest minimalny.

— Pedro
źródło

6

Szczegółowe wyjaśnienie znajduje się w książce John P. Boyd Chebyshev and Fourier Spectral Methods, w której dobrze wyjaśniono wielomian błędu interpolacji Pedro (Rozdział 4.2 Strona 85).

— Bort

Dziękuję Ci. Również stała Lebesgue'a dla wyżej wymienionych wyborów zachowuje się inaczej. W przypadku punktów o równych odstępach stała Lebesgue'a rośnie wykładniczo, podczas gdy dla LG, LGL, Czebyszewa niejako nasyca się wraz ze wzrostem n. en.wikipedia.org/wiki/Lebesgue_constant_(interpolation) , ami.ektf.hu/uploads/papers/finalpdf/AMI_33_from109to123.pdf , ale wciąż pozostaje pytanie dotyczące numerycznej implementacji ...

— Subodh

Przepraszam, niewiele wiem o ENO / WENO. Ale nie oczekuję problemów w gładkim regionie dla interpolacji niskiego rzędu, chociaż węzły kwadraturowe są zdecydowanie lepszym wyborem z oczywistych powodów.

— Bort

22

To naprawdę interesujące pytanie i istnieje wiele możliwych wyjaśnień. Jeśli próbujemy zastosować interpolację wielomianową, zauważ, że wielomian spełnia następującą irytującą nierówność

Biorąc pod uwagę wielomian o stopniu nieprzekraczającym , mamy $P$ $N$

| P^{'} (x) | \leq \frac{N}{\sqrt{1 - x^{2}}} max_{x} | P (x) |

$|P^{\prime}(x)| \leq \frac{N}{\sqrt{1-x^2}}\max _x |P(x) |$

dla każdego . Jest to znane jako nierówność Bernsteina , zauważ osobliwość tej nierówności. Może to być ograniczone nierównością Markowa $x \in (-1,1)$

max_{x} | P^{'} (x) | \leq N^{2} max_{x} | P (x) |

$\max _x |P^{\prime} (x) | \leq N^2 \max _x |P(x) |$

i zauważmy, że jest to ostre w tym sensie, że wielomiany Chebysehva tworzą to równanie. Innymi słowy, mamy następujące połączone powiązanie.

| P^{'} (x) | \leq min (\frac{N}{\sqrt{1 - x^{2}}}, N^{2}) max_{x} | P (x) |

$|P^{\prime}(x)| \leq \min \left(\frac{N}{\sqrt{1-x^2}},N^2\right)\max _x |P(x) |$

Co to oznacza: gradienty wielomianów rosną wszędzie liniowo w swojej kolejności, z wyjątkiem małych dzielnic granic przedziałów. Na granicach rosną bardziej jak . To nie przypadek, że wszystkie stabilne węzły interpolacji mają klaster pobliżu granic. Grupowanie jest konieczne do kontrolowania gradientów podstawy, podczas gdy w pobliżu punktu środkowego można być nieco bardziej zrelaksowanym. $N^2$ $1/{N^2}$

Okazuje się jednak, że niekoniecznie jest to zjawisko wielomianowe, sugeruję następujący artykuł:

http://math.la.asu.edu/~platte/pub/prevised.pdf

Mówi luźno: jeśli masz taką samą moc aproksymacji podstawy wielomianu, to nie możesz używać punktów o równej odległości w stabilny sposób.

— Reid.Atcheson
źródło

1

Problemem nie są jednakowo rozmieszczone punkty . Problemem jest globalne wsparcie funkcji podstawowych wraz z równo rozmieszczonymi punktami. Idealnie dobrze uwarunkowany interpolant wykorzystujący równomiernie rozmieszczone punkty opisano w analizie numerycznej Kressa, wykorzystując funkcje bazowe splajnu sześciennego b zwartej podpory.

— użytkownik14717
źródło

jasne, ale wtedy twój interpolant nie będzie globalnie gładki (tylko w twoim przykładzie)

C^{2}

$C^2$

— GoHokies

@ GoHokies: Kompaktowo obsługiwane splajny mogą być dowolnie gładkie dzięki iteracyjnemu splotowi. Jaki jest przypadek użycia interpolacji ?

C^{\infty}

$C^{\infty}$

— user14717,

słuszny punkt. („przyspieszenie prędkości położenia”) wystarcza do większości zastosowań. możesz chcieć dla niektórych problemów z wartością graniczną, ale nie możesz pomyśleć o żadnym typowym przypadku użycia powyżej tego.

C^{2}

$C^2$

C^{4}

$C^4$

— GoHokies

1

Co dokładnie dzieje się w przypadku punktów o równych odstępach?

Dlaczego wzrost kolejności wielomianowej powoduje wzrost błędu po określonym punkcie?

Jest to podobne do zjawiska Runge'a, w którym przy węzłach o równych odstępach błąd interpolacji dochodzi do nieskończoności wraz ze wzrostem stopnia wielomianu, tj. Liczby punktów.

Jeden z źródeł tego problemu można znaleźć w stałej Lebesgue'a, jak odnotowano w komentarzu @ Subodha do odpowiedzi @Pedro. Ta stała wiąże interpolację z najlepszym przybliżeniem.

Niektóre notacje

Mamy funkcję do interpolacji węzłów . W interpolacji Lagrange'a zdefiniowane są wielomiany Lagrange'a : $f \in C([a,b])$ $x_k$

L_{k} (x) = \prod_{i = 0, i \neq j}^{n} \frac{x - x_{i}}{x_{k} - x_{i}}

$L_k(x) = \prod_{i=0, i\neq j}^{n}\frac{x-x_i}{x_k-x_i}$

z tym definiuje się wielomian interpolacyjny nad parami dla notacji świetlnej $p_n \in P_n$ $(x_k, f(x_k))$ $(x_k, f_k)$

p_{n} (x) = \sum_{k = 0}^{n} f_{k} L_{k} (x)

$p_n(x) = \sum_{k=0}^n f_kL_k(x)$

Rozważmy teraz zaburzenie danych, może to być na przykład zaokrąglenie, więc mamy . Dzięki temu nowy wielomian jest: $\tilde{f}_k$ $\tilde{p}_n$

{\tilde{p}}_{n} (x) = \sum_{k = 0}^{n} {\tilde{f}}_{k} L_{k} (x)

$\tilde{p}_n(x) = \sum_{k=0}^n \tilde{f}_k L_k(x)$

Szacunkowe błędy to:

p_{n} (x) - {\tilde{p}}_{n} (x) = \sum_{k = 0}^{n} (f_{k} - {\tilde{f}}_{k}) L_{k} (x)

$p_n(x) - \tilde{p}_n(x) = \sum_{k=0}^n (f_k - \tilde{f}_k) L_k(x)$

| p_{n} (x) - {\tilde{p}}_{n} (x) | \leq \sum_{k = 0}^{n} | f_{k} - {\tilde{f}}_{k} | | L_{k} (x) | \leq (max_{k} | f_{k} - {\tilde{f}}_{k} |) \sum_{k = 0}^{n} | L_{k} (x) |

$| p_n(x) - \tilde{p}_n(x) | \leq \sum_{k=0}^n |f_k - \tilde{f}_k| |L_k(x)| \leq \left ( \max_k |f_k - \tilde{f}_k| \right) \sum_{k=0}^n |L_k(x)|$

Teraz można zdefiniować stałą Lebesgue'a jako: $\Lambda_n$

Λ_{n} = max_{x \in [a, b]} \sum_{k = 0}^{n} | L_{k} (x) |

$\Lambda_n = \max_{x \in [a,b]} \sum_{k=0}^n |L_k(x)|$

Dzięki temu ostateczne szacunki są następujące:

| | p_{n} - {\tilde{p}}_{n} | |_{\infty} \leq (max_{k} | f_{k} - {\tilde{f}}_{k} |) Λ_{n}

$|| p_n - \tilde{p}_n ||_{\infty} \leq \left ( \max_k |f_k - \tilde{f}_k| \right) \Lambda_n$

(uwaga marginalna, wyglądamy tylko na normę również dlatego, że jesteśmy ponad przestrzenią skończonej miary, więc ) $\infty$ $L^{\infty} \subseteq \dots \subseteq L^1$

Z powyższych obliczeń wynika, że to: $\Lambda_n$

niezależny od daty:
zależy tylko od rozkładu węzłów;
wskaźnik stabilności (im mniejszy, tym lepszy).

Jest to również norma operatora interpolacji przestrzegającego norma. $|| \cdot||_\infty$

Z poniższym twierdzeniem mamy oszacowany błąd interpolacji przy stałej stałej Lebesgue'a:

Niech i jak wyżej mamy gdzie jest błędem najlepszego jednolitego wielomianu aproksymacyjnego $f$ $p_n$
$| | f - p_{n} | |_{\infty} \leq (1 + Λ_{n}) d_{n} (f)$ $|| f - p_n ||_{\infty} \leq (1 + \Lambda_n) d_n(f)$ $d_{n} (f) = inf_{q_{n} \in P_{n}} | | f - q_{n} | |_{\infty}$ $d_n(f) = \inf_{q_n \in P_n} || f - q_n ||_{\infty}$

Tzn. Jeśli jest mały, błąd interpolacji nie jest od błędu najlepszego przybliżenia jednolitego, a twierdzenie porównuje błąd interpolacji z najmniejszym możliwym błędem, który jest błędem najlepszego przybliżenia jednolitego. $\Lambda_n$

W tym celu zachowanie interpolacji zależy od rozkładu węzłów. Istnieją dolne granice w że przy danym rozkładzie węzłów istnieje stała taka, że: więc stała rośnie, ale jak rośnie importan. $\Lambda_n$ $c$

Λ_{n} \geq \frac{2}{π} \log (n) - c

$\Lambda_n \geq \frac{2}{\pi} \log(n) - c$

Dla węzłów o odstępach Pominąłem niektóre szczegóły, ale widzimy, że wzrost jest wykładniczy.

Λ_{n} \approx \frac{2^{n + 1}}{e n \log (n)}

$\Lambda_n \approx \frac{2^{n+1}}{en \log(n)}$

W przypadku węzłów Czebyszewa również tutaj pominąłem niektóre szczegóły, są bardziej dokładne i skomplikowane oszacowanie. Zobacz [1] po więcej szczegółów. Zauważ, że węzły rodziny Czebyszewa mają logarytmiczny wzrost i z poprzednich szacunków jest blisko najlepszych, jakie możesz uzyskać.

Λ_{n} \leq \frac{2}{π} \log (n) + 4

$\Lambda_n \leq \frac{2}{\pi} \log(n) + 4$

W przypadku innych dystrybucji węzłów zobacz na przykład tabelę 1 tego artykułu .

W książce jest wiele odniesień na temat interpolacji. On-line te slajdy są ładne jak CV.

Również ten otwarty artykuł ([1])

Numeryczne porównanie interpolacji siedmiu siatek dla wielomianu w interwale dla różnych porównań.

— Mauro Vanzetto
źródło

1

Dobrze jest zdawać sobie sprawę z interpolants Pływak-Hörmann gdy mają (lub chcą) praca z równoodległych punktów . $\{x_i\}_{i=1\ldots n}$

Biorąc pod uwagę liczbę całkowitą z , niech będzie wielomianowym interpolantem . Następnie interpolant FH funkcji w ma postać $d$ $0 \le d \le n$ $p_i$ $\{ x_i, \ldots x_{i+d} \}$ $f$ $\{x_i\}_{i=1\ldots n}$

r_{n} (x) := \frac{\sum_{i = 0}^{n - d} λ_{i} (x) p_{i} (x)}{\sum_{i = 0}^{n - d} λ_{i} (x)}

$r_n(x) := \frac{\sum_{i=0}^{n-d} \lambda_i(x) \, p_i(x)}{\sum_{i=0}^{n-d} \lambda_i(x)}$

z „funkcjami mieszania”

λ_{i} (x) = \frac{(- 1)^{i}}{(x - x_{i}) \dots (x - x_{i + d})}

$\lambda_i(x) = \frac{(-1)^i}{(x-x_i) \ldots (x - x_{i+d})}$

Niektóre właściwości tych interpolantów:

są barycentrycznymi racjonalnymi interpolantami bez prawdziwych biegunów ;
${\cal O}(h^{d+1})$ $f \in C^{d+2}[a,b]$
$p_0, \ldots p_{n-d}$ $\lambda$
$d$ $d+1$ $n-d$
może być napisany w formie barycentrycznej (patrz rozdział 4 artykułu Floatera i Hormanna).

$d$

$2 d$ $[a,b]$ $f$ $[a,b]$ $f_0, \ldots f_n$ $r_{n+2d}$ $[a,b]$

$n$ $d$ $d$

Biblioteka Chebfun wykorzystuje interpolanty FH podczas budowania chebfunsnierównomiernych danych, jak wyjaśniono tutaj .

Referencje:

MS Floater i K. Hormann, Barycentryczna racjonalna interpolacja bez biegunów i wysokie wskaźniki przybliżenia, Numerische Mathematik 107 (2007).

G. Klein, Rozszerzenie rodziny Floater – Hormann Barycentrycznych racjonalnych interpolantów, Matematyka obliczeń , 82 (2011) - przedruk

L. Bos, S. De Marchi, K. Hormann i G. Klein, O stałej Lebesgue'a barycentrycznej racjonalnej interpolacji w równo odległych węzłach, Numer. Matematyka 121 (2012)

— GoHokies
źródło