(Éléments de correction : programmes et mathématiques)
Théorie Les méthodes usuelles d'intégration numérique sont constituées par l'utilisation d'une formule de quadrature élémentaire, reproduite sur des sous-intervalles subdivisant le domaine d'intégration.
Les méthodes d'intégration numérique de Gauss permettent d'approcher la valeur d'une intégrale en utilisant un nombre minimal d'évaluations de la fonction pour un ordre de convergence maximal. Les méthodes obtenues sont alors comparativement plus précises pour un même nombre de points de quadrature. Le prix à payer est le calcul (a priori) de ces points de quadrature, qui se trouvent être les racines de polynômes orthogonaux. Les poids de la quadrature peuvent quant à eux être calculés par des formules faisant intervenir les dérivées de ces polynômes.
But du TP. Il s'agit de mettre en œuvre une première méthode de quadrature simple, puis certaines méthodes d'intégration numérique gaussiennes et d'en comparer la performance avec les méthodes de Newton-Cotes les plus classiques.
$\square$ Programmer la méthode des rectangles à gauche pour approcher l'intégrale suivante à l'aide d'une subdivision régulière de l'intervalle considéré avec $N=100$ sous-intervalles: $I = \int_0^1 e^{\sin x}\mathrm{d}x.$
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams["figure.figsize"] = (12,10)
N = 100
h = 1/100
I = 0
for i in range(100):
I = I + h*np.exp(np.sin(i*h))
print(I)
1.62527283585714
Il peut s'avérer compliqué de construire les polynômes orthogonaux à tout ordre, d'en calculer les racines et les poids d'intégration. On se contentera pour commencer d'une méthode particulière : la méthode de Gauss-Legendre à trois points. La méthode élémentaire correspondante est associée au poids uniforme $w(x)=1$ sur $[0,1]$ et correspond à l'approximation suivante:
\begin{equation*}
\int_0^1 \varphi(x)w(x)\mathrm{d} x\simeq
\frac1{18}\left[5\,\varphi\left(\frac12-\frac{\sqrt{15}}{10}\right)
+8\,\varphi\left(\frac12\right)+5\,\varphi\left(\frac12+\frac{\sqrt{15}}{10}\right)\right].
\end{equation*}
$\square$ Programmer la méthode composée correspondante pour approcher une intégrale de la forme $\int_a^b f(x)\mathrm{d} x$, utilisant une subdivision régulière de l'intervalle $[a,b]$.
def GaussLegendre(f,a,b,N):
h = (b-a)/N
x = np.arange(a,b,h)
X1 = x + (1/2-np.sqrt(15)/10)*h
X2 = x + h/2
X3 = x + (1/2+np.sqrt(15)/10)*h
F = 1/18*(5*f(X1)+8*f(X2)+5*f(X3))
I = h*np.sum(F)
return I
# Test de la fonction précédente sur l'intégrale I
def f(x):
return np.exp(np.sin(x))
GaussLegendre(f,0,1,400)
1.631869608418051
Il est ici essentiel de bien manipuler les vecteurs incrémentaux obtenus par exemple avec np.arange
et de prendre en compte en conséquence les bons points d'intégration.
np.linspace(a,b,N)
créé un array
comprenant N
valeurs équidistantes entre a
et b
. Ces deux valeurs sont incluses et le pas entre deux valeurs consécutives est $(b-a)/(N-1)$.
np.arange(a,b,h)
créé un array
comprenant les valeurs entre a
inclus et b
exclu, distantes d'un pas h
.
$\square$ Programmer de même la méthode de Simpson.
def Simpson(f,a,b,N):
h = (b-a)/N
x = np.arange(a,b,h)
X1 = x
X2 = x + h/2
X3 = x + h
F = 1/6*(f(X1)+4*f(X2)+f(X3))
I = h*np.sum(F)
return I
# Test de la fonction précédente sur l'intégrale I
def f(x):
return np.exp(np.sin(x))
Simpson(f,0,1,400)
1.6318696084179964
1. Comparer les deux méthodes précédentes en termes de performance (ordre de convergence) et de coût de calcul (nombre d'évaluations de la fonction). On considérera une fonction $f\in\mathcal{C}^4([0,1])$.
def f(x):
return np.exp(x)
a = 0
b = 1
ListeN = np.arange(10,400,20)
I_GaussLeg = []
I_Simpson = []
for N in ListeN:
I_GaussLeg.append(GaussLegendre(f,a,b,N))
I_Simpson.append(Simpson(f,a,b,N))
Iex = np.exp(1)-np.exp(0)
Err_GaussLeg = np.abs(I_GaussLeg-Iex)
Err_Simpson = np.abs(I_Simpson-Iex)
plt.plot(np.log(ListeN),np.log(Err_GaussLeg),'-x',label="Gauss-Legendre")
plt.plot(np.log(ListeN),np.log(Err_Simpson) ,'-x',label="Simpson")
plt.legend()
plt.title("Courbes de convergence")
plt.xlabel("log N")
plt.ylabel("log erreur")
plt.show()
/Users/boutin/Library/Python/3.6/lib/python/site-packages/ipykernel_launcher.py:18: RuntimeWarning: divide by zero encountered in log
On teste les deux méthodes pour approcher $\int_0^1 e^x dx$. La figure représente le logarithme de l'erreur en fonction du logarithme du nombre de sous-intervalles de $[0,1]$. Les courbes de convergence saturent à l'ordonnée de l'ordre du logarithme de l'erreur machine : -36.
On peut retarder l'influence de l'erreur machine en relevant les courbes de convergence. Il suffit pour cela de considérer une fonction plus difficile à intégrer, par exemple une fonction assez oscillante : $\int_0^1 \cos(20x)dx$.
def g(x):
return np.cos(20*x)
a = 0
b = 1
ListeN = np.arange(10,400,20)
I_GaussLeg = []
I_Simpson = []
for N in ListeN:
I_GaussLeg.append(GaussLegendre(g,a,b,N))
I_Simpson.append(Simpson(g,a,b,N))
Iex = 1/20*(np.sin(20*b)-np.sin(20*a))
Err_GaussLeg = np.abs(I_GaussLeg-Iex)
Err_Simpson = np.abs(I_Simpson-Iex)
plt.plot(np.log(ListeN),np.log(Err_GaussLeg),'-x',label="Gauss-Legendre")
plt.plot(np.log(ListeN),np.log(Err_Simpson) ,'-x',label="Simpson")
plt.legend()
plt.title("Courbes de convergence")
plt.xlabel("log N")
plt.ylabel("log erreur")
plt.show()
## Regression linéaire pour le calcul de l'ordre
# Voir la documentation de polyfit(x,y,degree)
aGL = np.polyfit(np.log(ListeN),np.log(Err_GaussLeg),1)[0]
aSi = np.polyfit(np.log(ListeN),np.log(Err_Simpson),1)[0]
print("Ordre de Gauss-Legendre : "+str(-aGL))
print("Ordre de Simpson : "+str(-aSi))
Ordre de Gauss-Legendre : 6.030425387377482 Ordre de Simpson : 4.021437537705376
Pour ce test, la regression linéaire sur ces calculs donne un ordre de convergence effectif de $5.9504269$ dans le cas de la méthode de Gauss, et $4.0214371$ dans celui de la méthode de Simpson. La théorie prévoit respectivement des ordres de 6 et de 4, sous réserve de régularité suffisante pour les fonctions intégrées. Concernant le coût de calcul, les programmes proposés ne sont pas optimisés et les deux méthodes requièrent chacune $3N$ évaluations de la fonction intégrée. Le coût de la méthode de Simpson peut être légèrement réduit en programmant la forme équivalente :
\begin{equation*} \int_a^b f(x) dx \simeq \frac{h}{6}\left[f(a)+2\sum_{k=1}^{N-1}f(a+kh)+4\sum_{k=0}^{N-1}f(a+(k+\tfrac{1}{2})h)+f(b)\right]. \end{equation*}De cette manière il faut seulement $2N+1$ évaluations de la fonction intégrée. Néanmoins, cette réduction du coût ne suffit pas à compenser la différence sur l'ordre de la méthode. Dans l'idée, il existe deux constantes $C_{GL}$ et $C_S$ ne dépendant que de la méthode et de la fonction intégrée, telle que l'erreur pour $N$ sous-intervalles soit de l'ordre de $C_{GL} N^{-6}$ pour Gauss-Legendre et $C_{S} N^{-4}$ pour Simpson. Supposons que chaque évaluations de $f$ prenne 1 seconde et que le reste des calculs soit de durée négligeable, pour atteindre une précision de $\epsilon$ il faudra un temps de l'ordre de $3(C_{GL}/\epsilon)^{1/6}$ par Gauss-Legendre et de l'ordre de $2(C_S/\epsilon)^{1/4}$ par Simpson. À une constante multiplicative près qui ne dépend que des données ($f$, $[a,b]$ et des constantes universelles liées aux méthodes utilisées), le temps de calcul $T_{S}$ pour Simpson augmente donc comme $T_{GL}^{3/2}$ lorsque la précision demandée $\epsilon$ tend vers 0.
$\square$ Programmer la méthode du point milieu sur $[a,b]$ utilisant une subdivision régulière.
def PointMilieu(f,a,b,N):
h = (b-a)/N
x = np.arange(a,b,h)
X2 = x + h/2
F = f(X2)
I = h*np.sum(F)
return I
2. Par la méthode du point milieu, approcher l'intégrale suivante \begin{equation*} J = \int_0^1\frac{e^{\sin(x)}}{x^{8/9}}\mathrm{d}x\simeq 10.09485330. \end{equation*} On pourra examiner la vitesse de convergence en fonction du nombre de points de la subdivision et analyser les observations.
def h(x):
return np.exp(np.sin(x))/(x**(8/9))
ListeN = 2**np.arange(4,20)
IPM = []
for N in ListeN:
IPM.append(PointMilieu(h,0,1,N))
Iex = np.array(10.09485330)
Err_PM = np.abs(IPM-Iex)
plt.plot(np.log(ListeN),np.log(Err_PM),'-x',label="Point-Milieu")
plt.legend()
plt.title("Courbes de convergence")
plt.xlabel("log N")
plt.ylabel("log erreur")
plt.show()
aPM = np.polyfit(np.log(ListeN),np.log(Err_PM),1)[0]
print("Ordre effectif de Point Milieu : "+str(-aPM))
Ordre effectif de Point Milieu : 0.1110951256016846
L'ordre obtenu par regression linéaire est de |0.1110968|. Les valeurs obtenues pour l'intégrale approchée convergent très lentement vers la valeur exacte, pour les différentes subdivisions considérées, on obtient les valeurs approchées suivantes
ListeN = 2**np.arange(4,20)
print("N \t Integrale")
for N in ListeN:
print(N, "\t", PointMilieu(h,0,1,N))
N Integrale 16 4.819314986713353 32 5.209596671023749 64 5.571388812091542 128 5.906546291050773 256 6.216939961157075 512 6.504361343482547 1024 6.770493774578032 2048 7.016906507766329 4096 7.245057254758516 8192 7.456297844749772 16384 7.651880896858635 32768 7.8329666373869244 65536 8.000629501902932 131072 8.155864380829938 262144 8.299592463244014 524288 8.432666675727575
Quelques précisions sur ces observations :
la formule d'erreur de la quadrature élémentaire du point milieu, dans le cas d'une fonction $f\in\mathcal{C}^2([a,b])$ prend la forme
\begin{equation*}
\dfrac{(b-a)^3}{24}f''(\xi), \quad \xi\in]a,b[.
\end{equation*}
Ici la dérivée seconde de l'intégrande $\dfrac{e^{\sin(x)}}{x^{8/9}}$ prend la forme $\dfrac{\alpha(x)}{x^{26/9}}$ avec $\alpha$ une fonction régulière sur le fermé $[0,1]$ non-nulle en 0.
En considérant l'erreur globable pour la quadrature composée pour $n$ sous-intervalles de taille $h=1/n$, on obtient donc en sommant les erreurs locales sur les sous-intervalles constituant $[h,1]$ :
\begin{equation*}
\sum_{i=1}^{n-1}\dfrac{h^3}{24}\dfrac{\alpha(\xi_i)}{\xi_i^{26/9}},\quad \xi_i\in]ih,(i+1)h[.
\end{equation*}
On peut majorer la valeur absolue de cette somme par la quantité
\begin{equation*}
\dfrac{h^3}{24 h^{26/9}}\|\alpha\|_\infty\sum_{i=1}^{n-1} \dfrac{1}{i^{26/9}} \leq \dfrac{\|\alpha\|_\infty}{24}h^{1/9}\sum_{i=1}^{+\infty} \dfrac{1}{i^{26/9}}
\end{equation*}
où la série converge (on peut penser ici à faire le lien entre l'intégrabilité de $f$, les comparaisons série/intégrale, etc.)
L'erreur commise sur le premier intervalle $[0,h]$, quant à elle, est liée au comportement de la quantité
\begin{equation*}
\int_{0}^h \dfrac{1}{x^{8/9}}\, dx - \dfrac{h}{(h/2)^{8/9}},
\end{equation*}
Chacun des deux termes se comporte à des constantes multiplicatives près comme $h^{1/9}$.
L'erreur globale pour la quadrature sur $]0,1]$ est donc $O(h^{1/9})$, où $1/9\simeq 0.111111$ est bien l'ordre observé.
Un peu d'analyse.
On se donne $h\in]0,1[$ fixé. Proposer une méthode gaussienne à un point, exacte pour tout $p\in\mathbb{R}_1[X]$ dans l'évaluation de
\begin{equation*}
\int_0^h\frac{p(x)}{x^{8/9}}\mathrm{d}x.
\end{equation*}
Il s'agit d'identifier une quadrature exacte sur $\mathbb{R}_1[X]$ destinée à l'évaluation d'intégrales de la forme précédente. On peut pour cela identifier les premiers polynômes orthogonaux pour le poids $x^{-8/9}$ sur $]0,1]$, ou bien procéder par identification des paramètres de la quadrature à un point. \begin{equation*} \int_0^h \dfrac{ax+b}{x^{8/9}}\,dx = a\dfrac{9}{10}h^{10/9}+9bh^{1/9}. \end{equation*} La quadrature correspondante sera de la forme $Q(p)=\omega(ax_0+b)$ et sera exacte sur $\mathbb{R}_1[X]$ si et seulement si $\omega x_0 = \tfrac{9}{10}h^{10/9}$ et $\omega = 9h^{1/9}$, c'est à dire si et seulement si $\omega = 9h^{1/9}$ et $x_0 = h/10$.
Ainsi la quadrature retenue est la suivante \begin{equation*} \int_0^h \dfrac{f(x)}{x^{8/9}}\mathrm{d}x \simeq 9h^{1/9} f\left(\dfrac{h}{10}\right). \end{equation*}
3. Approcher l'intégrale $J$ par une méthode hybride utilisant la quadrature gaussienne obtenue sur $]0,h]$ et la quadrature composée du point milieu à $n$ points sur $[h,1]$. On pourra ensuite choisir $h$ en fonction de $n$ de manière à optimiser la vitesse de convergence.
La formule considérée prend la forme suivante, dans laquelle on a posé $x_i=h+i\dfrac{1-h}{n}$ une subdivision régulière de $[h,1]$, et $x_{i+1/2}=\tfrac{1}{2}(x_i+x_{i+1})$: \begin{equation*} \begin{aligned} \int_0^1 \dfrac{f(x)}{x^{8/9}}\mathrm{d}x &= \int_0^h \dfrac{f(x)}{x^{8/9}}\mathrm{d}x + \sum_{i=0}^{n-1} \int_{x_i}^{x_{i+1}}\dfrac{f(x)}{x^{8/9}}\mathrm{d}x &\simeq 9h^{1/9} f\left(\dfrac{h}{10}\right) + \dfrac{1-h}{n} \sum_{i=0}^{n-1}\dfrac{f(x_{i+1/2})}{x_{i+1/2}^{8/9}}. \end{aligned} \end{equation*}
def f(x):
return np.exp(np.sin(x))/(x**(8/9))
Iex = 10.09485330
H = 0.2*0.8**np.arange(1,15)
ERR = []
for i in range(len(H)):
ListeN = 2**np.arange(4,20)
Err = []
for N in ListeN:
h = H[i]
Iapp = PointMilieu(f,h,1,N) + 9*h**(1/9)*np.exp(np.sin(h/10))
Err.append(np.abs(Iapp-Iex))
ERR.append(np.min(Err)) # Stockage de la valeur minimale de l'erreur en fonction de h
plt.plot(np.log(ListeN),np.log(Err),'-x',label="h = "+str(np.round(h,5)))
plt.legend()
plt.title("Courbes de convergence")
plt.xlabel("log N")
plt.ylabel("log erreur")
plt.show()
plt.plot(np.log(H),np.log(ERR),'-x')
plt.title("Courbes de convergence")
plt.xlabel("log h")
plt.ylabel("log erreur")
plt.show()
aHyb = np.polyfit(np.log(H),np.log(ERR),1)[0]
print("Ordre effectif en h : "+str(aHyb))
Ordre effectif en h : 2.1099091178463856
Précisions sur l'optimisation des paramètres
Adaptons l'analyse précédemment menée pour la méthode du point milieu, mais sur $[h,1]$ seulement (le pas d'intégration est alors $(1-h)/n$.
L'erreur de quadrature pour l'approximation de la somme des $n$ termes s'écrit:
\begin{equation*}
\begin{aligned}
\left\vert\sum_{i=0}^{n-1} \left(\int_{x_i}^{x_{i+1}}\dfrac{f(x)}{x^{8/9}}\mathrm{d}x-\dfrac{1-h}{n}\dfrac{f(x_{i+1/2})}{x_{i+1/2}^{8/9}}\right)\right\vert
&\leq \sum_{i=0}^{n-1} \dfrac{(1-h)^3}{24 n^3}\|\alpha\|_{\infty}\dfrac{1}{\xi_i^{26/9}},\quad \textrm{où } \xi_i\in[x_i,x_{i+1}],\\
&\leq \dfrac{\|\alpha\|_\infty}{24 n^3} \sum_{i=0}^{n-1} \dfrac{1}{x_i^{26/9}}.
\end{aligned}
\end{equation*}
Quelle que soit la valeur de $h\in]0,1[$ et de $n\in\mathbb{N}^\star$, la série partielle qui intervient prend aussi la forme
\begin{equation*}
\sum_{i=0}^{n-1} \dfrac{1}{\left(h+\tfrac{i(1-h)}{n}\right)^{26/9}} = \dfrac{1}{h^{26/9}} \sum_{i=0}^{n-1}\dfrac{1}{1+\tfrac{i}{n}\tfrac{1-h}{h}} \leq \dfrac{n}{h^{26/9}}.
\end{equation*}
L'erreur pour les termes considérés est donc majorée par une quantité de la forme
\begin{equation*}
\dfrac{C_1}{n^2h^{26/9}},
\end{equation*}
où $C_1>0$ est une constante indépendante de $h$ et de $n$.
Concernant l'intégration gaussienne sur $[0,h]$, l'erreur commise est liée aux premiers termes non-nuls du développement de Taylor du numérateur $f(x)=e^{\sin(x)}$ en $h/10$: $f(x) = P_1(x) + \tfrac{1}{2}(x-h/10)^2 \phi(x)$ avec $P_1(x)=f(h/10)+(x-h/10)f'(h/10)$ et $\phi$ régulière. \begin{equation*} \begin{aligned} \int_0^h \dfrac{f(x)}{x^{8/9}}\mathrm{d}x - 9h^{1/9} f\left(\dfrac{h}{10}\right) = \int_0^h \dfrac{P_1(x)}{x^{8/9}}\mathrm{d}x - 9h^{1/9} P_1\left(\dfrac{h}{10}\right) + \int_0^h \dfrac{\tfrac{1}{2}(x-h/10)^2\phi(x)}{x^{8/9}}\mathrm{d}x \end{aligned} \end{equation*} La formule étant exacte pour les polynômes de degré 1, la première différence du second membre est nulle. Le terme restant se majore (en valeur absolue) par: \begin{equation*} \dfrac{\|\phi\|_\infty}{2}\int_0^1 \dfrac{(hy-h/10)^2}{(hy)^{8/9}}hdy = \dfrac{\|\phi\|_\infty}{2}h^{19/9}\int_0^1 \dfrac{(y-1/10)^2}{(y)^{8/9}}dy. \end{equation*} Il existe donc une constante $C_2$ indépendante de $h$ et de $n$ telle que l'erreur sur cette quadrature soit majorée par une quantité de la forme \begin{equation*} C_2h^{19/9}. \end{equation*} Les deux majorations précédemment obtenues permettent de dégager un régime "optimal à la limite" pour choisir $h$ en fonction de $n$. Supposant que les majorations sont optimales (au sens où l'erreur est équivalente à son majorant, ce qui n'a pas été prouvé) l'erreur globale se comporte comme \begin{equation*} \dfrac{C_1}{n^2h^{26/9}}+C_2h^{19/9}. \end{equation*} L'expérience numérique confirme ce comportement, on effectue l'analyse de convergence pour différentes valeurs de $h$, de sorte à "séparer" le comportement des deux termes. On observe la saturation de l'erreur sur une quantité qui n'est autre que l'erreur de la quadrature gaussienne. On peut ensuite tracer en fonction de $h$ cette valeur et vérifier sa convergence vers 0 comme $h^{19/9}$.
Pour minimiser l'erreur globale on peut choisir $h$ en fonction de $n$ de sorte que les deux erreurs soient du même ordre : \begin{equation*} \dfrac{C_1}{n^2h^{26/9}} \sim C_2h^{19/9} \end{equation*} En réalité, les constantes sont importantes car elles définissent une constante $C$ telle que le choix optimal ait la forme \begin{equation*} h = \dfrac{C}{n^{2/5}}, \end{equation*} et l'erreur se comporte comme finalement \begin{equation*} \dfrac{\tilde{C}}{n^{4/5}}. \end{equation*}
Err = []
for N in ListeN:
h = N**(-2/5) # Choix optimisé (à une constante multiplicative près)
Iapp = PointMilieu(f,h,1,N) + 9*h**(1/9)*np.exp(np.sin(h/10)) # Méthode hybride
Err.append(np.abs(Iapp-Iex))
plt.plot(np.log(ListeN),np.log(Err),'-x',linewidth=3,label="Optimisé")
for i in range(len(H)):
ListeN = 2**np.arange(4,20)
Err = []
for N in ListeN:
h = H[i]
Iapp = PointMilieu(f,h,1,N) + 9*h**(1/9)*np.exp(np.sin(h/10))
Err.append(np.abs(Iapp-Iex))
ERR.append(np.min(Err)) # Stockage de la valeur minimale de l'erreur en fonction de h
plt.plot(np.log(ListeN),np.log(Err),'-x',label="h = "+str(np.round(h,5)))
plt.legend()
plt.title("Courbes de convergence")
plt.xlabel("log N")
plt.ylabel("log erreur")
plt.show()
aHyb = np.polyfit(np.log(ListeN),np.log(Err),1)[0]
print("Ordre effectif en N : "+str(-aHyb))
Ordre effectif en N : 1.1080920263854717