Gutensohn
[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]

Konvergenzbeschleunigung

Methoden zur Konvergenzbeschleunigung dienen der Reduktion des Rechenaufwandes, welcher bei langsam konvergierenden Folgen oft gegeben ist.


Delta2-Verfahren:

Voraussetzungen:

{x(k)}ist eine linear konvergente Folge mit dem Grenzwert x* und dem Konvergenzfaktor a < 1, sodaß gilt:

$\underset{k\rightarrow \infty }{\lim }\frac{\left| x^{(k+1)}-x^{*}\right|}{\left| x^{(k)}-x^{*}\right| }$ =\thinspace a \TEXTsymbol{<} 1

Um das Delta2-Verfahren zu motivieren, wird zunächst angenommen, daß

$x^{(k)}-x^{*},x^{(k+1)}-x^{*},x^{(k+2)}-x^{*}$

alle gleiches Vorzeichen haben und k groß genug ist, damit:

$\frac{x^{(k+1)}-x^{*}}{x^{(k)}-x^{*}}$ $\approx $ a $\approx $$\frac{x^{(k+2)}-x^{*}}{x^{(k)}-x^{*}}$

gilt.

Durch umformen gelangt man zur Möglichkeit der Generierung einer neuen Folge wie folgt:

$y^{(k)}:=$x$^{(k)}-\frac{(x^{(k+1)}-x^{(k)})^2}{x^{(k+2)}-2x^{(k+1)}+x^{(k)}}$

Wird auf diese Art die Folge {x(k)} in die neue Folge {y(k)} überführt, so konvergiert die neue Folge rascher als die Ursprüngliche gegen den Grenzwert und man spricht vom Delta2-Verfahren.

Die Bezeichnung des Verfahrens stammt von der Differenzenschreibweise

\EQN{7}{1}{}{}{\RD{\CELL{\Delta x^{(k)}&:&=x^{(k+1)}-x^{(k)},}}{1}{}{}{}\RD{\CELL{\Delta ^2x^{(k)}:=\Delta(x^{(k+1)}-x^{(k)})=\Delta x^{(k+1)}-\Delta x^{(k)}=}}{1}{}{}{}\RD{\CELL{&&x^{(k+2)}-2x^{(k+1)}+x^{(k)}}}{1}{}{}{}}

mit der sich für das Delta2-Verfahren

$y^{(k)}:=$ x$^{(k)}-\frac{(\Delta x^{(k)})^2}{\Delta x^{(k)}}$

ergibt.


Steffensen-Verfahren:

Wenn die Delta2-Beschleunigung nicht erst nach Vorliegen aller Werte von {x(k)}angewendet wird, sondern so oft wie möglich, d. h. erstmals nach zwei Iterationsschritten - der Verfügbarkeit von drei Werten einer Folge -, spricht man vom Steffensen-Verfahren.

Siehe auch Extrapolation.

[ < ] [ globale Übersicht ] [ Kapitelübersicht ] [ Stichwortsuche ] [ > ]