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 - 1 N L 1 L 2 L N NNN1NL1L2LNN

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(π2 x) ,x[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:

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

wprowadź opis zdjęcia tutaj

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

wprowadź opis zdjęcia tutaj

  1. a) Punkty LG (interpolacja dla ): N=65wprowadź opis zdjęcia tutaj

  2. b) Punkty LG (wykres błędu, skala logu):

wprowadź opis zdjęcia tutaj

Subodh
źródło

Odpowiedzi:

26

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

f(x)Pn(x)=f(n+1)(ξ)(n+1)!i=0n(xxi),ξ[x0,xn]

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

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 N , mamyPN

|P(x)|N1x2maxx|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ą Markowax(1,1)

maxx|P(x)|N2maxx|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)|min(N1x2,N2)maxx|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.N21/N2

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)C2
GoHokies
@ GoHokies: Kompaktowo obsługiwane splajny mogą być dowolnie gładkie dzięki iteracyjnemu splotowi. Jaki jest przypadek użycia interpolacji ? C
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 4C2C4
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 :fC([a,b])xk

Lk(x)=i=0,ijnxxixkxi

z tym definiuje się wielomian interpolacyjny nad parami dla notacji świetlnejpnPn(xk,f(xk))(xk,fk)

pn(x)=k=0nfkLk(x)

Rozważmy teraz zaburzenie danych, może to być na przykład zaokrąglenie, więc mamy . Dzięki temu nowy wielomian jest:f~kp~n

p~n(x)=k=0nf~kLk(x)

Szacunkowe błędy to:

pn(x)p~n(x)=k=0n(fkf~k)Lk(x)

|pn(x)p~n(x)|k=0n|fkf~k||Lk(x)|(maxk|fkf~k|)k=0n|Lk(x)|

Teraz można zdefiniować stałą Lebesgue'a jako:Λn

Λn=maxx[a,b]k=0n|Lk(x)|

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

||pnp~n||(maxk|fkf~k|)Λn

(uwaga marginalna, wyglądamy tylko na normę również dlatego, że jesteśmy ponad przestrzenią skończonej miary, więc )LL1

Z powyższych obliczeń wynika, że to:Λ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.||||

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 aproksymacyjnegofpn

||fpn||(1+Λn)dn(f)
dn(f)=infqnPn||fqn||

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.Λ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.Λnc

Λn2πlog(n)c

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

Λn2n+1enlog(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ć.

Λn2π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 .{xi}i=1n

Biorąc pod uwagę liczbę całkowitą z , niech będzie wielomianowym interpolantem . Następnie interpolant FH funkcji w ma postać0 d n p i { x i , x i + d } fd0dnpi{xi,xi+d}f{xi}i=1n

rn(x):=i=0ndλi(x)pi(x)i=0ndλi(x)

z „funkcjami mieszania”

λi(x)=(1)i(xxi)(xxi+d)

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

  • są barycentrycznymi racjonalnymi interpolantami bez prawdziwych biegunów ;
  • O(hd+1)fCd+2[a,b]
  • p0,pndλ
  • dd+1nd
  • może być napisany w formie barycentrycznej (patrz rozdział 4 artykułu Floatera i Hormanna).

d

2d [a,b]f[a,b]f0,fnrn+2d[a,b]

ndd

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