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äßt sich mit

$f\; \backslash sim\; g$

genau dann wenn

$\backslash frac\{f(n)\}\{g(n)\}\; \backslash to\; 1\; \backslash mathrm\{\backslash \; f\backslash ddot\{u\}r\backslash \; \}\; n\backslash to\backslash infty$.

eine Äquivalenzrelation definieren. Die Äquivalenzklassen von f bestehen aus allen Funktionen h mit ähnlichem Wachstumsverhalten beim Grenzwert $n\backslash to\backslash infty$.

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.

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 $(\backslash phi\_n)$ mit der Eigenschaft, dass $\backslash phi\_\{n+1\}(x)\; =\; \backslash hbox\{o\}(\backslash phi\_n(x)),\; \backslash ;\; x\; \backslash to\; x\_0$ als

$f(x)\; =\; \backslash sum\_\{i=1\}^N\; a\_i\backslash phi\_i(x)\; +\; \backslash hbox\{o\}(\backslash phi\_N(x))$.

Wenn die asymptotische Entwicklung nicht konvergiert, gibt es für jedes Funktionsargument x einen Index k, bei dem der Approximationsfehler

$f(x)-\backslash sum\_\{i=1\}^k\; a\_i\backslash phi\_i(x)$

am kleinsten wird; hinzufügen weiterer Terme verschlechtert die Approximation. Dieser Index k, der die beste Approximation angibt, wird bei asymptotischen Entwicklungen aber umso größer, je größer x ist.

Asymptotische Entwicklungen treten insbesondere bei der Approximation gewisser Integrale auf, beispielsweise mit der saddle-point method.

Literatur

---

• Erdélyi, A.: Asymptotic Expansions, New York: Dover, 1987.

Analysis

Asymptotic analysis