Unter Extrapolation, auch Extrapolation zum Grenzwert oder Extrapolationsverfahren genannt, versteht man eine Klasse von Verfahren zur Beschleunigung der Konvergenz einer gegebenen Folge gegen den gesuchten Grenzwert.

Abhängig von der Struktur der zu beschleunigenden Folge kann man aus einer Vielzahl von Extra-polationsverfahren auswählen. Die Grundidee ist aber stets die gleiche: Unter der Voraussetzung, daß eine zugrundeliegende Folge von (explizit berechenbaren) Werten eine gewisse Struktur aufweist

(s. u.), insbesondere gegen einen i. allg. nicht explizit berechenbaren Grenzwert konvergiert, will man die Konvergenz dieser Folge beschleunigen, um so den gewünschten Wert schneller bzw. in besserer Näherung zu erhalten. Die Extrapolation ist also in diesem Sinne ein Teilgebiet der Numerischen Mathematik.

Sehr weit verbreitet ist wegen ihrer Einfachheit und somit Effizienz die lineare Extrapolation, hier etwa als historisch besonders wichtige Spezialfälle die Richardson-Extrapolation oder das RombergVerfahren.

In neuerer Zeit wendet man aber auch in zunehmendem Maße nichtlineare Extrapolationsverfahren an, hier sind der ϵ-Algorithmus oder der EAlgorithmus gebräuchlich. Im Gegensatz zur linearen Extrapolation können jedoch die nichtlinearen Varianten nicht ohne weiteres auf Folgen von Vektoren oder Matrizen angewandt werden, sondern bedürfen hierfür der Modifikation; weitere Informationen findet man in [1].

Wir geben hier als instruktives Beispiel die Rechenvorschrift für die lineare Extrapolation bei ganzzahligen Exponenten an: Die zu beschleunigende Folge {s(n)} reeller oder komplexer Zahlen besitze eine asymptotische Entwicklung der Form \begin{eqnarray}s(n)={c}_{0}+\displaystyle \sum _{\nu=1}^{\infty }\frac{{c}_{\nu}}{{n}^{\varrho \nu}}\end{eqnarray}

mit festem ϱ ∈ ℝ₊.

Die Iterationsvorschrift zur Extrapolation dieser Folge lautet nun \begin{eqnarray}\begin{array}{cc}{y}_{i}^{(0)}=s({2}^{i}),i=0,1,\ldots, \end{array}\end{eqnarray}\begin{eqnarray}\begin{array}{cc}{y}_{i}^{(k)}=\frac{2{\varrho}^{k}{y}_{i+1}^{(k-1)}-{y}_{i}^{(k-1)}}{2{\varrho}^{k}-1},\left\{\begin{array}{c}k=1,2,\ldots,K,\\ i=0,1,\ldots.\end{array}\right.\end{array}\end{eqnarray}

Dann besitzt jede der Folgen \(\{{y}_{i}^{(k)}\}\) eine asymptotische Entwicklung der Form \begin{eqnarray}{y}_{i}^{(k)}={c}_{0}+\displaystyle \sum _{\nu=k+1}^{\infty }\frac{{c}_{\nu}^{(k)}}{{n}^{\varrho\nu}},\end{eqnarray}

konvergiert also insbesondere schneller gegen den Grenzwert c₀ als \(\{{y}_{i}^{(k-1)}\}\).

Die berechneten Werte werden üblicherweise in einem (halbunendlichen) dreieckförmigen Schema notiert (vgl. Abb.), das man auch Romberg-Schema nennt.

Die o. g. Aussage über die Konvergenz der einzelnen Folgen \(\{{y}_{i}^{(k)}\}\) bedeutet gerade, daß im Romberg-Schema jede Spalte schneller konvergiert als ihre Vorgängerspalte, und insbesondere schneller als die erste, die die Werte der ursprünglichen Folge \({y}_{i}^{(0)}\) enthält.

Die Bezeichnung Extrapolation oder Extrapolation zum Grenzwert leitet sich aus folgender Sichtweise ab: Interpretiert man die Zahlen s(n) als Werte einer Funktion an den natürlichen Zahlen, so ist \({y}_{i}^{(k)}\) der Wert eines geeigneten diese Werte interpolierenden verallgemeinerten Polynoms an der Stelle ∞. Man extrapoliert also durch den o. g. Prozeß das Verhalten dieses Polynoms nach Unendlich.

Eines der wichtigsten Anwendungsgebiete von Extrapolation ist die Extrapolationsmethode für Anfangswertprobleme.

Ein kurzer historischer Abriß soll zeigen, daß Extrapolation seit vielen Jahrhunderten bis in die Neuzeit hinein zu den aktuellen Themen der Mathematik gehört:

In gewissem Sinne beginnt die Geschichte der Extrapolation bereits mit Archimedes und seiner Exhaustionsmethode zur Berechnung des Flächeninhalts des Einheitskreises und damit von π; Archimedes’ Ideen benutzend, berechnete Ludolf van Ceulen im Jahre 1610 die ersten 35 Stellen von π, indem er den Flächeninhalt A_n des regelmäßigen n-Ecks für n = 2⁶²(!) berechnete. Aus diesem Grunde bezeichnete man zeitweise auch π als die Ludolfsche Zahl.

Der erste wirklich methodische Fortschritt gelang Chr. Huygens im Jahre 1654: Mit geometrischen Argumenten kam er zu dem Schluß, daß die Folge { T_n }, definiert durch \begin{eqnarray}{T}_{n}=\frac{4{A}_{2n}-{A}_{n}}{3},\end{eqnarray}

schneller gegen π konvergiert als die Ausgangsfolge { A_n}. Huygens gab somit den ersten Schritt der Extrapolationsvorschrift (2) (für ϱ = 2) an.

Den nächsten wirklichen Meilenstein in der Entwicklung hin zum Extrapolationsverfahren stellt zweifellos ein – damals allerdings wenig beachtetes – Büchlein von J.F.Saigey ([3]) aus dem Jahr 1859 dar; hier bewies der Autor mit rein analytischen Argumenten die Existenz einer asymptotischen Entwicklung der Form (in moderner Notation) \begin{eqnarray}{A}_{n}=\pi +\frac{{c}_{1}}{{n}^{2}}+\frac{{c}_{2}}{{n}^{4}}+\frac{{c}_{3}}{{n}^{6}}+\cdots,\end{eqnarray}

wobei die c_ν feste Koeffizienten sind, und leitete hieraus seine „höheren Approximationen“ an π ab, die aus heutiger Sicht nichts anderes sind als ein erster Spezialfall der o. g. Extrapolationsvorschrift: Bezeichnet man die Ausgangsfolge {A_n} als die Folge der ersten Approximationen, so definiert Saigey die zweiten Approximationen durch \begin{eqnarray}{\tilde{A}}_{n}={A}_{2n}+\frac{{A}_{2n}-{A}_{n}}{3},\end{eqnarray}

die dritten Approximationen durch \begin{eqnarray}{\tilde{B}}_{n}={\tilde{A}}_{2n}+\frac{{\tilde{A}}_{2n}-{\tilde{A}}_{n}}{15},\end{eqnarray}

die vierten Approximationen durch \begin{eqnarray}{C}_{n}={B}_{2n}+\frac{{B}_{2n}-{B}_{n}}{63},\end{eqnarray}

und so weiter. Saigey war also der erste, der einen Spezialfall des Extrapolationsprozesses (2) in iterativer Form angab, und das bereits 100 Jahre vor Romberg’s bahnbrechender Arbeit.

Erwähnt sei hier auch noch das Buch [2] von K.Kommerell aus dem Jahre 1936, worin ebenfalls bereits ein Berechnungsalgorithmus für π, ein Spezialfall von (2), in iterativer Form angegeben wird.

Abseits der Berechnung von π gibt es noch ein zweites, bis heute hochaktuelles Anwendungsgebiet für Extrapolation: Die numerische Lösung von Differentialgleichungen.

Hier ist es eine Arbeit aus dem Jahre 1927 von Richardson und Gaunt, die als Keimzelle aller Extrapolationsverfahren gesehen wird; aus diesem Grunde spricht man manchmal auch von „Richardson-Extrapolation“.

In dieser Arbeit wurde – wiederum für den Spezialfall ϱ = 2 – der erste Schritt der Vorschrift (2) angegeben. In einer Anmerkung notieren die Autoren, daß es wohl keinen Sinn macht, das Verfahren in iterativer Form zu formulieren, da der entsprechende Genauigkeitsgewinn wohl nur marginal wäre. Aus heutiger Sicht eine Fehleinschätzung.

Der große, bis heute andauernde Durchbruch der Extrapolationsverfahren kam dann im Jahre 1955 mit einer kurzen, mittlerweile berühmten Arbeit von Werner Romberg über „Vereinfachte Numerische Integration“. Wenngleich Romberg selbst keine iterative Formulierung „seines“ Verfahrens angab (er formulierte lediglich, ausgehend von der Trapezregel, verbesserte Formeln zur numerischen Integration, die sich dann wiederum als explizite Formulierungen der sich durch den Extrapolationsprozeß ergebenden neuen Folgen herausstellten),

so gab diese Arbeit doch den Anstoß zu einer heute nicht mehr zu überblickenden Anzahl von Publikationen bzw. Untersuchungen zum Thema Extrapolation. Viele Autoren sprechen daher auch anstelle von Extrapolation vom „Rombergschen Prinzip“ oder vom „verallgemeinerten Romberg-Verfahren“.

Abschließend sei noch auf die Monographien [1] und [4] hingewiesen, in denen man eine Fülle von Informationen zum hier behandelten Thema findet.

Literatur

[1] Brezinski, C.; Redivo Zaglia, M.: Extrapolation Methods: Theory and Practice. North-Holland Amsterdam, 1991.

[2] Kommerell, K.: Das Grenzgebiet der elementaren und höheren Mathematik. Köhler Leipzig, 1936.

[3] Saigey, J.F.: Problèmes d’arithmétique et exercises de cacul du second degré avec les solutions raisonnées. L.Hachette Paris, 1859.

[4]Walz, G.: Asymptotics and Extrapolation. Akademie-Verlag Berlin, 1996.