20marzo2014 Candidata:ClaudiaBittanteRelatore:prof.DeMarchiStefanoCorrelatore:prof.AlviseSommariva Unanuovatecnicadicubaturaquasi-MonteCarlosudomini2De3D

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 )D_N∗(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 V}T _{è 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 Ωηn_{la 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 = VT_w

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 kL2_{d λ}(Ω)ε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 −1₄((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, 30

Domini 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_{+ y}2_{+ z}2₎ f5(x , y , z) = p (x2_{+ y}2_{+ z}2₎3 Gradi: n = 5, 7, 9

Domini 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 n}3 _{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.