Upload
enatt2012
View
18
Download
0
Embed Size (px)
DESCRIPTION
Integration Numérique
Citation preview
Méthodes d'intégrationsApproches déterministes
Quadratures
Approches déterministesQuadratures
http://numericalmethods.eng.usf.edu
3
Qu'est ce qu'intégrer
Intégration
I=∫a
b
f ( x )d x
Mesurer l'aire sous une courbe.
Définitions :
f(x) est l'intégrande
a = borne inférieure
b = borne supérieure
f(x)
a b
y
x
∫a
b
f ( x )d x
Intégrale au sens de Riemann
I n=∑k=1
n
f ( x k ) (x k−x k−1)
flimn→∞
I n=∫x0
xn
f ( x )= I
Intégration numérique 1D - Rectangles● Méthode des rectangles
– A droite
– A gauche
● Convergence
– Si f est C0 : O (n-1)
I n=b−an∑k=1
n
f (x k )
I n=b−an∑k=1
n
f (x k−1 )
Intégration numérique 1D – Points du milieu● Méthode des points du milieu
● Convergence
– Si f est C0 : O (n-1)
– Si f est au moins C2 : O (n-2)
I n=b−an∑k=1
n
f ( x k +1− xk2 )
Intégration numérique 1D● Intervalles uniformes
● Méthode des rectangles
● Méthode des trapèzes
● Formule de Simpson
I n=b−an ∑k=1
n
f (x k )
Convergence
O(n-1)
f
I n=b−a2n ∑k=1
n
(f ( x k−1 )+f (x k ))O(n-2)
I n=b−a6n ∑k=1
n
(f ( x k−1 )+4f (x k−1/2)+f ( xk ))f
O(n-4)
I=∫−1
1f ( x ) d x≃∑
m=1
M
W m f (εm )
Poids Positions d'intégration
● Les poids et les positions maximisent la précision● M positions pour l'espace des polynômes de degré 2M-1● Le calcul des intégrales est exact sur cet espace
● Les positions sont les racines du polynôme de Legendre● Base de polynômes orthogonale sur [-1,1]
Quadrature de Gauss en 1D
∀ p∈P2M−1 ,∫−1
1p (x )d x=∑
m=1
M
W mp(εm)
PM ( x)=1
2M M !dM
d xM(( x2−1 )
M )
1D - M = 1
I=∫−1
1f ( x )d x=w1 f ( x1)
Pour les polynômes de degré au plus 1
⇒ w1=2Pour f(x) = 1
⇒ x1=0Pour f(x) = x
1D - M = 2
121 ww
ε1=−√33, ε2=
√33
I=∫−1
1f ( x )d x=w1 f ( x1)+w2f ( x2)
Pour les polynômes de degré au plus 3
Calcul des positions, racine de
d2
dε2 ( (ε2−1 )
2)=0=4(3ε2−1)
⇒ w1+w2=2Pour f(x) = 1
⇒−w1+w2=0Pour f(x) = x
Calcul des poids
I=∫−1
1
∫−1
1f ( s , t ) d s d t
s
t
1
1
1 1
3
1,
3
1
3
1,
3
1
3
1,
3
1
3
1,
3
1
I≈∫−1
1 (∑j=1
M
W j f (s , t j )) ds≈∑i=1
M
∑j=1
M
W iW j f ( si ,t j )
En utilisant la forme 1D pour t
En utilisant la forme 1D pour s
2D – M = 2
Quadrature de Gauss 2D : domaine triangulaire
s
t
1
1
s=1-tt
t
Intégrale sur le domaine de référence
I=∫t=0
1
∫s=0
1−tf (s , t )d s d t
≈∑n=1
N
W n f ( sn , t n)
Contraintes sur les poids – fonction constante
Si f(s,t)=1
I=∫t=0
1
∫s=0
1−tf (s , t )d s d t=
12
=∑nW n
∴∑nW n=
12
Quadrature de Gauss sur un triangle : M = 1
f ( s , t )~ 1s t
3
1,
3
1
2
1fI
s
t
1
11/3
1/3
Démonstration
f ( s , t )=α s+βtLes polynômes de degré 1 s'écrivent
321
1
0
1
0 !3
1
!3
1
2
1dsdt),(f
t
t
sts
En intégrant, on obtient
D'où la contrainte
∫t=0
1
∫s=0
1−tf (s ,t ) d sd t=W 1 f (s1 , t 1)
∴13 !
α+13 !β=W 1 (α s1+βt 1 )
Ainsi
!3
1;
!3
1;
2
111111 tWsWW
Solution exacte pour tous les polynômes de degré au plus 2
f ( s , t )= 1s t
s2 st t 2
I≈16
f ( 12 ,12 )+
16
f ( 12 ,0)+ 16
f (0, 12 )s
t
1
1
1/2
1/22
1
3
Quadrature de Gauss sur un triangle : M = 3
I ≈−2796
f ( 13 ,13 )+
2596
f (0 .2,0 . 6 )+2596
f (0 .2,0 .2 )+2596
f (0 .6,0 . 2 )
s
t
1
1 2
13 4
(1/3,1/3)
(0.2,0.2)
(0.2,0.6)
(0.6,0.2)
Quadrature de Gauss sur un triangle : M = 4
Solution exacte pour tous les polynômes de degré au plus 3
f ( s , t )= 1s t
s2 st t 2
s3 s2 t st 2 t3
Recommended order of integration“Finite Element Procedures” by K. –J. Bathe
Convergence et dimension
● En 1D
– Convergence en O(n-(c+1))
– c = continuité de la fonction
● En dimension plus élevée d
– Pour n valeurs / mailles
– Taille intervalle 1D n1/d
– Convergence en O(n-(c+1)/d)
Méthodes d'intégrationsApproches stochastiques
Méthode / algorithme probabiliste● Principe : introduire de l'aléatoire
– Choix de solutions aléatoires, et garder la meilleure
– Mélanger les données
– Choisir des valeurs aléatoires
● Pour l'intégration : intégration de Monte Carlo
Probabilité en espace continue : 1D● Échantillons aléatoires {Xi}
● Densité de probabilité (PDF)
– Probabilité associée
– Probabilité totale
pdf ( x )≥0
P [ X i∈[ x , x+dx ] ]=pdf (x )d x
∫−∞
∞
pdf ( x )d x=1
Probabilité en espace continue : 1D● Fonction cumulative (CDF)
P [Xi∈[a , b ] ]=cdf (b)−cdf (a )
cdf (a)=P (X ∈[−∞ ,a ] )=∫−∞
apdf ( x )d x
CDF vs PDF
0
0.5
1
1.5
2
0 0.2 0.4 0.6 0.8 1
pdf (x)=π2
sin (π x )
cdf (x )=(1−cos (π x ) )
2
Intégrale de Lebesgue● Plus générique que Riemann
– Notion de mesure de l'espace () 0
I=∫ f (x)μ (d x )
Espérance – Variance – Écart-type● Espérance : valeur moyenne
● Variance : distance au carré à la moyenne
● Écart-type : distance à la moyenne
E [g(X )]=∫g (x )pdf ( x )d x
V [g (X )]=∫ (g(x)−E [g(X )] )2pdf ( x )d x
V [g (X )]=E [g2(X ) ]−E2 [g(X )]
σ [g(X ) ]=√V [g(X )]
● Estimateur
● Biais
– Différence valeur attendue vs cherchée
– Estimateur sans biais
I n=∑i=1
n
αi f (x i )I n=∑
i=1
n 1n
1pdf (X i )
f (X i )
biais=E [ I n ]− I
Méthode de Monte Carlo
biais=0
Convergence● Variance
● Convergence
● Meilleur choix de la PDF
V [ I n ]=E [ I n2]−E [ I n ]
2=
1n
V [ I 1 ]
σ [ I n ]=1
√nσ [ I 1 ]
pdf (x )=1I
f (x )⇒V [In ]=0
Choix de la PDF / Importance Sampling● Algorithme d'échantillonnage
– En fonction d'une PDF
● i = nombre aléatoire uniforme (drand48(), …)
● xi ← cdf-1(i)
● Choix de la PDF
– Rappel, l'idéal
– Approximation par une fonction proche
● Doit être intégrable● L'intégrale doit être inversible
pdf (x )= 1
∫ f (x)d xf (x )
Importance Sampling
0
0.5
1
1.5
2
0 0.2 0.4 0.6 0.8 1
pdf (x)=π2
sin (π x )
cdf (x)=(1−cos (π x ))
2
x
Choix de la PDF / Importance Sampling● Algorithme d'échantillonnage
● Choix de la PDF
– Version tabulée
● Échantillonnage de la fonction à intégrer● PDF constante par morceau● CDF linéaire par morceau● Calcul de l’échantillon en O( ln (k) )
Définitions xD● Xi = (X1,i, ...... , Xn,i)
● Probabilité conditionnelle
– Probabilité de Xj,i sachant que l'on connaît les autres
– Propriétés (Bayes)pdf ( x j∣{xk ,k≠ j })≥0
pdf ( x1, .. , xn)=pdf (x j∣{xk , k≠ j })pdf (x1 , ... , x j−1 , x j+1 , ... , xn )
pdf ( x1 , ... , x j−1 , x j+1 , ... xn)=∫ pdf ( x1 , .. , xn)d x j
Définitions xD
● Xi = (X1,i, ...... , Xn,i)
● Variables indépendantes
pdf ( x j∣{xk ,k≠ j })=pdf ( x j )
pdf ( x1, .. , xn)=∏ jpdf (x j )
Définitions xD
● Xi = (X1,i, ...... , Xn,i)
● CDF conditionnelle
cdf (a j∣{ak , k≠ j })=∫−∞a j
pdf (x j∣{xk=ak , k≠ j })dx j
cdf (a j∣{ak , k≠ j })=∫−∞
a jpdf ( x1 , ... , xn )dx j
pdf ( x1 , ... , x j−1 , x j+1 , ... , xn)
cdf (a j∣{ak , k≠ j })=∫−∞
a jpdf (x1 , ... , xn )dx j
∫−∞+∞
pdf (x1 , ... , xn )dx j
Importance Sampling xD● Exemple en 2D: (X,Y)
● Données
– CDF(X)
– CDF(Y|X)
● Algorithme
– e1 et e2 : valeurs aléatoires
– X tel que e1 = CDF(X)
– Y tel que e2 = CDF(Y|X)
Convergence et dimension● En 1D
– Convergence en O(n-(c+1))
– c = continuité de la fonction
● En dimension plus élevée d
– Pour n valeurs / mailles
– Taille intervalle 1D n1/d
– Convergence en O(n-c/d)
– Monte Carlo en O(n-1/2)