Konvergenzgeschwindigkeit - LinkFang.de





Konvergenzgeschwindigkeit


Unter Konvergenzgeschwindigkeit (auch Konvergenzordnung) versteht man die Geschwindigkeit, mit der sich die Glieder einer konvergenten Folge ([math]x_n[/math]) dem Grenzwert x nähern. In der numerischen Mathematik ist die Konvergenzgeschwindigkeit ein wichtiges Qualitätsmerkmal iterativer Verfahren, neben dem Rechenaufwand pro Iteration und der numerischen Stabilität.

Konvergenzordnung bei Iterationsverfahren

Man unterscheidet zwischen linearer, superlinearer sowie p-ter Konvergenzordnung.

Lineare Konvergenz liegt vor, falls es ein 0<c<1 gibt, so dass

[math] \|x_{k+1}-x\| \leq c\|x_{k}-x\|, k=0,1,... [/math]

Superlineare Konvergenz liegt vor, wenn die obige Ungleichung nicht nur mit einem konstanten c gilt, sondern sogar mit einer gegen Null konvergenten Zahlenfolge ([math]c_k[/math]):

[math] \|x_{k+1}-x\| \leq c_k\|x_{k}-x\|, k=0,1,... [/math]

Eine Folge, die superlinear konvergiert, konvergiert also schneller als linear.

Konvergenz der Ordnung p mit p>1 liegt vor, wenn ([math]x_k[/math]) konvergiert und ein c>0 existiert, so dass

[math] \|x_{k+1}-x\| \leq c\|x_{k}-x\|^{p}, k=0,1,... [/math]

Für p=2 spricht man von quadratischer Konvergenz. Konvergenz der Ordnung p impliziert superlineare Konvergenz und superlineare Konvergenz impliziert lineare Konvergenz.

Der Begriff ist vor allem in der Numerik wichtig, wo eine Näherung des Grenzwertes eines Iterationsverfahrens meist durch Berechnung einer kleinen Anzahl von Folgengliedern geschieht. Konvergenz der Ordnung p bedeutet dann, dass in jedem Iterationsschritt die Anzahl der genauen Dezimalstellen (bzw. Stellen in einem beliebigen Stellenwertsystem) ver-[math]p[/math]-facht werden, also beispielsweise bei quadratischer Konvergenz verdoppelt.

Die schnellere Konvergenz von Verfahren höherer Ordnung wird meist mit größerem Aufwand pro Iteration bezahlt, in vielen Fällen auch mit schlechteren Stabilitätseigenschaften oder Einschränkungen an die behandelbaren Problemklassen (z. B. Forderung nach höherer Differenzierbarkeitsordnung der Daten).

Beispiele

  • Das Newton-Verfahren konvergiert bei einer einfachen Nullstelle mit zweiter Ordnung. Vereinfachte Varianten des Newton-Verfahrens konvergieren langsamer, teilweise superlinear, teilweise mit erster Ordnung. Im Vergleich zum Newton-Verfahren ist ein Iterationsschritt aber möglicherweise deutlich günstiger.
  • Fixpunktverfahren, deren Konvergenz mit dem Fixpunktsatz von Banach nachgewiesen ist (beispielsweise Splitting-Verfahren), haben mindestens lineare Konvergenzgeschwindigkeit.
  • Das Sekantenverfahren hat eine gebrochene Konvergenzordnung mit p = ½ (1+√5) (goldener Schnitt), es konvergiert insbesondere superlinear.

Allgemeine Definition der Konvergenzgeschwindigkeit

Um die Konvergenzgeschwindigkeit zu beschreiben, mit der eine Folge ([math]x_n[/math]) gegen den Grenzwert x konvergiert, vergleicht man die Konvergenzgeschwindigkeit der Nullfolge [math](a_n) = (x - x_n)[/math] mit gewissen anderen Nullfolgen, für deren Konvergenzgeschwindigkeit man ein gutes Gefühl hat wie z. B. [math](n^{-a})[/math], [math](n^{-a} \log n)[/math] für [math]a\gt0[/math], [math](q^n)[/math] für 0<q<1 oder [math](e^{-2^n})[/math].

Definition

Man sagt, eine Nullfolge ([math]a_n[/math]) konvergiert mindestens so schnell wie eine Nullfolge ([math]b_n[/math]), wenn gilt [math]\sup |a_n /b_n| \lt \infty[/math].

Eine Folge ([math]a_n[/math]) heißt schnell fallend, wenn sie schneller als jede Folge der Art ([math]n^{-k}[/math]), k eine natürliche Zahl, fällt, also [math]\sup |a_n| n^k \lt \infty[/math] für jedes k (ein Beispiel ist etwa die Folge [math]\left(e^{-n}\right)[/math].)

Von besonderem Interesse ist also die Beschreibung der Konvergenzordnung numerischer Verfahren in normierten Räumen, wo also die Folgenglieder die Gestalt [math]\|x-x_n \|[/math] haben.

Im Sinne dieser Definition nennt man ein Iterationsverfahren linear konvergent, wenn es so schnell wie die Folge ([math]q^n[/math]) mit 0<q<1 konvergiert. Man nennt es quadratisch konvergent, wenn es so schnell wie die Folge [math]\left(e^{-2^n}\right)[/math] konvergiert. Ebenso lassen sich auch höhere Konvergenzordnungen (kubisch, superlinear) definieren.

Beliebig langsame Konvergenz

Viele wichtige numerische Verfahren sind beliebig langsam konvergent. Sei also X ein Banachraum und [math]X_n[/math] eine Folge von n-dimensionalen Teilräumen und sei V ein Verfahren, das zu jeder Lösung einer Gleichung [math]f(x) = y[/math] eine angenäherte Lösung [math]x_n[/math] in [math]X_n[/math] liefert. Das Verfahren V heißt dann beliebig langsam konvergent, wenn es zu jeder positiven Nullfolge [math](a_n)[/math] ein y gibt, so dass [math](x-x_n)[/math] für die zugehörigen angenäherten Lösungen [math]x_n[/math] langsamer als die Folge [math](a_n)[/math] konvergiert.

Setzt man z. B. bei der numerischen Integration nur die Stetigkeit der zu integrierenden Funktion voraus, nicht aber eine gewisse Differenzierbarkeitsordnung, so ist das Verfahren der numerischen Integration beliebig langsam konvergent, d. h. zu jeder beliebig langsam gegen Null konvergierenden monotonen Folge positiver Zahlen gibt es eine stetige Funktion f, so dass die Folge der Quadraturwerte langsamer gegen das Integral konvergieren als die gegebene Nullfolge. Andere Beispiele findet man bei der Interpolation oder der Lösung inkorrekt gestellter Probleme.

Umgekehrte Resultate

In etlichen Disziplinen der Analysis lassen sich aus der Konvergenzgeschwindigkeit Erkenntnisse über die Struktur des zu untersuchenden Problems gewinnen. Als Beispiel seien die Bernstein­sätze aus der Approximationstheorie erwähnt: Ist eine stetige Funktion durch Polynome vom Grad n mit der Konvergenzgeschwindigkeit [math]\mathcal{O}(n^{-k-a})[/math] für ein a>0 approximierbar, so ist sie k-fach differenzierbar.

Kritik an dem Konzept

Oftmals ist man lediglich an einem Verfahren interessiert, welches schnell ([math]k\leq 10[/math]) eine bestimmte Genauigkeit, z. B. IEEE-double precision,

[math] \|x_{k}-x\| \lt \epsilon [/math]

erreicht. Dafür ist es jedoch zweitrangig, ob das Verfahren für große [math]k[/math], beispielsweise [math]k\gt100[/math], lineare, quadratische oder kubische Konvergenzgeschwindigkeit besitzt.

Siehe auch

Literatur

  • Martin Hanke-Bourgeois, Grundlagen der Numerischen Mathematik und des Wissenschaftlichen Rechnens, Teubner, Stuttgart 2002
  • Arnold Schönhage, Approximationstheorie, de Gruyter, Berlin 1971
  • Eberhard Schock, Arbitrarily Slow Convergence, Uniform Convergence and Superconvergence of Galerkin-like Methods, IMA J. Numer. Analysis 5 (1985) 153-160
  • Hans R. Schwarz, Norbert Köckler: Numerische Mathematik. 5. Auflage. Teubner, Stuttgart 2004,

Kategorien: Numerische Mathematik

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Konvergenzgeschwindigkeit (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.