Asymptotische Analyse
In der Mathematik und ihren Anwendungen, insbesondere in der Komplexitätstheorie, bezeichnet asymptotische Analyse eine Methode um das Grenzwertverhalten von Funktionen zu klassifizieren, indem man nur den wesentlichen Trend des Grenzwertverhaltens beschreibt.Beschreibung des asymptotischen Verhaltens
Das asymptotische Verhalten lässt sich beispielsweise mit Äquivalenzrelationen von Funktionen definieren. Sind beispielsweise f und g reellwertige Funktionen natürlicher_Zahlen n, so lässt sich eine Äquivalenzrelation definieren durch
:
genau dann wenn
:.
Die Äquivalenzklassen von f bestehen aus allen Funktionen h mit ähnlichem Wachstumsverhalten beim Grenzwert .
Landau Notation
Eine nützliche Notation zur Beschreibung der Wachstumsklassen ist die Landau-Notation, die ursprünglich von Paul Bachmann stammt, aber durch Edmund Landau bekannt gemacht wurde. Eine wichtige Anwendung der Landau-Notation ist die Komplexitätstheorie, in der die asymptotische_Laufzeit und Speicherverbrauch eines Algorithmus' untersucht wird.
Die einfachste Art, diese Symbole zu definieren, ist die folgende: sind Klassen von Funktionen mit den folgenden Eigenschaften.
:
:
:
wird in der Regel aus dem Kontext klar. Weiter schreibt man gerne statt das Folgende:
Asymptotische Entwicklung
Unter einer asymptotischen Entwicklung einer Funktion f(x) versteht man die Darstellung der Funktion als divergente (oder zumindest nicht notwendigerweise konvergente) Reihe. Die Partialsummen dieser Reihe konvergieren nicht, liefern aber gute Näherungen für den Funktionswert. Das bekannteste Beispiel einer asymptotischen Entwicklung ist die Stirling-Formel als asymptotische Entwicklung für die Fakultät. Darstellen lässt sich die Entwicklung immer über eine asymptotische Folge als
:
mit der Eigenschaft, dass .
Falls die asymptotische Entwicklung nicht konvergiert, gibt es für jedes Funktionsargument x einen Index k, bei dem der Approximationsfehler
:
am kleinsten wird; Hinzufügen weiterer Terme verschlechtert die Approximation. Der Index k der besten Approximation wird bei asymptotischen Entwicklungen aber desto größer, je größer x ist.
Asymptotische Entwicklungen treten insbesondere bei der Approximation gewisser Integrale auf, beispielsweise mit der Sattelpunktmethode.
Literatur
* Erdélyi, A.: Asymptotic Expansions, New York: Dover, 1987.
