Una nuova tecnica di cubatura quasi-Monte Carlo
su domini 2D e 3D
Candidata: Claudia Bittante Relatore: prof. De Marchi Stefano Correlatore: prof. Alvise Sommariva
Università degli studi di Padova
Obiettivi
Cubatura su domini multivariati:
Per alcuni domini esistono formule di cubatura con grado algebrico esatto, legate alla particolare geometria. Ma talvolta usano un numero elevato di nodi e/o pesi non sempre positivi.
Per molti domini la cubatura viene fatta mediante tecniche di tipo (quasi-)Monte Carlo (QMC), che però necessita di molti punti (troppi!).
w
Vogliamo combinare il metodo QMC con l’estrazione di un numero ridotto di punti. Ovvero, preso un insieme di punti quasi-random iniziale, estraiamo un sottoinsieme di punti tramite i metodi di Matlab:
1. lsqnonneg;
2. approxfek (Sommariva-Vianello, 2010).
L’integrazione Monte Carlo
Data f : Ω → R, Ω ⊆ Rd, 0 < λ
d(Ω) < ∞, si vuole calcolare l’integrale
I (f ) := Z
Ω
f (x )dx.
Ponendo d µ = dx /λd(Ω), si interpreta l’integrale di f come valore
atteso di f con la misura del dominio: Z Ω f (x )dx = λd(Ω) Z Ω f (x )d µ(x) = λd(Ω)E (f )
Si usa laLegge Forte dei Grandi Numeriper approssimare il valor medio di f con la media campionaria:
L’integrazione Monte Carlo
Si ottiene così lastima di Monte Carloper l’integrale di f
I (f ) := Z Ω f (x )dx ≈ λd(Ω) N N X i =1 f (xi) =: IN(f )
Se f ∈ L2(µ), allora per l’errore d’integrazione
N := I (f ) − IN(f ) si hanno le stime (i) E (2 N) 1/2= λ d(Ω)σ(f )N−1/2, dove σ2(f ) è la varianza;
(ii) Teorema del Limite Centrale: se la 0 < σ2(f ) < ∞ allora esiste
ν ∈ N(0, 1) tale che
limN→∞N(f ) = λd(Ω)σ(f )N−1/2ν.
L’integrazione Monte Carlo
Vantaggi:
l’ordine di N non dipende dalla dimensione, mentre per le regole
classiche d’integrazione l’errore è O(N−2/d);
applicabile su qualunque dominio.
Limiti:
stime probabilistiche di N, anziché upper bounds;
la regolarità di f non incide su IN(f );
problema di come generare punti random al calcolatore.
Soluzioni:
tecniche di riduzione della varianza;
L’integrazione quasi-Monte Carlo
Idea: scegliere un insieme di punti {xi}1≤i ≤N deterministico,
uniformemente distribuito, con proprietà “speciali” che migliorino N.
Per misurare l’uniformità della distribuzione si usa ladiscrepanza.
DEFINIZIONE: Sia J =Qd
i =1[αi, βi) = {x ∈ R d : α
i ≤ xi < βi}. Sia
X = {x1, . . . , xN} ⊂ J una sequenza finita di punti di J. Si definisce
discrepanzadell’insieme di punti X la quantità
D(X ) = sup B⊆J #(B, X ) N − λd(B) ,
dove B ⊆ J sono sottointervalli d -dimensionali di J, e #(B, X ) =PN
L’integrazione quasi-Monte Carlo
DEFINIZIONE: Una sequenza X = {x1, . . . , xN} si dicequasi-randomo
a bassa discrepanzase
DN(X ) ≤ c(log N)kN−1,
dove c e k sono costanti indipendenti da N, che possono dipendere dalla dimensione d .
L’integrazione quasi-Monte Carlo
Teorema di Koksma-Hlawka: Sia f : [0, 1]d
→ R una funzione a variazione limitata nel senso di Hardy-Krause, e sia
X = {x1, . . . , xN} ⊂ [0, 1]d una sequenza qualsiasi. Allora
(f ) ≤ V (f )DN∗(X ) dove V (f ) è la variazione di f , e D∗ N(X ) è la discrepanza stellata di X . w w L’integrazione quasi-Monte Carlo ha errore
N≈ O((log N)kN−1)
lsqnonneg e problemi NNLS
La funzione Matlablsqnonnegrisolve problemiNNLS(Nonnegative Least Squares), ovveroproblemi ai minimi quadrati non negativi:
min w ∈Rn kAw − bk w ≥ 0. (NNLS) dove A ∈ Rm×n , b ∈ Rm.
lsqnonneg può essere usato per estrarre il minimo numero di nodi {xk}
con pesi solo positivi da un insieme di punti {yi} sufficientemente
grande, e fare su questi la cubatura a meno di un errore rispetto alla cubatura sull’intero insieme {yi}.
lsqnonneg e problemi NNLS
Scegliendo:
A = VT, dove VT è la trasposta della matrice di Vandermonde V
calcolata sui punti {yi}1≤i ≤n, nella base {pj}1≤j ≤m
b = m, dove m = (m1, . . . , mm)T è il vettore dei momenti
mj =RΩpj(x )d µ(x ), 1 ≤ j ≤ m, nella base {pj}1≤j ≤m si ottiene il problema NNLS min w ∈RnkV T w − mk wi≥ 0 i = 1, . . . , n.
La soluzione w ∈ Rn è il vettore dei pesi ≥ 0 associati ai nodi {y
i}1≤i ≤n.
I pesi strettamente positivi saranno in numero minore, ˆn ≤ n, e determinano altrettanti nodi {x1, . . . , xˆn} ⊆ {yi}.
Punti di Fekete
DEFINIZIONE: Sia Ω ⊂ Cd
compatto e Pd
n-determinante. I punti
del-l’insieme ξ = {ξ1, . . . , ξηn} ⊂ Ω, ηn = dim(Pdn) = n+d
d , si dicono
punti di Feketese sono unisolventi per l’interpolazione su Pd
n(Ω), ovvero
det(V (ξ, q)) 6= 0, e inoltre massimizzano in Ωηnla quantità | det(V (ξ, q))|.
Per costruzione sono buoni per l’interpolazione e per la quadratura in domini generici di Rd.
Sono noti analiticamente solo in pochi casi (intervallo, cerchio complesso, cubo con l’interpolazione prodotto tensoriale).
Sono costosi da calcolare: determinarli numericamente richiede di risolvere problemi di ottimizzazione multivariata non lineare.
w w
Punti approssimati di Fekete
Gli AFP sono punti estratti da una discretizzazione del dominio compatto.
Sono calcolati tramite la fattorizzazione QR con pivoting per colonne, implementata nella funzione Matlab approxfek
(Sommariva-Vianello, 2010).
Una nuova tecnica di cubatura
Procedimento:
1. Dato un dominio compatto Ω ⊂ R2
oppure Ω ⊂ R3, consideriamo il
rettangolo d -dimensionale ad esso circoscritto, con i lati paralleli agli assi coordinati.
2. Costruiamo una griglia di punti quasi-random (Halton o Sobol) sul rettangolo, da cui selezioniamo i punti contenuti in Ω.
Una nuova tecnica di cubatura
OSSERVAZIONE: Non sempre sono noti i momenti esatti di un
dominio. Quando possibile, li abbiamo ricavati da metodi di cubatura con grado algebrico esatto, altrimenti dal metodo QMC mediante il sistema
m = VTw
dove
V è la matrice di Vandermonde, tipicamente nella base di
Chebyshev, calcolata nei nodi prodotti dal metodo di cubatura con grado algebrico esatto, oppure dai punti quasi-random di QMC; w sono i pesi del metodo con grado algebrico esatto, oppure di QMC;
Errore di cubatura
TEOREMA (Sommariva-Vianello, 2014): Si considerino i metodi di cubatura S1(f ) = Z Ω f (P)d ν = N1 X i =1 wif (Pi), S2(f ) = N2 X k=1 ωkf (Qk)
e sia εmom= km − µk2 l’errore tra i rispettivi momenti.
Allora per ogni f ∈ C(Ω) vale la stima dell’errore di cubatura
Z Ω f (X )d ν − N2 X k=1 ωkf (ξk) ≤ ν(Ω) + N2 X k=1 |ωk| + p η(Ω)εmom ! En(f ; Ω) + kf kL2d λ(Ω)εmom
Domini 2D
Metodi di cubatura per i poligoni:
Polygauss* (Sommariva-Vianello, 2007); QMC;
lsqnonneg con momenti “esatti” e QMC; AFP con momenti “esatti” e QMC. Metodi di cubatura per la lente:
gqlenss* (Da Fies-Vianello, 2012); QMC;
lsqnonneg con momenti “esatti” e QMC; AFP con momenti “esatti” e QMC.
Metodi di cubatura per il dominio composito: QMC*;
Domini 2D
Funzioni test: f1(x , y ) = 3 4e −1 4((9x −2)2+(9y −2)2)+3 4e −1 49(9x +1)2−101(9y +1) +1 2e −14((9x −7)2+(9y −3)2)−1 5e −(9x−4)2−(9y −7)2 f2(x , y ) = p (x − 0.5)2+ (y − 0.5)2 f3(x , y ) = e−100((x−0.5) 2+(y −0.5)2) f4(x , y ) = cos(30(x + y )) Gradi: n = 10, 20, 30Domini 2D
#AFP sono in numero ≈ n3/6
#lsqnonneg, #AFP sono 1/15 dei nodi di Polygauss #lsqnonneg ≤ #AFP, #gqlens
lsqnonneg e AFP sono pressoché equivalenti
lsqnonneg e AFP con momenti “esatti” sono migliori di QMC lsqnonneg e AFP con momenti QMC sono equivalenti a QMC Errori arrivano fino all’ordine O(10−8)
Lo studio del rapporto dei pesi ρ =
P
i|wi|
|P
iwi| mostra che gli AFP
possono risentire di fenomeni di instabilità a causa dei pesi negativi (dominio composito, n = 30, momenti QMC).
Si ottengono risultati molto migliori per le funzioni con variazione piccola (cfr. Teorema di Koksma-Hlawka).
Domini 3D
Metodi di cubatura per il cubo:
Gauss-Chebyshev prodotto tensoriale*; QMC;
lsqnonneg con momenti “esatti” e QMC; AFP con momenti “esatti” e QMC.
Metodi di cubatura per il cono e la piramide: 3dWAM* (De Marchi-Vianello, 2013);
QMC;
lsqnonneg con momenti QMC; AFP con momenti QMC.
Metodi di cubatura per il dominio composito: QMC*;
Domini 3D
Funzioni test: f1(x , y , z) = 0.75e− 1 4((9x −2)2+(9y −2)2+(9z−2)2) + 0.75e−491(9x +1)2−101(9y +1)−101(9z+1) + 0.5e−14((9x −7)2+(9y −3)2+(9z−5)2) − 0.2e−(9x−4)2−(9y −7)2−(9z−5)2 f2(x , y , z) = p (x − 0.4)2+ (x − 0.4)2+ (x − 0.4)2 f3(x , y , z) = cos(4(x + y + z)) f4(x , y , z) = 1 1 + 16(x2+ y2+ z2) f5(x , y , z) = p (x2+ y2+ z2)3 Gradi: n = 5, 7, 9Domini 3D
Gradi bassi a causa della complessità numerica. Inoltre, tempi di esecuzione molto lunghi per approxfek. Enbrambe le questioni sono superabili con calcolatori più potenti (cluster).
#AFP sono in numero ≈ n3/6 , contro gli n3 nodi di
Gauss-Chebyshev prodotto tensoriale #lsqnonneg ≤ #AFP
lsqnonneg e AFP sono pressoché equivalenti
lsqnonneg e AFP non sempre sono migliori di QMC, a causa del grado basso
Errori arrivano fino all’ordine O(10−7) Lo studio del rapporto dei pesi ρ =
P
i|wi|
|P
iwi| mostra che gli AFP
possono risentire di fenomeni di instabilità a causa dei pesi negativi. I nodi di 3dWAM hanno valore ρ ancora peggiore.
Si ottengono risultati molto migliori per le funzioni con variazione piccola (cfr. Teorema di Koksma-Hlawka).
Conclusioni
La cubatura sui punti estratti da lsqnonneg e da approxfek da griglie quasi-random fornisce in generale risultati apprezzabili con un numero ridotto di nodi. Costituiscono, quindi, una valida alternativa a QMC e ai metodi di cubatura con grado algebrico esatto qui presentati.
L’utilizzo di momenti QMC è una buona soluzione per i casi in cui non sono noti i momenti esatti del dominio.
Nel caso trivariato, si rende necessario l’uso di cluster o calcolatori più potenti per estrarre i nodi tramite approxfek.