• Non ci sono risultati.

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

N/A
N/A
Protected

Academic year: 2021

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

Copied!
31
0
0

Testo completo

(1)

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

(2)

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).

(3)
(4)

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:

(5)

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ν.

(6)

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;

(7)

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

(8)

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 .

(9)

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)

(10)
(11)

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}.

(12)

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 =Rpj(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}.

(13)
(14)

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 

(15)

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).

(16)
(17)

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 Ω.

(18)

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;

(19)

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

(20)
(21)
(22)

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*;

(23)

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, 30

(24)

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).

(25)
(26)

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*;

(27)

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, 9

(28)

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 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).

(29)
(30)

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.

(31)

Riferimenti

Documenti correlati

Coniche: curve che si possono ottenere come intersezione di un cono con un piano; al variare dell’inclinazione del piano rispetto al cono si possono ottenere

Quanti numeri interi possiedono

la promessa di assunzione di tutti i precari nelle graduatorie ad esaurimento non è stata preceduta da « un' analisi dei profili professionali necessari alla

LA SIGNORA DESIDERIA, MOGLIE DELL’ELFO BENIAMINO, STA CONFEZIONANDO NASTRI COLORATI E STELLE DI CARTA PER ADORNARE I PACCHETTI DEI REGALI.. OSSERVA BENE IL DISEGNO

Un sistema costituito da due equazioni di secondo grado in due incognite si dice omogeneo se nelle sue equazioni mancano i termini di primo

Copyright © 2011 Zanichelli Editore SpA, Bologna [6435] Questo file è una estensione online del corso di A.M... Copyright © 2011 Zanichelli Editore SpA, Bologna [6435] Questo file

Per il primo campione di 123 bambini, che indossavano la cintura di sicurezza, il numero di giorni passati in terapia intensiva ha una media campionaria pari a 0.83 e una

[r]