epsilonAlgorithmus

Der Epsilon-Algorithmus, auch Epsilon-Transformation genannt, ist eine Methode der numerischen Analyse zur Beschleunigung der Konvergenz von Folgen und zur Summation von unendlichen Reihen. Er wurde in den 1950er Jahren von Peter Wynn entwickelt und gehört zu den transformierenden Verfahren, die aus einer gegebenen Folge schneller konvergente Annäherungen ableiten.

Die Methode arbeitet mit einer zweidimensionalen Tabelle ε(k,n). Die Startwerte sind ε(0,n) = s_n, wobei s_n die n-te Partialsumme der zu beschleunigenden Folge ist, und ε(-1,n) = 0. Rekursionsrelation: ε(k+1,n) = ε(k-1,n+1) + 1 / (ε(k,n+1) - ε(k,n)). Der Ausbau der Terme liefert eine Sequenz von Annäherungen; insbesondere die glatten even-Terme ε(2m,0) nähert gewöhnlich den Grenzwert der Folge schneller an als die Originalfolge.

Anwendungsgebiete umfassen die Beschleunigung der Konvergenz langsamer Reihen und die Extrapolation von Funktionswerten aus unvollständigen Daten. Der Algorithmus ist eng verwandt mit der Shanks-Transformation und der Theorie der Padé-Approximation. Numerische Stabilität kann eine Beschränkung darstellen, insbesondere wenn die Differenzen ε(k,n+1) - ε(k,n) nahe Null liegen. Die Kosten belaufen sich typischerweise auf O(n^2) Operationen für n betrachtete Elemente.

Geschichte und Rezeption: Wynn führte den Algorithmus in den 1950er Jahren in der Fachliteratur ein; seitdem wird er in Lehrbüchern und Softwarepaketen zur Konvergenzverbesserung beschrieben. Varianten existieren, die sich auf spezielle Arten von Folgen oder auf robuste numerische Berechnung konzentrieren.

Siehe auch: Shanks-Transformation, Levin-Transformation, Padé-Transformation.