Warum verhalten sich Punkte mit gleichem Abstand schlecht?

24

Versuchsbeschreibung:

Bei der Lagrange-Interpolation wird die exakte Gleichung an $N$ Punkten (Polynomordnung $N - 1$ ) abgetastet und an 101 Punkten interpoliert. Hier wird $N$ von 2 bis 64 variiert. Jedes Mal werden $L_1$ , $L_2$ und $L_\infty$ -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(\frac{\pi}{2}~x)$ , $x \in [-1, 1]$

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

Ergebnisse:

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

Bildbeschreibung hier eingeben

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

Bildbeschreibung hier eingeben

a) LG Punkte (Interpolation für $N = 65$ ):
b) LG-Punkte (Fehlerdiagramm, logarithmische Skala):

Bildbeschreibung hier eingeben

finite-difference interpolation error-estimation polynomials Subodh
quelle

26

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

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]$

$x_i$

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

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

für jedes . Dies ist als Bernsteins Ungleichung bekannt , beachten Sie die Singularität in dieser Ungleichung. Dies kann durch die Markov-Ungleichung begrenzt werden $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) |$

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

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. $N^2$ $1/{N^2}$

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)

C^{2}

$C^2$

GoHokies

@GoHokies: Die kompakt gelagerten Splines können durch iterative Faltung beliebig glatt gemacht werden. Was ist der Anwendungsfall für die -Interpolation?

C^{\infty}

$C^{\infty}$

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.

C^{2}

$C^2$

C^{4}

$C^4$

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 : $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}$

wird das Interpolationspolynom über die Paare für die Lichtnotation $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)$

Betrachten Sie nun eine Störung über den Daten, dies kann zum Beispiel zum Runden sein, so dass wir . Damit lautet das neue Polynom : $\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)$

Die Fehlerschätzungen sind:

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

Jetzt ist es möglich, die Lebesgue-Konstante wie folgt zu definieren : $\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)|$

Damit ist die endgültige Schätzung:

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

(Randbemerkung, wir schauen nur norm, auch weil wir uns über einen endlichen Raum befinden, also ) $\infty$ $L^{\infty} \subseteq \dots \subseteq L^1$

Aus der obigen Berechnung ergibt sich, dass ist: $\Lambda_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. $|| \cdot||_\infty$

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 Approximation $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}$

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. $\Lambda_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. $\Lambda_n$ $c$

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

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

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

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

$\Lambda_n \approx \frac{2^{n+1}}{en \log(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.

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

$\Lambda_n \leq \frac{2}{\pi} \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) . $\{x_i\}_{i=1\ldots n}$

Wenn die ganze Zahl mit , sei die Polynominterpolante von . Dann hat der FH-Interpolant einer Funktion bei die Form $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)}$

mit den "Mischfunktionen"

λ_{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})}$

Einige Eigenschaften dieser Interpolanten:

sie sind baryzentrische rationale Interpolanten ohne echte Pole ;
Erzielen beliebiger Approximationsordnungen für , unabhängig von der Punkteverteilung; ${\cal O}(h^{d+1})$ $f \in C^{d+2}[a,b]$
sind insofern Splines ähnlich, als sie (lokale) Polynominterpolanten mischen wobei die als Mischfunktionen fungieren; $p_0, \ldots p_{n-d}$ $\lambda$
sie reproduzieren Polynome vom Grad höchstens (oder wenn ungerade ist); $d$ $d+1$ $n-d$
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 . $2 d$ $[a,b]$ $f$ $[a,b]$ $f_0, \ldots f_n$ $r_{n+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. ). $n$ $d$ $d$

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

Warum verhalten sich Punkte mit gleichem Abstand schlecht?

Antworten: