Gott würfelt nicht - KITtkuhr/HauptseminarWS0910/Kunz.pdf · Monte-Carlo-Methode mit Pseudo- und Quasizufallszahlen David Kunz Einführung Zufallszahlen verteilte Zufallszahlen Integration

Gott würfelt nicht

Monte-Carlo-Methodemit Pseudo- und Quasizufallszahlen

David KunzMonte-Carlo-Methode mit Pseudo- und Quasizufallszahlen Einführung Zufallszahlen verteilte Zufallszahlen Integration Simulation

Inhaltsverzeichnis

● Einführung● Pseudo- und Quasizufallszahlen● verteilte Zufallszahlen● Monte-Carlo-Integration● Monte-Carlo-Simulation


Einführung


Monte-Carlo-Methode● Bekannt nach Stadt Monte Carlo (wegen Casino) ● verwendet Prinzipien der Wahrscheinlichkeitsrechnung und Statistik● benutzt Zufallszahlen → „Methode der statistischen Versuche“● Fähigkeit, komplexe Probleme näherungsweise zu lösen● Schwierigkeitsgrad relativ gering

Fähigkeiten:● numerische Lösung von Problemen (Integrale, DGL, usw.) → deterministisch

● Simulation von Systemen mit Unsicherheiten → stochastisch

Einsatzgebiete:● Teilchenphysik● Astrophysik● Risikomanagement● ...


Zufallszahlen


Pseudozufallszahlen● Zufallszahlen ϵ [0,1] „zufällig“ durch Computer erzeugt ● linear kongruenter Generator:

I j=a⋅I j−1c mod m Bsp: 7 mod 2 = 1weil: 7/2=3 Rest 1

● Zufallszahl durch:● benötigt 3 ganzzahlige Konstanten:

z. B.

● und eine Saat:

a , c ,m ϵ ℤx j x j=I j /m

m=231−1, c=0, a=16807 (Park Miller Generator)

I 0


Pseudozufallszahlen




Quasizufallszahlen● gleichförmig verteilte zahlentheoretische Punktfolgen● nicht mehr unabhängig → systematisch konstruiert

● Richtmyer-Generator:

k-te Koordinate des i-ten Punkts:

mit : k-te Primzahl

● n Zufallsgeneratoren der n Dimensionen voneinander unabhängig

xik=ipk mod 1

pk


Quasizufallszahlen


Beispiel: Berechnung von Pi● erzeuge Punkte mittels zwei Pseudozufallszahlen und ϵ [0,1]

● Zähle Punkte innerhalb von Kreis (Radius 1)

● Pi erhält man dann aus:

N totx1 x2

N ac

x12x2

2≤1

pi=4N ac

N tot


pi=3,13vgl.

=3,14


Gitter, Pseudozufallszahlen oder Quasizufallszahlen?

Simulation● Pseudozufallszahlen

Integration● Entscheidung durch Fehlerabschätzung:

=∣QN f − If ∣≤V f D∗∞ PN

Koksma-Hlawka-Ungleichung für Integrationsfehler

Diskrepanz (Maß für Ungleichverteilung)



Diskrepanz∣n−N vol J ∣ klein für alle J



Integration● Für Dimensionen : Quasizufallszahlen bessere Diskrepanz als Pseudozufallszahlen

● Für Dimensionen : Kleinere Diskrepanz → kleinerer Fehler

→ Vorteil von Quasizufallszahlen mit größeren

● kleine N: Gitter so genau wie Quasizufallszahlen

● große N (ca. 2000): Gitter schlechtere Ergebnisse als Quasizufallszahlen

● Für : Gitter schlechter als Pseudozufallszahlen

● weiterer Nachteil von Gitter: Keine kontinuierliche Steigerung von N

s≤20

s≤10

s≥4

s


verteilte Zufallszahlen


verteilte Zufallszahlen● benötigt bei Integration und Simulation● gegeben: Homogen verteilte Zufallszahlen● gesucht: Zufallszahlen, die einer Wahrscheinlichkeitsdichte folgen


Wegwerfmethode (von Neumann's Acceptance-Rejection Method)

● Wahrscheinlichkeitsdichte f(x)● Eingrenzung (Box zwischen x1, x2 und fmax)● generiere Zufallszahl ϵ [x1,x2]● generiere zweite Zufallszahl u ϵ [0,fmax]● für u<f(x) wird x akzeptiert, ansonsten verworfen● wiederhole Vorgang

























Variablentransformation● gegeben: Wahrscheinlichkeitsdichte f(x) Zufallszahlen u ϵ [0,1] mit g(u)=const.

● Methode: Transformiere u→x:

∫−∞

ug u ' du '=∫−∞

x uf x ' dx '

u=F x u

F−1u= x u


VariablentransformationF−1u=x u


VariablentransformationBsp: F−1u=x u f x =e−x F x=∫0

xdx ' e−x '=−e−x1

F−1u=−ln 1−u=x u


Majorantenmethode(importance sampling)

● Kombination: Wegwerfmethode und Variablentransformation● wähle alle x

● generiere Zufallszahlen, die m(x) folgen (Variablentransformation)● generiere pro Zufallszahl x eine Zufallszahl u ϵ [0,m(x)]● verwerfe Zufallszahlen mit u>f(x)

m x f x



Bsp: Planck-Verteilung



Bsp: Planck-Verteilung


Monte-Carlo-Integration


Monte-Carlo-Integration

I=∫xa

xb y x ' dx ' mit y x ' 0

kann auf mehrere Dimensionen verallgemeinert werden


Primitive Wegwerfmethode● erzeuge 2D-Zufallszahlen in Kasten zwischen , und ● Anzahl Punkte unterhalb y(x): ● Anzahl aller Punkte: ● Fläche des Kastens:

xa xb ymaxN

N 0I 0

I≈ I 0NN 0


Primitive Wegwerfmethode● Unsicherheit durch Binomialverteilung:

P N =N 0

N N 1−N 0−N

Erfolgswahrscheinlichkeit ≈ NN 0

N=N 01−

II =N

N =1−N

II =1−

N

● Verbesserung durch Erhöhung von

● Verbesserung durch Erhöhung von NN 0

N


Majorantenmethode● finde Majorante m(x) zu y(x)● erzeuge Punkte x', die Wahrscheinlichkeitsdichte m(x') folgen● dann → Wegwerfmethode:● generiere zu jedem ein mit ● Anzahl der Punkte unterhalb : N

I≈ I 0NN 0

I 0=∫xa

xb mx ' dx '

x ' y ' 0≤ y '≤mx ' y x '


Wichtungsmethode

● mittle Funktionswerte mit Zufallszahlen zwischen und :

● entspricht herkömmlicher numerischer Integration● Unterschied: Stützstellen sind zufällig verteilt

I=∫xa

xb y x ' dx '

xa xb

y=1N ∑i=1

Ny xi

I≈xb− xa y

y 2≈ 1N N−1∑i

y xi−y ² II =y

y


Wichtungsmethode

y 2≈ 1N N−1∑i

y xi−y ²

● Verbesserung durch Reduzierung der Schwankungen


Vorteile der Monte-Carlo-Integration

● bessere Konvergenz für s-dimensionale Integrale mit als bei herkömmlicher numerischer Integration

● einfachere Behandlung der Integrationsgrenzen● Genauigkeit kann kontinuierlich gesteigert werden● Fehler leichter abschätzbar

s≥4


Monte-Carlo-Simulation


Photomultiplier

● herausgeschlagene Elektronen folgen Poisson-Verteilung


Photomultiplier


Photomultiplier


Fragen? Diskussion

Documents

Gott würfelt nicht - KITtkuhr/HauptseminarWS0910/Kunz.pdf · Monte-Carlo-Methode mit Pseudo- und Quasizufallszahlen David Kunz Einführung Zufallszahlen verteilte Zufallszahlen Integration