TP4 – Intégration numérique

(É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.$

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]$.

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


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

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

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.


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.

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

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


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