Konvergenzgeschwindigkeit

Unter Konvergenzgeschwindigkeit (auch Konvergenzordnung) versteht man die Geschwindigkeit, mit der sich die Glieder einer konvergenten Folge ${\displaystyle \left(s_{n}\right)_{n\in \mathbb {N} }}$ dem Grenzwert ${\displaystyle s}$ 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

Sei ${\displaystyle \left(s_{k}\right)_{k\in \mathbb {N} }}$ eine Folge mit dem Grenzwert ${\displaystyle s}$. Zur Vermeidung nebensächlicher Fallunter­scheidungen seien Glieder mit ${\displaystyle s_{k}=s}$ und andere Wiederholungen weggelassen.

Lineare Konvergenz liegt vor, falls

${\displaystyle c:=\limsup _{k\to \infty }c_{k}<1}$   mit   ${\displaystyle c_{k}:={\frac {|s_{k+1}-s|}{|s_{k}-s|}}}$.

Manche Autoren bezeichnen ${\displaystyle c}$ als die Konvergenzrate (engl. rate of convergence, franz. taux de convergence). Je kleiner ${\displaystyle c}$, desto schneller konvergiert die Folge, will sagen: desto weniger Glieder werden benötigt, um eine vorgegebene Genauigkeit zu erreichen.

Unterlineare oder sublineare Konvergenz liegt vor bei ${\displaystyle c=1}$. Konvergiert die Folge unterlinear und gilt zusätzlich

${\displaystyle \lim _{k\to \infty }{\frac {|s_{k+2}-s_{k+1}|}{|s_{k+1}-s_{k}|}}=1}$,

dann spricht man von logarithmischer Konvergenz.

Superlineare Konvergenz liegt vor, wenn es eine gegen Null konvergente Zahlenfolge ${\displaystyle (c_{k})}$ gibt mit:

${\displaystyle |s_{k+1}-s|\leq c_{k}|s_{k}-s|,\;k=0,1,\dotsc }$

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

Konvergenz der Ordnung q (oder Q-Konvergenzordnung (≥) q) mit ${\displaystyle q>1}$ liegt vor, wenn ${\displaystyle (s_{k})}$ konvergiert und ein ${\displaystyle c>0}$ existiert, sodass

${\displaystyle |s_{k+1}-s|\leq c\,|s_{k}-s|^{q},\;k=0,1,\dotsc }$

In der Literatur finden sich auch Formulierungen wie „konvergiert mit der Q-Ordnung (wenigstens) ${\displaystyle q}$“ (englisch converges with Q-order at least ${\displaystyle q}$) für denselben Sachverhalt.^[1] Das Q kommt von Quotient, weil die Q-Ordnung über den Quotienten zweier aufeinanderfolgender Terme definiert ist. Konvergiert die Folge ${\displaystyle \left(s_{n}\right)}$ mit einer Q-Ordnung ${\displaystyle \geq q}$, dann konvergiert sie auch mit der Q-Ordnung ${\displaystyle \geq q^{\prime }}$ für jedes ${\displaystyle q^{\prime }}$ mit ${\displaystyle 1<q^{\prime }\leq q}$.

Man sagt, die Folge ${\displaystyle \left(s_{n}\right)}$ hat die exakte Q-Ordnung q, wenn es positive ${\displaystyle a,b}$ mit

${\displaystyle a|s_{k}-s|^{q}\leq |s_{k+1}-s|\leq b\,|s_{k}-s|^{q},\;k=0,1,\dotsc }$

gibt. Die exakte Q-Ordnung ${\displaystyle q}$ ist eindeutig, wenn sie existiert:

${\displaystyle q=\lim _{k\to \infty }{\frac {\log {\left|{\frac {s_{k+1}-s_{k}}{s_{k}-s_{k-1}}}\right|}}{\log {\left|{\frac {s_{k}-s_{k-1}}{s_{k-1}-s_{k-2}}}\right|}}}}$

Für ${\displaystyle q=2}$ spricht man von quadratischer Konvergenz. Konvergenz der Ordnung ${\displaystyle q>1}$ impliziert superlineare Konvergenz (die "Konvergenzrate" ${\displaystyle (c_{k})}$ ist eine Nullfolge) und superlineare Konvergenz impliziert lineare Konvergenz.

Konvergenz der Ordnung ${\displaystyle q>1}$ bedeutet, dass in jedem Iterationsschritt die Anzahl der genauen Dezimalstellen (oder die Anzahl der Stellen in einem beliebigen Stellenwertsystem) in etwa ver-${\displaystyle q}$-facht wird, also beispielsweise bei quadratischer Konvergenz verdoppelt.

Konvergenzbeschleunigung beschränkt sich meist auf Potenzreihen, die linear konvergieren. Dabei wird i. d. R. nur die Konvergenzrate ${\displaystyle c}$ (und nicht die Q-Ordnung ${\displaystyle q}$) verbessert, was trotzdem eine wesentliche Verringerung des Gesamtaufwands (bei ggf. größerem Aufwand pro Iteration) bedeuten kann. Verfahren der Ordnungen >1 gibt es nicht zu jeder Problemklasse. Bei Iterationsverfahren müssen auch Stabilitätseigenschaften beobachtet werden.

Beispiele

• Die Leibniz-Reihe

${\displaystyle \arctan 1=\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{2k+1}}=1-{\frac {1}{3}}+{\frac {1}{5}}-{\frac {1}{7}}+{\frac {1}{9}}-\dotsb ={\frac {\pi }{4}}}$

konvergiert logarithmisch.

• Die von Euler entdeckte Reihe

${\displaystyle \zeta (2)=\sum _{k=1}^{\infty }{\frac {1}{k^{2}}}={\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\dotsb ={\frac {\pi ^{2}}{6}}}$

konvergiert unterlinear.

• Die Machinsche Reihe

${\displaystyle 4\arctan {\frac {1}{5}}-\arctan {\frac {1}{239}}={\frac {4}{5^{1}}}-{\frac {1}{239^{1}}}-{\frac {4}{3\cdot 5^{3}}}+{\frac {1}{3\cdot 239^{3}}}+{\frac {4}{5\cdot 5^{5}}}-{\frac {1}{5\cdot 239^{5}}}-\dotsb ={\frac {\pi }{4}}}$

konvergiert linear mit der Konvergenzrate ${\displaystyle c=1/25}$.

• Die Exponentialreihe

${\displaystyle \sum _{n=0}^{\infty }{\frac {x^{n}}{n!}}=1+x+{\frac {x^{2}}{2!}}+{\frac {x^{3}}{3!}}+{\frac {x^{4}}{4!}}+\dotsb =\exp(x)}$

hat Q-Konvergenzordnung ${\displaystyle \geq 1}$ für alle ${\displaystyle x\in \mathbb {C} }$.

• Die Nullfolge ${\displaystyle \left(s_{k}\right)_{k\in \mathbb {N} _{0}}}$ mit

${\displaystyle s_{k}={\frac {1}{2^{2^{k}}}}}$, also ${\displaystyle s_{0}={\frac {1}{2}},\,s_{1}={\frac {1}{4}},\,s_{2}={\frac {1}{16}},\,s_{3}={\frac {1}{256}},\,s_{4}={\frac {1}{65536}},\,\dotsc }$,

konvergiert quadratisch.

• Das Newton-Verfahren konvergiert bei einer einfachen Nullstelle quadratisch. 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 ${\displaystyle q={\tfrac {1+{\sqrt {5}}}{2}}}$ (goldener Schnitt), es konvergiert insbesondere superlinear.

Vergleichende Konvergenzgeschwindigkeit

Um die Konvergenzgeschwindigkeit zu beschreiben, mit der eine Folge ${\displaystyle (s_{n})}$ gegen den Grenzwert ${\displaystyle s}$ konvergiert, vergleicht man die Konvergenzgeschwindigkeit der Nullfolge ${\displaystyle (a_{n}):=(s-s_{n})}$ mit anderen Nullfolgen, deren Konvergenzgeschwindigkeit man kennt, wie z. B. ${\displaystyle (n^{-a})}$, ${\displaystyle (n^{-a}\log n)}$ für ${\displaystyle a>0}$, ${\displaystyle (q^{n})}$ für ${\displaystyle 0<q<1}$ oder ${\displaystyle \left(e^{-2^{n}}\right)}$.

Definition

Man sagt, eine Nullfolge ${\displaystyle (a_{n})}$ konvergiert mindestens so schnell wie eine Nullfolge ${\displaystyle (b_{n})}$, wenn gilt ${\displaystyle \sup |a_{n}/b_{n}|<\infty }$.

Eine Folge ${\displaystyle (a_{n})}$ heißt schnell fallend, wenn sie schneller als jede polynomische Folge ${\displaystyle (n^{-m})}$ mit natürlichem ${\displaystyle m}$ fällt, also ${\displaystyle \sup |a_{n}|n^{m}<\infty }$ für jedes ${\displaystyle m}$ (ein Beispiel ist etwa die Folge ${\displaystyle \left(e^{-n}\right)}$.)

Von besonderem Interesse ist daher die Beschreibung der Konvergenzordnung numerischer Verfahren in normierten Räumen, wo also die Folgenglieder die Gestalt ${\displaystyle \|s-s_{n}\|}$ haben.

Im Sinne dieser Definition nennt man ein Iterationsverfahren linear konvergent, wenn es so schnell wie die Folge ${\displaystyle \left(e^{-cn}\right)}$ für ein ${\displaystyle c>0}$ konvergiert. Man nennt es quadratisch konvergent, wenn es so schnell wie die Folge ${\displaystyle \left(e^{-c2^{n}}\right)}$ konvergiert. Ebenso lassen sich auch höhere Konvergenzordnungen (kubisch, superlinear) definieren.

Beliebig langsame Konvergenz

Viele wichtige numerische Verfahren sind beliebig langsam konvergent. Sei beispielsweise ${\displaystyle X}$ ein Banachraum, ${\displaystyle (X_{n})}$ eine Folge von ${\displaystyle n}$-dimensionalen Teilräumen und ${\displaystyle \mathbf {V} }$ ein Verfahren, das zu jeder Lösung einer Gleichung ${\displaystyle f(x)=y}$ eine angenäherte Lösung ${\displaystyle x_{n}}$ in ${\displaystyle X_{n}}$ liefert. Das Verfahren ${\displaystyle \mathbf {V} }$ heißt dann beliebig langsam konvergent, wenn es zu jeder positiven Nullfolge ${\displaystyle (a_{n})}$ ein ${\displaystyle y}$ gibt, sodass die Nullfolge ${\displaystyle (x-x_{n})}$ mit ${\displaystyle f(x)=y}$ und den zugehörigen angenäherten Lösungen ${\displaystyle x_{n}}$ langsamer als die Folge ${\displaystyle (a_{n})}$ 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 0 konvergierenden monotonen Folge positiver Zahlen gibt es eine stetige Funktion ${\displaystyle f}$, sodass die Folge der Quadraturwerte langsamer gegen das Integral konvergiert 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 ${\displaystyle p}$ mit der Konvergenzgeschwindigkeit ${\displaystyle {\mathcal {O}}\left(p^{-n-a}\right)}$ für ein ${\displaystyle a>0}$ approximierbar, so ist sie ${\displaystyle n}$-fach differenzierbar.

Fourier-Koeffizienten

Für Fourier-Koeffizienten funktioniert das in beide Richtungen: Die Konvergenzgeschwindigkeit der Koeffizienten impliziert den Grad der Differenzierbarkeit und vice versa.

Sei ${\displaystyle f\in L^{2}[-\pi ,\pi ]}$ eine über dem Intervall ${\displaystyle [-\pi ,\pi ]}$ quadratisch integrierbare Funktion, und seien ${\displaystyle {\hat {f_{k}}}=(2\pi )^{-1}\int _{-\pi }^{\pi }\exp(-\mathrm {i} kx)f(x)dx}$ für ${\displaystyle k\in \mathbb {N} }$ die Fourier-Koeffizienten. Dann gilt für ${\displaystyle n\in \mathbb {N} _{0}}$:

• Ist ${\displaystyle f\in C^{n}[-\pi ,\pi ]}$ eine über ${\displaystyle [-\pi ,\pi ]}$ ${\displaystyle n}$-mal stetig differenzierbare Funktion, dann ist ${\displaystyle |{\hat {f_{k}}}|\leq {\frac {M}{|k|^{n}}}}$ mit ${\displaystyle M:=\sup _{x\in [-\pi ,\pi ]}|f^{(n)}(x)|.}$
• Gibt es ${\displaystyle D,\varepsilon >0}$ mit ${\displaystyle |{\hat {f_{k}}}|\leq {\frac {D}{|k|^{n+1+\varepsilon }}}}$, dann ist ${\displaystyle f\in C^{n}[-\pi ,\pi ].}$

Siehe auch

• Landau-Symbole
• Experimentelle Konvergenzordnung

Literatur

• Hans R. Schwarz, Norbert Köckler: Numerische Mathematik. 5. Auflage. Teubner, Stuttgart 2004.
• 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.

Einzelnachweise

1. ↑ F. A. Potra: On Q-order and R-order of convergence. In: J. Optim. Th. Appl. 63. Jahrgang, Nr. 3, 1989, S. 415–431, doi:10.1007/BF00939805.