Analysenumérique: Intégrationnumérique...Formules de Newton-Cotes Newton-Cotes fermé Casn = 0,formuledesrectangles Leseulpointestsoita,soitb. Z b a f(x)dx ˇ(b a)f(a) Z b a f(x)dx

Analyse numérique :Intégration numérique

Pagora 1A

Chapitre 4

8 février – 11 mars 2013

Analyse numérique (Pagora 1A) Intégration numérique 8/02 - 11/03/2013 1 / 67

Plan

1 Introduction

2 Intégration par méthode de Monte-Carlo

3 Formules de Newton-CotesBasesNewton-Cotes ferméNewton-Cotes ouvert

4 Formules composites

5 Formules de GaussBasesUn exemple concretFormules de Gauss-Legendre


Introduction

Plan

1 Introduction






Introduction

Description du problème

On cherche à estimer la valeur numérique de

I =

∫ b

af (x) dx

avec :

a et b deux réels (a < b).

f fonction mal connue mais ne disposant pas de singularité sur [a, b].

exemple : f (x) = 1√x intégrable sur [0, 1] mais possède une sigularité en 0.


Introduction

Méthode classique : primitive

Lorsqu’on connait une primitive de f (noté ici F ) sur [a, b], on peutcalculer directement I .

I =

∫ b

af (x) dx = F (b)− F (a)

exemple : F (x) = 2√

x est une primitive de f (x) = 1√x sur [0, 1], on a donc

I =

∫ 1

0

1√x

dx = 2√1− 2

√0 = 2


Introduction

Problème

La plupart des fonctions f ne disposent pas d’expressions analytique pourleurs primitives même dans le cas de fonctions s’écrivant très simplement.

exemples : ∫ 1

0e−x2

dx∫ π/2

0

√1 + cos2 x dx∫ 1

0cos(x2) dx

Solution : utiliser des méthodes numériques.


Introduction

Exemple concret intégration numérique

Dans le cas du traitement du signal, on peut vouloir connaitre la valeurmoyenne f (t) d’un signal f sur [0, t].


Introduction

Exercice : valeur moyenne d’une fonction f

Soit f une fonction intégrable sur [a, b], quelle est sa valeur moyenne ?En déduire l’expression de f d’un signal f sur [0, t].


Introduction

Exercice (correction)

Soit f une fonction intégrable sur [a, b], quelle est sa valeur moyenne ?En déduire l’expression de f d’un signal f sur [0, t].

Notons fmoy la valeur moyenne de f sur [a, b]. fmoy doit vérifier l’égalité :∫ b

afmoy dx =

∫ b

af (x) dx

donc (b − a)fmoy =

∫ b

af (x) dx

et fmoy =1

b − a

∫ b

af (x) dx

d’où l’expression de f (t) =1t

∫ t

0f (x) dx avec t > 0


Intégration par méthode de Monte-Carlo

Plan

1 Introduction







Bases de la méthode de Monte-Carlo

Objectif : calculer

I =

∫Ω

f (x) dx

avec Ω ∈ Rn de volume V connu, c’est à dire on connait la valeur exacte de

V =

∫Ω

dx

Comment faire : on tire aléatoirement de manière uniforme des valeursxi ∈ Ω, i = 1, . . . ,N et on approche l’intégrale par

I ≈ QN =VN

N∑i=1

f (xi )



Exercice

Écrire un programme Scilab permettant d’estimer l’intégrale de 11+x2 sur

[0, 1] par la méthode de Monte-Carlo avec pour entrée N.

Pour rappel, la fonction rand(n,m) retourne une matrice de taille n ×mcontenant des nombres aléatoires de loi uniforme compris entre 0 et 1.




Voici un exemple de solution :

function QN = integraleMC(N)QN = 0 ;for k = 1:N

u = rand(1,1) ;QN = QN + (1./N).*(1./(1 + u.*u)) ;

endendfunction

On vient de donner un algorithme permettant de calculer∫ 1

0

11 + x2 dx = arctan(1)



Vitesse de convergence de la méthode

La méthode converge vers le bon résultat

limN−→∞

QN = I

Cependant sa vitesse de convergence est très lente (il faut que N soit trèsgrand pour avoir un résultat convenable). En effet, on note

fN =1N

N∑i=1

f (xi ) et limN−→∞

fN = fmoy valeur moyenne de f

σ2N =

1N − 1

N∑i=1

(f (xi )− fN)2 et limN−→∞

σ2N = σ2 ∈ R+

La variance de QN vaut

Var(QN) =V 2σ2

NN


Formules de Newton-Cotes

Plan

1 Introduction






Formules de Newton-Cotes Bases

Plan

1 Introduction







Interpolation et intégrale

On peut approcher une fonction quelconque f par un polynôme P . Commef (x) est proche de P(x), on a :

f (x) ≈ P(x) =⇒∫ b

af (x) dx ≈

∫ b

aP(x) dx

Avantages :

les polynômes sont faciles à intégrer.

cette méthode est utilisable même si on ne connait que des valeurs def puisqu’on peut alors construire le polynôme P d’interpolation de fsur ces valeurs.



Formules de quadrature de type interpolation

Soient (xi , yi = f (xi )), i = 0, . . . , n, n + 1 points d’interpolation tel quea ≤ x0 < x1 < . . . < xn ≤ b.

I =

∫ b

af (x) dx ≈

∫ b

aP(x) dx =

∫ b

a

n∑i=0

yiì (x) dx

Posons

In =

∫ b

a

n∑i=0

yiì (x) dx =n∑

i=0

∫ b

ayiì (x) dx =

n∑i=0

wi f (xi )

avec

wi =

∫ b

aì (x) dx



Définition : formule de quadrature

On approche l’intégrale par

I (f ) =

∫ b

af (x) dx ≈ In(f ) =

n∑i=0

wi f (xi )

avec :xi , i = 0, . . . , n, noeuds ou points d’intégration.

wi , i = 0, . . . , n, poids de la formule de quadrature.

On définit l’erreur comme étant

R(f ) = I (f )− In(f )



Définitions et théorème

Définition : Une formule de quadrature est dite exacte sur un ensemble Vsi pour tout f de V

R(f ) = 0

Définition : Une formule de quadrature est dite de degré de précision nsi elle est exacte pour xk , k = 0, . . . , n et non exacte pour xn+1.

Théorème : Une formule de quadrature à n+1 points est exacte surl’ensemble des polynômes de degré au plus n si, et seulement si, c’est uneformule de type interpolation à n+1 points.

Remarque : Une formule exacte sur l’ensemble des polynômes de degré auplus n est de degré de précision au moins n.



Exercice

Trouver A0 et A1 tels que :∫ 1

−1f (x) dx = A0f (−1) + A1f (1) + R(f )

et vérifier que cette formule de quadrature est de degré de précision 1.




C’est une formule de type interpolation à 2 points donc exacte surl’ensemble des polynômes de degré au plus 1. D’où :

f (x) = 1 , R(f ) = 0⇐⇒∫ 1

−11 dx = A0 + A1 = 2

f (x) = x , R(f ) = 0⇐⇒∫ 1

−1x dx = −A0 + A1 = 0

On obtient A0 = 1 et A1 = 1 donc∫ 1

−1f (x) dx = f (−1) + f (1) + R(f )

Cette méthode par construction est au moins de degré de précision 1.




Montrons que cette formule de quadrature est de degré de précision 1.

Pour

f (x) = x2∫ 1

−1f (x) dx =

236= A0f (−1) + A1f (1) = 2

donc R(f ) 6= 0 et la formule de quadrature est de degré de précision 1.


Formules de Newton-Cotes Newton-Cotes fermé

Plan

1 Introduction







Généralités

Pour obtenir les formules de Newton-Cotes fermé, on interpole f aux pointsuivants

xi = a + ih i = 0, . . . , n avec h =b − a

n

On a donc x0 = a et xn = b et on construit les formules de quadratures dela façon suivante : ∫ b

af (x) dx ≈ (b − a)

n∑i=0

w (n)i f (xi )

avec

w (n)i =

1b − a

∫ b

aì (x) dx



Cas n = 0, formule des rectanglesLe seul point est soit a, soit b.∫ b

af (x) dx ≈ (b − a)f (a)

∫ b

af (x) dx ≈ (b − a)f (b)

C’est la formule des rectangles qui estexacte uniquement pour les polynômes dedegré 0 (ie. les constantes).

Si f est C1 sur [a, b] alors il existe ξ ∈]a, b[tel que

R(f ) = ±(b − a)

2f ′(ξ)

+ si a, − si bAnalyse numérique (Pagora 1A) Intégration numérique 8/02 - 11/03/2013 26 / 67


Cas n = 1, formule des trapèzes

Les points d’interpolation sont x0 = a et x1 = b.

Exercice : Trouver la formule des trapèzes en calculant w (1)0 et w (1)

1 .




Correction :




Correction :

w (1)0 =

1b − a

∫ b

a`0(x) dx =

1b − a

∫ b

a

x − ba − b

dx =12

w (1)1 =

1b − a

∫ b

a`1(x) dx =

1b − a

∫ b

a

x − ab − a

dx =12

donc la formule des trapèzes est∫ b

af (x) dx ≈ 1

2(f (a) + f (b))




La formule des trapèzes est exacte pour les polynômes de degré au plus 1et est de degré de précision 1.

Si f est C2 sur [a, b] alors il existe ξ ∈]a, b[ tel que l’erreur R soit

R(f ) = −(b − a)3

12f ′′(ξ)



Cas n = 2, formule de Simpson

Les points d’interpolation sont x0 = a, x1 =a + b2

et x2 = b.

La formule de Simpson qui est exacte pour les polynômes de degré au plus2 vaut ∫ b

af (x) dx ≈ (b − a)

6

(f (a) + 4f

(a + b2

)+ f (b)

)


R(f ) = −(b − a)5

2880f (4)(ξ)

La formule de Simpson est de degré de précision 3.




Exercice : montrer que la formule de Simpson est de degré de précision 3.




Exercice : montrer que la formule de Simpson est de degré de précision 3.

La formule de Simpson est exacte pour les polynômes de degré au plus 2donc elle est de degré de précision au moins 2. D’autre part,∫ b

ax3 dx =

b4 − a4

4=

b − a4

(b3 + ab2 + a2b + a3)

b − a6

(a3 + 4

(a + b2

)3

+ b3

)=

b − a4

(b3 + ab2 + a2b + a3)

La formule de Simpson est de degré de précision au moins 3.




Pour x4, on obtient∫ b

ax4 dx =

b5 − a5

5=

b − a5

(b4 + ab3 + a2b2 + a3b + a4)

et

b − a6

(a4 + 4

(a + b2

)4

+ b4

)=

b − a24

(5b4 + 4ab3 + 6a2b2 + 4a3b + 5a4)

Les deux quantités ne sont pas égales donc la formule de Simpson est dedegré de précision 3.



Quelques formules de Newton-Cotes fermé

n nom w (n)0 w (n)

1 w (n)2 w (n)

3 w (n)4 w (n)

5 w (n)6

1 trapèzes 12

12

2 Simpson 16

46

16

3 Simpson 3/8 18

38

38

18

4 Boole 790

3290

1290

3290

790

5 - 19288

75288

50288

50288

75288

19288

6 Weddle 41840

216840

27840

272840

27840

216840

41840


Formules de Newton-Cotes Newton-Cotes ouvert

Plan

1 Introduction







Généralités

Pour obtenir les formules de Newton-Cotes ouvert, on interpole f aux pointsuivants

xi = a + (i + 1)h i = 0, . . . , n avec h =b − an + 2

et on construit les formules de quadratures de la façon suivante :∫ b

af (x) dx ≈ (b − a)

n∑i=0

w (n)i f (xi )

avec

w (n)i =

1b − a

∫ b

aì (x) dx

Contrairement aux formules de Newton-Cotes fermé, les pointsd’intégration ne sont jamais a et b.



Cas n = 0, formule des rectangles

Exercice : Trouver la formule des rectangles pour Newton-Cotes ouvert etmontrer qu’elle est de degré de précision 1.




Correction :

w (0)0 =

1b − a

∫ b

a`0(x) dx =

1b − a

∫ b

adx = 1

La formule des rectangles est donc :∫ b

af (x) dx ≈ (b − a)f

(a + b2

)Montrons que cette formule est de degré de précision 1.

I (1) =

∫ b

adx = (b − a) I0(1) = (b − a)f

(a + b2

)= (b − a)

La formule est donc de degré au moins 0 (car R(1) = I (1)− I0(1) = 0)




I (x) =

∫ b

ax dx =

b2 − a2

2I0(x) = (b − a)f

(a + b2

)= (b − a)

a + b2

La formule est donc de degré au moins 1 (car R(x) = I (x)− I0(x) = 0)

I (x2) =

∫ b

ax2 dx =

b3 − a3

3=

13

(b − a)(b2 + ab + a2)

I0(x2) = f(

a + b2

)= (b − a)

(a + b2

)2

=14

(b − a)(b2 + 2ab + a2)

R(x2) 6= 0, donc le degré de précision est bien 1.


R(f ) =(b − a)3

24f (2)(ξ)



Quelques formules de Newton-Cotes ouvert

n nom w (n)0 w (n)

1 w (n)2 w (n)

30 rectangles 11 trapèzes 1

212

2 Milne 23 -13

23

3 - 1124

124

124

1124



Quelques propriétés pour terminer

Pour une formule de Newton-Cotes associée à une valeur impaire de n.

Si f ∈ Cn+1([a, b]), alors il existe un réel Kn et ξ ∈]a, b[ tel que l’erreur Rcommise sur la valeur de l’intégrale soit

R(f ) =Kn

(n + 1)!(b − a)n+2 f (n+1)(ξ)

A noter que :Kn < 0 si Newton-Cotes fermé

Kn > 0 si Newton-Cotes ouvert



Quelques propriétés pour terminer

Pour une formule de Newton-Cotes associée à une valeur paire de n.

Si f ∈ Cn+2([a, b]), alors il existe un réel Mn et ξ ∈]a, b[ tel que l’erreur Rcommise sur la valeur de l’intégrale soit

R(f ) =Mn

(n + 2)!(b − a)n+3 f (n+2)(ξ)

A noter que :Mn < 0 si Newton-Cotes fermé

Mn > 0 si Newton-Cotes ouvert

Remarque : La propriété est valable pour toutes les formules deNewton-Cotes (fermé et ouvert) sauf Newton-Cotes fermé avec n = 0.



Degré de précision des formules de Newton-Cotes

Exercice : déduire des propriétés précédentes le degré de précision desformules de Newton-Cotes.



Degré de précision des formules de Newton-Cotes

Dans le cas n pair,

R(f ) =Mn

(n + 2)!(b − a)n+3 f (n+2)(ξ)

Donc pour tout k < n + 2, R(xk) = 0 et le degré de précision est au moinsn + 1. Maintenant,

R(xn+2) = Mn (b − a)n+3 6= 0

Le degré de précision des formules de Newton-Cotes avec n pair est n + 1.

Par un raisonnement analogue, on montre que le degré de précision desformules de Newton-Cotes avec n impair est n.


Formules composites

Plan

1 Introduction






Formules composites

Défauts des formules de Newton-Cotes

Pour rendre l’erreur plus petite qu’une quantité donnée, la seulepossibilité avec les formules de Newton-Cotes est d’augmenter lenombre de points d’intégration (donc le degré du polynômed’interpolation). Cela conduit parfois à l’apparition de comportementspeu appréciables (ex : phénomène de Runge).

A partir de n ≥ 9, les formules de Newton-Cotes deviennent instables(c’est à dire que les poids intervenant dans les formules peuvent êtrenégatifs).

=⇒ Idée : approcher f par des polynômes par morceaux pour le calcul del’intégrale (formule composite).


Formules composites

Bases

La méthode consiste à diviser l’intervalle [a, b] en r sous-intervalles delongueur

h =b − a

ret d’introduire les points de subdivision

ti = a + ih i = 0, . . . , r

On forme ∫ b

af (x) dx =

r−1∑i=0

∫ ti+1

tif (x) dx

et l’on applique sur chaque intervalle [ti , ti+1] une des formules deNewton-Cotes.


Formules composites

Exercice : formule composite des trapèzes (NC fermé)

Établir la formule composite des trapèzes. En combien de points est ilnécessaire d’évaluer f pour pouvoir utiliser cette formule ?


Formules composites


On applique sur chaque intervalle [ti , ti+1] la formule des trapèzes (NCfermé) ∫ ti+1

tif (x) dx ≈ h

2(f (ti ) + f (ti+1))

D’où ∫ b

af (x) dx =

r−1∑i=0

∫ ti+1

tif (x) dx ≈

r−1∑i=0

(f (ti ) + f (ti+1))

et la formule composite des trapèzes s’écrit∫ b

af (x) dx ≈ h

(12f (a) +

r−1∑i=1

f (ti ) +12f (b)

)

On doit évaluer r + 1 fois f pour pouvoir utiliser cette formule.


Formules composites

Erreur commise par la formule composite des trapèzes

On note R(f , [ti , ti+1]) l’erreur commise sur l’intgrale de f entre ti et ti+1.∫ ti+1

tif (x) dx =

h2

(f (ti ) + f (ti+1)) + R(f , [ti , ti+1])

Or on a vu précédement que si f ∈ C2([ti , ti+1]), il existe ξi ∈]ti , ti+1[ telquel

R(f , [ti , ti+1]) = − 112

h3f ′′(ξi )

Maintenant, supposons que f soit C2 sur [a, b] alors l’erreur R(f ) commisesur l’intégrale de f entre a et b vaut

R(f ) =r−1∑i=0

R(f , [ti , ti+1]) = −h3

12

r−1∑i=0

f ′′(ξi ) ξi ∈]ti , ti+1[


Formules composites

Erreur commise par la formule composite des trapèzes

Si f est C2 sur [a, b], alors f ′′ est continue sur [a, b] et il existe un réel c telquel

c = maxx∈[a,b]

|f ′′(x)|

On peut donc majorer |R(f )|, ainsi

|R(f )| ≤ h3

12

r−1∑i=0

|f ′′(xii )| ≤h3

12

r−1∑i=0

c = c h2 b − a12

et on alim

r−→∞|R(f )| = lim

h−→0|R(f )| = 0

On assure bien ici que l’erreur commise sur l’estimation de l’intégrale tendevers 0 en utilisant la formule composite des trapèzes (ceci reste vrai pourtout autre formule composite).


Formules de Gauss

Plan

1 Introduction






Formules de Gauss Bases

Plan

1 Introduction







Petit rappel

Soit une formule de quadrature

In(f ) =n∑

i=0

wi f (xi )

Les formules de Newton-Cotes fixent les nœuds xi et utilisent des poidsassurant un degré de précision n ou n + 1.

L’idée des formules de Gauss est de choisir les nœuds pour que le degréde précision de la formule soit le plus élevé possible.



Mise en forme du problème

Problème : Trouver les nœuds xi , i = 0 et les poids wi , . . . , n tel que∫ b

af (x) dx ≈

n∑i=0

wi f (xi )

On cherche donc 2n + 2 inconnues.

Idée : Chercher une formule exacte sur l’ensemble des polynômes de degréau plus 2n + 1, soit∫ b

axk dx =

n∑i=0

wixki k = 0, . . . , 2n + 1

On cherche 2n + 2 inconnues reliées entre elles par 2n + 2 équations.

Remarque : La formule obtenue est de degré de précision 2n + 1.


Formules de Gauss Un exemple concret

Plan

1 Introduction







Exercice

Soit la formule de quadrature de Gauss

I (f ) =

∫ 1

−1f (x) dx ≈ In(f ) = w0f (x0) + w1f (x1)

Établir le système d’équations reliant les poids et les nœuds. Vérifier que

w0 = w1 = 1 x0 = −√33

x1 =

√33

est solution du système établi et vérifier que la formule

∫ 1

−1f (x) dx ≈ f

(−√33

)+ f

(√33

)

est de degré de précision 3.










On cherche une formule exacte sur l’ensemble des polynômes de degré auplus 2n + 1, soit∫ b

axk dx =

n∑i=0

wixki k = 0, . . . , 2n + 1

Ici a = −1, b = 1, n = 1. On établit le système suivant

∫ 1

−11 dx = 2 = w0 + w1∫ 1

−1x dx = 0 = w0x0 + w1x1∫ 1

−1x2 dx =

23

= w0x20 + w1x2

1∫ 1

−1x3 dx = 0 = w0x3

0 + w1x31




w0 = w1 = 1 x0 = −√33

x1 =

√33

est solution du système établi précédemment.

Montrons enfin que la formule est de degré de précision 3. Par définition,elle est de degré de précision au moins 3. D’autre part, on a∫ 1

−1x4 dx =

256= w0x4

0 + w1x41 =

29

La formule est bien de degré de précision 3.


Formules de Gauss Formules de Gauss-Legendre

Plan

1 Introduction







Polynômes de Legendre

Les polynômes de Legendre notés Pm (m entier positif) peuvent se définirde différentes manières :

Pm(x) =1

2m m!

dm

dxm [(x2 − 1)m]

Pm(x) =12m

m∑k=0

(m!

k!(m − k)!

)2

(x − 1)k(x + 1)m−k



Polynômes de Legendre



Formule de Gauss-Legendre

On veut approcher

I (f ) =

∫ 1

−1f (x) dx

Par la formule de quadrature suivante

In(f ) =n∑

i=0

wi f (xi )

La formule de Gauss-Legendre indique de prendre pour xi la ième racine(classée dans l’ordre croissant) du polynôme de Legendre Pn+1(Pn+1(xi ) = 0) et pour wi

wi =2

(1− x2i )(P ′n+1(xi ))2

Cette formule est de degré de précision 2n + 1.Analyse numérique (Pagora 1A) Intégration numérique 8/02 - 11/03/2013 66 / 67


Formule de Gauss-Legendre dans le cas général

On veut maintenant approcher

I (f ) =

∫ b

af (t) dt

Pour pouvoir utiliser les formules précédentes, il faut tout d’abord effectuerle changement de variable suivant

I (f ) =

∫ b

af (t) dt =

b − a2

∫ 1

−1f(

b − a2

x +a + b2

)dx

et on peut utiliser la formule de Gauss-Legendre, on a∫ b

af (t) dt ≈ b − a

2

n∑i=0

wi f(

b − a2

xi +a + b2

)avec les xi et wi établis précédemment.Analyse numérique (Pagora 1A) Intégration numérique 8/02 - 11/03/2013 67 / 67

Documents

Analysenumérique: Intégrationnumérique...Formules de Newton-Cotes Newton-Cotes fermé Casn = 0,formuledesrectangles Leseulpointestsoita,soitb. Z b a f(x)dx ˇ(b a)f(a) Z b a f(x)dx