Warum verhalten sich Punkte mit gleichem Abstand schlecht?

24

Versuchsbeschreibung:

Bei der Lagrange-Interpolation wird die exakte Gleichung an N Punkten (Polynomordnung N1 ) abgetastet und an 101 Punkten interpoliert. Hier wird N von 2 bis 64 variiert. Jedes Mal werden L1 , L2 und L -Fehlerdiagramme erstellt. Es ist zu sehen, dass, wenn die Funktion an Punkten mit gleichem Abstand abgetastet wird, der Fehler anfänglich abfällt (bis N weniger als ungefähr 15 ist) und dann der Fehler mit einer weiteren Zunahme von zunimmt N.

Wenn die Erstabtastung an Legendre-Gauss (LG) -Punkten (Wurzeln von Legendre-Polynomen) oder Legendre-Gauss-Lobatto (LGL) -Punkten (Wurzeln von Lobatto-Polynomen) durchgeführt wird, sinkt der Fehler auf Maschinenebene und nicht erhöhen, wenn weiter erhöht wird.N

Meine Fragen sind:

Was genau passiert bei Punkten mit gleichem Abstand?

Warum führt eine Erhöhung der Polynomordnung dazu, dass der Fehler nach einem bestimmten Punkt ansteigt?

Bedeutet dies auch, dass ich im glatten Bereich Fehler erhalte, wenn ich Punkte mit gleichem Abstand für die WENO / ENO-Rekonstruktion verwende (unter Verwendung von Lagrange-Polynomen)? (Nun, dies sind nur hypothetische Fragen (nach meinem Verständnis), es ist wirklich nicht sinnvoll, ein Polynom in der Größenordnung von 15 oder höher für das WENO-Schema zu rekonstruieren.)

Zusätzliche Details:

Funktion angenähert:

f(x)=cos(π2 x),x[1,1]

x unterteilt inN Punkte mit gleichem Abstand (und später LG). Die Funktion wird jeweils zu 101 Punkten interpoliert.

Ergebnisse:

  1. a) Punkte mit gleichem Abstand (Interpolation für N=65 ):

Bildbeschreibung hier eingeben

  1. b) Punkte mit gleichem Abstand (Fehlerdiagramm, logarithmische Skala):

Bildbeschreibung hier eingeben

  1. a) LG Punkte (Interpolation für N=65 ): Bildbeschreibung hier eingeben

  2. b) LG-Punkte (Fehlerdiagramm, logarithmische Skala):

Bildbeschreibung hier eingeben

Subodh
quelle

Antworten:

26

Das Problem bei gleichmässigen Punkten ist, dass das Interpolationsfehlerpolynom, d.h.

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

xi

Wenn Sie Gauß-Legendre-Punkte verwenden, verhält sich das Fehlerpolynom wesentlich besser, dh es explodiert nicht an den Rändern. Wenn Sie Chebyshev-Knoten verwenden , gleicht sich dieses Polynom aus und der Interpolationsfehler ist minimal.

Pedro
quelle
6
Das Buch von John P. Boyd Chebyshev und Fourier Spectral Methods enthält eine ausführliche Erklärung, in der auch das Interpolationsfehlerpolynom von Pedro gut erklärt wird (Kapitel 4.2 Seite 85).
Bort
Vielen Dank. Auch die Lebesgue-Konstante für die oben genannten Auswahlmöglichkeiten verhält sich anders. Bei Punkten mit gleichem Abstand steigt die Lebesgue-Konstante exponentiell an, wohingegen sie bei LG, LGL und Chebyshev mit zunehmendem n sättigt. en.wikipedia.org/wiki/Lebesgue_constant_(interpolation) , ami.ektf.hu/uploads/papers/finalpdf/AMI_33_from109to123.pdf , aber die Frage nach der numerischen Implementierung bleibt noch offen ...
Subodh
Entschuldigung, ich weiß nicht viel über ENO / WENO. Aber ich erwarte keine Probleme im glatten Bereich für Interpolationen niedriger Ordnung, obwohl Quadraturknoten aus verschiedenen Gründen definitiv die bessere Wahl sind.
Bort
22

Dies ist eine wirklich interessante Frage, und es gibt viele mögliche Erklärungen. Wenn wir versuchen, eine Polynominterpolation zu verwenden, beachten Sie, dass das Polynom die folgende ärgerliche Ungleichung erfüllt

PN

|P(x)|N1x2maxx|P(x)|

für jedes . Dies ist als Bernsteins Ungleichung bekannt , beachten Sie die Singularität in dieser Ungleichung. Dies kann durch die Markov-Ungleichung begrenzt werdenx(1,1)

maxx|P(x)|N2maxx|P(x)|

und beachte, dass dies in dem Sinne scharf ist, dass Chebysehv-Polynome dies zu einer Gleichung machen. Mit anderen Worten, wir haben die folgende kombinierte Grenze.

|P(x)|min(N1x2,N2)maxx|P(x)|

Was dies bedeutet: Gradienten von Polynomen wachsen überall linear in ihrer Reihenfolge, außer in kleinen Nachbarschaften der Intervallgrenzen. An den Grenzen wachsen sie eher wie . Es ist kein Zufall, dass stabile Interpolationsknoten alle ein -Cluster in der Nähe von Grenzen aufweisen. Das Clustering ist notwendig, um die Gradienten der Basis zu steuern, während man in der Nähe des Mittelpunkts etwas entspannter sein kann.N21/N2

Es stellt sich jedoch heraus, dass dies nicht unbedingt ein Polynomphänomen ist. Ich schlage folgendes Papier vor:

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

Es heißt locker: Wenn Sie die gleiche Approximationsstärke der Polynombasis haben, können Sie Punkte mit gleichem Abstand nicht stabil verwenden.

Reid. Atcheson
quelle
1

Es sind nicht die gleichmäßig verteilten Punkte , die das Problem sind. Das Problem ist die globale Unterstützung der Basisfunktionen zusammen mit gleichmäßig verteilten Punkten. Eine perfekt konditionierte Interpolation mit gleichmäßig verteilten Punkten wird in Kress 'Numerical Analysis unter Verwendung von Kubik-B-Spline-Basisfunktionen mit kompakter Unterstützung beschrieben.

user14717
quelle
sicher, aber dann wird Ihr Interpolant nicht global glatt (nur für Ihr Beispiel)C2
GoHokies
@GoHokies: Die kompakt gelagerten Splines können durch iterative Faltung beliebig glatt gemacht werden. Was ist der Anwendungsfall für die -Interpolation? C
user14717
gutes Argument. ("Position-Geschwindigkeit-Beschleunigung") reicht für die meisten Anwendungen aus. Sie möchten vielleicht für einige Randwertprobleme, können sich aber keinen allgemeinen Anwendungsfall darüber vorstellen. C2C4
GoHokies
1

Was genau passiert bei Punkten mit gleichem Abstand?

Warum führt eine Erhöhung der Polynomordnung dazu, dass der Fehler nach einem bestimmten Punkt ansteigt?

Dies ähnelt dem Runge-Phänomen , bei dem bei Knoten mit gleichem Abstand der Interpolationsfehler mit zunehmendem Polynomgrad, dh der Anzahl der Punkte, unendlich wird.

Eine der Wurzeln dieses Problems liegt in der Lebesgue-Konstante, wie in @ Subodhs Kommentar zur @Pedro-Antwort vermerkt. Diese Konstante bezieht die Interpolation in bester Näherung.


Einige Notationen

Wir haben eine Funktion um über die Knoten zu interpolieren . In der Lagrange-Interpolation werden die Lagrange-Polynome definiert :fC([a,b])xk

Lk(x)=i=0,ijnxxixkxi

wird das Interpolationspolynom über die Paare für die LichtnotationpnPn(xk,f(xk))(xk,fk)

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

Betrachten Sie nun eine Störung über den Daten, dies kann zum Beispiel zum Runden sein, so dass wir . Damit lautet das neue Polynom :f~kp~n

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

Die Fehlerschätzungen sind:

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)|

Jetzt ist es möglich, die Lebesgue-Konstante wie folgt zu definieren :Λn

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

Damit ist die endgültige Schätzung:

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

(Randbemerkung, wir schauen nur norm, auch weil wir uns über einen endlichen Raum befinden, also )LL1

Aus der obigen Berechnung ergibt sich, dass ist:Λn

  • unabhängig vom Datum:
  • hängt nur von der Knotenverteilung ab;
  • ein Indikator für die Stabilität (je kleiner es ist, desto besser ist es).

Es ist auch die Norm des Interpolationsoperators, die norm.||||

Mit dem folgenden Theorem haben wir eine Schätzung des Interpolationsfehlers mit der Lebesgue-Konstante:

Sei und wie oben angegeben, dann haben wir wobei ist der Fehler durch das beste Polynom der gleichmäßigen Approximationfpn

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

wenn klein ist, ist der Fehler der Interpolation nicht weit vom Fehler der besten gleichförmigen Approximation entfernt und der Satz vergleicht den Interpolationsfehler mit dem kleinstmöglichen Fehler, der der Fehler der besten gleichförmigen Approximation ist.Λn

Das Verhalten der Interpolation hängt dabei von der Knotenverteilung ab. Es gibt eine Untergrenze für dass bei gegebener Knotenverteilung eine Konstante so dass: die Konstante wächst, aber wie sie wächst importan.Λnc

Λn2πlog(n)c

Für Knoten mit Abstand ich einige Details ausgelassen, aber wir sehen, dass das Wachstum exponentiell ist.

Λn2n+1enlog(n)

Für Chebyshev-Knoten habe ich auch hier einige Details weggelassen, es gibt genauere und kompliziertere Schätzungen. Siehe [1] für weitere Details. Beachten Sie, dass die Knoten der Familie Chebyshev logarithmisch wachsen und nach den vorherigen Schätzungen so gut wie möglich sind.

Λn2πlog(n)+4

Informationen zu anderen Knotenverteilungen finden Sie beispielsweise in Tabelle 1 dieses Artikels .


Es gibt eine Menge Nachschlagewerke zum Thema Interpolation. Online sind diese Folien als Zusammenfassung schön.

Auch dieser offene Artikel ([1])

Ein Vergleich der numerischen Sieben-Gitter-Interpolation für das Polynom auf dem Intervall für verschiedene Vergleiche.

Mauro Vanzetto
quelle
1

Es ist gut, Floater-Hormann-Interpolanten zu kennen, wenn Sie mit äquidistanten Punkten arbeiten müssen (oder wollen) .{xi}i=1n

Wenn die ganze Zahl mit , sei die Polynominterpolante von . Dann hat der FH-Interpolant einer Funktion bei die Formd0dnpi{xi,xi+d}f{xi}i=1n

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

mit den "Mischfunktionen"

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

Einige Eigenschaften dieser Interpolanten:

  • sie sind baryzentrische rationale Interpolanten ohne echte Pole ;
  • Erzielen beliebiger Approximationsordnungen für , unabhängig von der Punkteverteilung;O(hd+1)fCd+2[a,b]
  • sind insofern Splines ähnlich, als sie (lokale) Polynominterpolanten mischen wobei die als Mischfunktionen fungieren;p0,pndλ
  • sie reproduzieren Polynome vom Grad höchstens (oder wenn ungerade ist);dd+1nd
  • kann in baryzentrischer Form geschrieben werden (siehe Abschnitt 4 der Arbeit von Floater und Hormann).

Warnung : Wie erwartet (siehe das von @ Reid.Atcheson referenzierte Dokument), verschlechtert eine Erhöhung von schnell die Konditionierung des Approximationsprozesses.d

Klein hat in jüngster Zeit einige Arbeiten durchgeführt, um dieses Problem zu lösen. Er modifizierte den ursprünglichen Floater-Hormann-Ansatz, indem er neue Datenwerte hinzufügte , die Punkten außerhalb des ursprünglichen Interpolationsintervalls die aus einer glatten Erweiterung von außerhalb Verwendung nur der gegebenen Daten konstruiert wurden . Dieser "globale" Datensatz wird dann von einer neuen rationalen FH-Funktion interpoliert und nur in ausgewertet .2d [a,b]f[a,b]f0,fnrn+2d[a,b]

Die Details sind in Kleins Artikel (siehe unten) ausführlich dargestellt, in dem gezeigt wird, dass diese erweiterten rationalen Interpolanten Lebesgue-Konstanten haben, die logarithmisch mit und wachsen (während für das ursprüngliche FH-Schema das Wachstum in exponentiell ist , siehe Bos et al. ).ndd

Die Chebfun-Bibliothek verwendet FH-Interpolanten, wenn chebfunssie aus Daten mit gleichem Abstand erstellt, wie hier erläutert .

Verweise:

MS Floater und K. Hormann, Baryzentrische rationale Interpolation ohne Pole und hohe Approximationsraten, Numerische Mathematik 107 (2007).

G. Klein, Eine Erweiterung der Floater-Hormann-Familie der baryzentrischen rationalen Interpolanten, Mathematics of Computation , 82 (2011) - Preprint

L. Bos, S. De Marchi, K. Hörmann und G. Klein, Zur Lebesgue-Konstante der baryzentrischen rationalen Interpolation an äquidistanten Knoten, Numer. Mathematik. 121 (2012)

GoHokies
quelle