Stirlingformel + O-Notation?
Hallo, ich habe leider etwas Probleme diese Form der Stirlingformel (siehe unten)in Verbindung mit der O-Notation zu verstehen. Leider ist mir unklar wie ich das Theta 1/n verstehen muss, da ich es immer als eine Art Menge von Funktionen aufgefasst habe und das für mich in diesem Kontext nicht wirklich Sinn ergibt. Kennt sich jemand damit aus und kann es mir erklären?
Über eine Antwort würde ich mich sehr freuen.
MfG
1 Antwort
Bei dem "O" (eigentlich ein großes Teta), handelt es sich um eine Schreibweise für die dominierende Ordnung der Funktionen an dieser Stelle, für große n.
Das bedeutet an der Stelle von O(1/n) steht tatsächlich etwas wie:
A/n + B/n^2 + C/n^3 + ...
Also ein Term welcher proportional zu 1/n ist und weitere Terme, welche für große n kleiner sind als 1/n.
Die Idee ist die, dass man nun weiß, wie groß der Fehler der Approximation (ohne das O(1/n)) ist und letztlich abschätzen kann ob ein gegebenes n hinreichend klein ist, damit die Näherung passable Ergebnisse liefert.
Die Vorstellung als eine Menge von Funktionen ist also nicht so falsch, besser ist aber die Vorstellung, dass sich hier eine nicht weiter spezifizierte Funktion befindet, welche sich wie 1/n verhält. Dies ist durchaus eine Einschränkung auf eine gewisse Menge von Funktionen, in der Regel steht an der Stelle aber eine konkrete Funktion, deren genauer Verlauf lediglich nicht von Belang ist.
Im Vorliegenden Beispiel kannst du auf Wikipedia (https://de.m.wikipedia.org/wiki/Stirlingformel) leicht nachlesen, welche Funktion hier steht:
1/(12n) - 1/(360n^3) + ...
Du wirst desweiteren erkennen, dass schon für n=10 der Faktor 1/n relativ nahe bei Null liegt.
Ich hoffe das hilft.
Zunächst mal ja, die Approximation wird besser je größer n ist.
In der Formel oben steht ein Faktor 1+O(1/n), wenn nun zB für n=10 und folglich 1/n = 0.1 gilt, weißt du sofort, dass dein Fehler in der Größenordnung von 10% liegen wird. Ob das akzeptabel ist, hängt natürlich von der Problemstellung ab.
Zur Verständnisfrage: Die Stirlingformel ist, wie du sagst eine Näherung für die Fakultät. Um diese zu erhalten hat man bestimmte mathematische Techniken verwendet, welche auch genauere Approximationen zulassen und darum weiß man, wie sich der Fehler verhält.
Grundsätzlich könnte man absolut einen Term wie 1/n (allerdings mit Proportionalitätskonstante) verwenden um eine bessere Näherung, auch für kleinere n zu erhalten. Die Idee ist gut und wird auch so verwendet. Im vorliegenden Fall will man aber nur illustrieren, wie gut die gezeigte Näherung ist.
Vielen Dank schon mal :)
Ich hätte aber doch noch die ein oder andere kleine Frage zu diesem Abschnitt
Woher weiß ich nun, wie groß der Fehler meiner Approximation ist (einfach nur die Fakultät berechnen und mit dem Ergebnis der Stirling Formel vergleichen ?) und führt nicht ein möglichst großes n zu einer besseren Näherung?
Zudem wollte ich noch testen, ob ich das richtig verstanden habe. Also die Stirling Formel ist ja eine Funktion die sich der Fakultät bzw. Gammafunktion annähert, jedoch ist diese Approximation (besonders für kleine n) nicht optimal, weswegen wir Funktionen aus Theta 1/n verwenden um diese Fehler zu korrigieren. Welche Funktion dabei genau verwendet wird hängt dabei von der Eingabe n ab (?).
Stimmt das soweit und habe ich etwas wichtiges vergessen?
MfG