Archimedes vs. Monte Carlo < Algorithmen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:28 Fr 28.11.2014 | | Autor: | Muskat |
Hi,
kann mir jemand etwas über die Verlässlichkeit/Genauigkeit des Monte Carlo Verfahrens bzw. Archimedes-Methode in Bezug auf das Ergebnis (Pi) sagen.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:49 Fr 28.11.2014 | | Autor: | chrisno |
Da gibt es hier deutlich kompetentere als mich. Monte-Carlo konvergiert langsam. Bei der Genauigkeit wird erst einmal die Feinheit der Einteilung maßgeblich sein (vermute ich).
Archimedes dürfte schneller konvergieren, da solltest Du aber schauen, wie es mit der Rechengenauigkeit steht.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:30 Mo 04.05.2015 | | Autor: | bezier |
Hallo,
Die Formeln von Ramanujan für Pi sind rechen Pi schnell und sind hoch-effizient.
Gruss.
|
|
|
| |
|
Hallo!
Im Prinzip hat Chrisno schon alles wichtige gesagt.
Archimedes konvergiert monoton. Mit jeder Erhöhung der Eckenzahl nähert man sich weiter dem Wert von [mm] \pi [/mm] , überschreitet ihn aber nie. Wenn man neben dem inneren Vieleck (Ecken auf dem Kreis) auch das äußere (Seitenmitten auf dem Kreis) betrachtet, kennt man das Intervall, in dem [mm] \pi [/mm] liegen muß, und damit die bereits erreichte Präzision. Wenn du pi auf 5 Nachkommastellen bestimmen sollst, weißt du also sofort, wann du das erreicht hast.
Aber: Das Verfahren ist iterativ, man benutzt in jedem Schritt das Ergebnis des vorherigen. Rechenungenauigkeiten werden von Iteration zu Iteration mitgeschleppt, und führen so am Ende zu größeren Abweichungen.
MC ist dagegen ein statistischer Prozess. Es pendelt sich mit zunehmender Menge an Zufallszahlen um [mm] \pi [/mm] herum ein, driftet mal wieder weg, nähert sich an, überschreitet [mm] \pi, [/mm] entfernt sich wieder, und so weiter. Mit der Anzahl werden diese Schwankungen zwar immer geringer, aber du weißt nie genau, wie nah du denn bereits an [mm] \pi [/mm] bist. Vor allem: Jedes mal, wenn du die Berechnung wiederholst, sieht der "Tanz" um den wahren Wert anders aus.
(Mir kommt da grade die Idee, statt zufälliger Koordinaten ein Raster zu benutzen, das immer feiner wird.)
Die Rechengenauigkeit ist recht gut. Du berechnest für jedes Koordinatenpaar den Abstand zum Ursprung, und zählst dann, wie viele Punkte im Kreis liegen. Das Zählen ist fehlerfrei, und die geringen Fehler bei der Abstandsberechnung heben sich vermutlich auch noch ganz gut auf. Am Ende mußt du noch eine Division durchführen, das bringt nicht viel Ungenauigkeit.
Allerdings sind gute Zufallszahlen nicht so einfach zu erzeugen, ein Computer kann das gar nicht. Er kann nur Zahlenfolgen erzeugen, die möglichst zufällig aussehen. Wenn deine Zufallszahlen die Tendenz haben, näher bei 0 zu liegen, bekommst du zu viele Punkte im Kreis, und [mm] \pi [/mm] wird zu groß.
|
|
|
|
