14
Integrazione con metodo Monte Carlo Integrazione con metodo Monte Carlo Michele Antonelli 28 Ottobre 2010 Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Michele Antonelli
28 Ottobre 2010
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Outline
1 Integrazione con metodo Monte CarloMetodo Monte CarloStima dell’erroreImplementazione in REsempi
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Integrazione numerica
I metodi deterministici di integrazione numerica (come Simpson,trapezi, e in generale Newton-Cotes) lavorano tipicamente concampionature uniformi del dominio.
Tali formule di quadratura funzionano molto bene per funzioniunivariate, ma all’aumentare della dimensione/gradi di liberta delproblema soffrono di una perdita di efficienza dovuta alla crescitaesponenziale del numero di punti in cui si valuta la funzioneintegranda.
Per ovviare a cio, se la funzione da integrare ha un buoncomportamento, e possibile utilizzare metodi statistici, chegenerano casualmente un numero prefissato di punti di valutazioneall’interno del dominio (di qualsiasi dimensione esso sia).
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Integrazione con metodo Monte Carlo
Le realizzazioni dalle varie leggi distributive possono essereutilizzate per approssimare numericamente gli integrali del tipo
∫b
a
g(u)du
o, in piu dimensioni, ∫
V
g(u)du
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Valore atteso
Definizione
Data una variabile aleatoria X definita su uno spazio di probabilita(Ω,F ,P), si definisce valore atteso di X la quantita
E [X ] =
∫
Ω
X dP
Se la distribuzione di probabilita di X ammette una densita diprobabilita p(x), allora il valore atteso diventa
E [X ] =
∫
R
xp(x) dx
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Integrazione con metodo Monte Carlo
Siano u1, . . . , un n realizzazioni indipendenti da variabili aleatorieuniformi nell’intervallo [a, b], ovvero con densita di probabilita paria p(u) = 1
b−a.
Applicando la definizione di valore atteso nel nostro caso, si ha
E [g(u)] =
∫b
a
g(u)1
b − adu
Per la legge debole dei grandi numeri, c’e convergenza della mediacampionaria della funzione integranda al valore atteso:
1
n
n∑
i=1
g(ui ) −−−→n→∞
E [g(u)]
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Integrazione con metodo Monte Carlo
Pertanto vale
∫b
a
g(u) du = (b − a)E [g(u)] ≈ (b − a)1
n
n∑
i=1
g(ui )
Quindi si ottiene un valore approssimato dell’integralemoltiplicando la stima del valore atteso (data dalla media) perl’ampiezza dell’intervallo.
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Stima dell’errore
Il teorema del limite centrale assicura
1
n
n∑
i=1
g(ui ) ∼ N
(E [g(u)],
1
nvar[g(u)]
)
L’errore puo quindi scriversi come deviazione standard
σn = (b − a)
√g2 − (g)2
n
dove
g =1
n
n∑
i=1
g(ui ) e g2 =1
n
n∑
i=1
g2(ui )
e il valore dell’integrale si puo esprimere piu correttamente come∫
b
a
g(u)du ≈ (b − a)1
n
n∑
i=1
g(ui ) ± σn
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Osservazione
La stima del valore dell’integrale si discosta da E [g(u)] dell’ordinedi σn ∝ 1√
n, ovvero
P (E [g(u)](b − a) − σn < valore stimato < E [g(u)](b − a) + σn) ≈ 0.68
Questo significa che il metodo converge lentamente O(n−12 ),
ovvero per migliorare di una cifra significativa il risultato enecessario utilizzare un numero di punti (cioe di numeri generaticasualmente) 100 volte piu grande.
Esempi di metodi piu efficienti:
trapezi O(n−2)
Simpson/Gauss O(n−4)
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Osservazione
Tuttavia, il metodo di Monte Carlo (che mantiene la stessa formaper integrali multi-dimensionali) si dimostra piu conveniente apartire dalla dimensione 6 o 7, in confronto ad altri metodideterministici di integrazione.
Ad esempio, rispetto al metodo midpoint (che prevede unasuddivisione equispaziata del dominio), Monte Carlo e piu efficientegia per dimensione 3.
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Implementazione in R
montecarlo.R contiene:
function montecarlo 1d per Monte Carlo 1-dimensionalefunction montecarlo 2d per Monte Carlo 2-dimensionalefunction montecarlo per Monte Carlo a dimensione qualunque
valutazione delle funzioni integrande
main per testare gli esempi
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Esempi
Esempio 1
Approssimare l’integrale∫ 5
2sin x dx .
Vero valore: cos(2) − cos(5) ≈ −0.699809
2.5 3.0 3.5 4.0 4.5 5.0
-1.0
-0.5
0.5
Figure: f (x) = sin x , x ∈ [2, 5]
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Esempi
Esempio 2
Approssimare l’integrale doppio∫ 10
3
∫ 7
1sin(x − y) dx dy .
Vero valore: 2 sin(3)(cos(6) − cos(1)) ≈ 0.118504
2
4
6
4
6
8
10-1.0
-0.5
0.0
0.5
1.0
Figure: f (x , y) = sin(x − y), (x , y) ∈ [1, 7]× [3, 10]
Michele Antonelli Integrazione con metodo Monte Carlo
Integrazione con metodo Monte Carlo
Metodo Monte CarloStima dell’erroreImplementazione in REsempi
Esempi
Esempio 3
Approssimare l’integrale doppio∫ 1
0
∫π
−πy cos(xy) dx dy .
Vero valore: 4π≈ 1.27324
-2
0
2
0.0
0.5
1.0-1.0
-0.5
0.0
0.5
1.0
Figure: f (x , y) = y cos(xy), (x , y) ∈ [−π, π] × [0, 1]
Michele Antonelli Integrazione con metodo Monte Carlo
