Experimentelle Konvergenzordnung

Unter dem Begriff experimentelle Konvergenzordnung (englisch: experimental order of convergence, EOC) versteht man in der numerischen Mathematik einen Schätzwert der Konvergenzgeschwindigkeit einer Folge. Um diesen zu berechnen, wird der Grenzwert als bekannt vorausgesetzt.

Dieses Hilfsmittel wird oft zur Validierung von Finite-Elemente- und Diskontinuierliche Galerkin-Methoden eingesetzt.

Definition

Seien $x_k,x_{k+1},x_{k+2}$ drei aufeinanderfolgende Folgenglieder und $x$ der Folgengrenzwert. Die experimentelle Konvergenzordnung lautet dann

$\mathrm{E}\mathrm{O}\mathrm{C}=\frac{\log \frac{\Vert x_{k+1}-x\Vert }{\Vert x_{k+2}-x\Vert }}{\log \frac{\Vert x_k-x\Vert }{\Vert x_{k+1}-x\Vert }}$

wobei $\Vert \cdot \Vert$ eine geeignete Norm ist.

Motivation

Sei $x$ der bereits bekannte Grenzwert der Folge $(x_k{)}_{k\in \mathbb{N}}$. Die Folge konvergiert mit der Geschwindigkeit $\alpha$, wenn es eine Konstante $c>0$ gibt, die die Ungleichung

$\Vert x_{k+1}-x\Vert \le c\Vert x_k-x{\Vert }^{\alpha }$

erfüllt. Nun wird vereinfachend angenommen, die Konvergenz könne exakt durch

$\Vert x_{k+1}-x\Vert =c\Vert x_k-x{\Vert }^{\alpha }$

beschrieben werden. Diese Formulierung gilt dann auch für das nächste Folgenglied

$\Vert x_{k+2}-x\Vert =c\Vert x_{k+1}-x{\Vert }^{\alpha }$

Division der beiden Gleichungen liefert

$\frac{\Vert x_{k+1}-x\Vert }{\Vert x_{k+2}-x\Vert }={\left(\frac{\Vert x_k-x\Vert }{\Vert x_{k+1}-x\Vert }\right)}^{\alpha }$

Also gilt

$\alpha ={\log }_{\frac{\Vert x_k-x\Vert }{\Vert x_{k+1}-x\Vert }}\frac{\Vert x_{k+1}-x\Vert }{\Vert x_{k+2}-x\Vert }$

wobei ${\log }_{\frac{\Vert x_k-x\Vert }{\Vert x_{k+1}-x\Vert }}$ den Logarithmus zur Basis $\frac{\Vert x_k-x\Vert }{\Vert x_{k+1}-x\Vert }$ bezeichnet. Eine Umrechnung des Logarithmus zur Basis $10$ ergibt die Definition der $\mathrm{E}\mathrm{O}\mathrm{C}$.

Anwendung: Numerische Lösungen von Differentialgleichungen

Seien $u_h,u_{h^{\prime }}$ numerische Lösungen eines Verfahrens, das (partielle) Differentialgleichungen näherungsweise löst. Dabei seien $h,h^{\prime }$ verschiedene Werte eines Diskretisierungsparameter, der die Auflösung der Diskretisierung beschreibt. Im eindimensionalen Fall ist $h$ üblicherweise die Länge des größten Intervalls. Im höherdimensionalen Fall nimmt man ein analoges Maß für die Feinheit des Gitters, beispielsweise in zwei Dimensionen den größten Inkreisdurchmesser. Sei $u$ der Grenzwert des Verfahrens für $h\to 0$. Dann ist die experimentelle Konvergenzordnung $\mathrm{E}\mathrm{O}\mathrm{C}$ in Abhängigkeit von $h$ und $h^{\prime }$ durch

$\mathrm{E}\mathrm{O}\mathrm{C}(h,h^{\prime })=\frac{\log \frac{\Vert u_h-u\Vert }{\Vert u_{h^{\prime }}-u\Vert }}{\log \frac{h}{h^{\prime }}}$

gegeben. Dieser Fall lässt sich durch einen A-priori-Fehlerschätzer der Form

$\Vert u_h-u\Vert \le c{h}^{\alpha }$

mit Konstanten $c,\alpha >0$ motivieren. Wie zuvor wird auch hier vereinfachend Exaktheit

$\Vert u_h-u\Vert =c{h}^{\alpha }$

angenommen. Dies gilt sowohl für die Diskretisierung $h$ als auch für $h^{\prime }$. Durch Division der beiden Gleichungen erhält man

$\frac{\Vert u_h-u\Vert }{\Vert u_{h^{\prime }}-u\Vert }={\left(\frac{h}{h^{\prime }}\right)}^{\alpha }$.

Also gilt

$\alpha ={\log }_{\frac{h}{h^{\prime }}}\frac{\Vert u_h-u\Vert }{\Vert u_{h^{\prime }}-u\Vert }$,

was nach Umrechnung des Logarithmus auf die Basis 10 die Formel für $\mathrm{E}\mathrm{O}\mathrm{C}(h,h^{\prime })$ gibt.

Zusammenhang zur wahren Konvergenzordnung

Mittels der EOC kann keine Konvergenz nachgewiesen werden, da diese vorausgesetzt wird. Liegt ein konvergentes Verfahren vor, so kann im Allgemeinen nicht gesagt werden, ob die tatsächliche Konvergenzrate durch die EOC über- oder unterschätzt wird.