{ "cells": [ { "cell_type": "markdown", "id": "3aefd380", "metadata": {}, "source": [ "
\n", "\n", "Ce fichier reflète les énoncés des exercices d'un chapitre de la deuxième édition du livre *[Programmation Python par la pratique](https://www.dunod.com/sciences-techniques/programmation-python-par-pratique-problemes-et-exercices-corriges-0)*. Tous les énoncés peuvent être téléchargés au format [Jupyter Notebook](https://python.guillod.org/livre/) ou exécutés directement en ligne sur [mybinder](https://mybinder.org/v2/gh/guillod/livre-python/HEAD). Les corrigés sont disponibles dans le livre en version papier (ISBN [9782100862122](https://www.dunod.com/sciences-techniques/programmation-python-par-pratique-problemes-et-exercices-corriges-0)) ou numérique (ISBN [9782100875153](https://www.dunod.com/sciences-techniques/programmation-python-par-pratique-problemes-et-exercices-corriges-0)) publiés chez Dunod. Ce fichier reflète les exercices tels que publiés dans cet ouvrage et diffère quelque peu des exercices présentés à la page [python.guillod.org](https://python.guillod.org/)." ] }, { "cell_type": "markdown", "id": "b3f5a7f0", "metadata": {}, "source": [ "# 5 Intégration" ] }, { "cell_type": "markdown", "id": "d6727efb", "metadata": {}, "source": [ "
\n", "\n", "Le but est d'obtenir une approximation d'une intégrale définie du type" ] }, { "cell_type": "markdown", "id": "86fa116a", "metadata": {}, "source": [ "$$\n", "J = \\int_a^b f(x) \\, \\mathrm{d} x\n", "$$" ] }, { "cell_type": "markdown", "id": "be4a1a9f", "metadata": {}, "source": [ "pour une certaine fonction $f:[a,b] \\to \\mathbb{R}$ trop compliquée pour *a priori* déterminer la valeur de $J$ à la main.\n", "Des méthodes d'approximations déterministes et probabilistes seront introduites pour obtenir une approximation $\\tilde{J}$ de $J$.\n", "\n", "**Concepts abordés:**\n", "\n", "* méthodes classiques (rectangles, trapèzes et Simpson)\n", "\n", "* méthode de Monte-Carlo\n", "\n", "* vitesse de convergence\n", "\n", "* statistiques" ] }, { "cell_type": "markdown", "id": "a6e820d5", "metadata": {}, "source": [ "# Exercice 5.1: Méthode des rectangles" ] }, { "cell_type": "markdown", "id": "1ca83c4f", "metadata": {}, "source": [ "
\n", "\n", "La méthode des rectangles est basée sur la définition de l'intégrale au sens de Riemann. La première étape est de découper l'intervalle $[a,b]$ en $N$ intervalles $[x_n,x_{n+1}]$ de même taille $\\delta=\\frac{b-a}{N}$, *i.e.* $x_n = a+n\\delta$ pour $n\\in\\{0,1,\\dots,N-1\\}$. La seconde étape consiste à supposer que la fonction $f$ est constante sur chaque intervalle $[x_n,x_{n+1}]$, donc à faire l'approximation" ] }, { "cell_type": "markdown", "id": "54152df1", "metadata": {}, "source": [ "$$\n", "J_n = \\int_{x_n}^{x_{n+1}} f(x) \\, \\mathrm{d} x \\approx \\delta f(\\tilde{x}_n)\n", "$$" ] }, { "cell_type": "markdown", "id": "6e0dfe1c", "metadata": {}, "source": [ "pour $\\tilde{x}_n$ une certaine valeur à choisir dans l'intervalle $[x_n,x_{n+1}]$. Le choix de $\\tilde{x}_n$ peut par exemple être fait par $\\tilde{x}_n = x_n + \\alpha\\delta$ avec $\\alpha\\in[0,1]$. Finalement l'approximation de $J$ est donnée par la somme des approximations de $J_n$," ] }, { "cell_type": "markdown", "id": "de9a0c7c", "metadata": {}, "source": [ "$$\n", "\\tilde{J} = \\sum_{n=0}^{N-1} \\delta f(\\tilde{x}_n)\\,.\n", "$$" ] }, { "cell_type": "markdown", "id": "5dcb2f29", "metadata": {}, "source": [ "En supposant que $f\\in C^1([a,b])$, alors il est possible de montrer que la méthode des rectangles converge et que sa vitesse de convergence est d'ordre un. Une méthode numérique est dite d'ordre $k$ si l'erreur entre l'approximation numérique et le résultat exact est de l'ordre de $N^{-k}$.\n", "\n", "**a)**\n", "Choisir une fonction continue $f:[a,b]\\to\\mathbb{R}$ et définir la fonction Python `f(x)` correspondante. Pour tester le code, il est judicieux de choisir une fonction $f$ dont l'intégrale peut être facilement calculable à la main.\n", "\n", "**Indication.**\n", "La liste des fonctions mathématiques de base disponibles en Python dans le module `math` est disponible [ici](https://docs.python.org/fr/3/library/math.html). À noter que NumPy définit également des fonctions mathématiques, voir la documentation [ici](https://numpy.org/doc/stable/reference/routines.math.html)." ] }, { "cell_type": "markdown", "id": "2f32c06d", "metadata": {}, "source": [ "**b)**\n", "Écrire une fonction `rectangles(f,a,b,N)` qui retourne l'approximation de l'intégrale $J$ par la méthode des rectangles par exemple en choisissant $\\tilde{x}_n=x_n$, *i.e.* le bord gauche de l'intervalle $[x_n,x_{n+1}]$.\n", "\n", "**Indication.**\n", "Il n'est pas nécessaire de stoker toutes les valeurs des approximations de $J_n$, mais il est possible d'incrémenter une variable pour chaque approximation de $J_n$." ] }, { "cell_type": "markdown", "id": "0c1f1a77", "metadata": {}, "source": [ "**c)**\n", "Modifier la fonction précédente pour que celle-ci prenne un paramètre optionnel `alpha` déterminant le choix du paramètre $\\alpha\\in[0,1]$." ] }, { "cell_type": "markdown", "id": "d075af91", "metadata": {}, "source": [ "**d)**\n", "Écrire une fonction `plot_rectangles(f,a,b,N,alpha=0.5)` qui représente graphiquement l'approximation par la méthode des rectangles." ] }, { "cell_type": "markdown", "id": "3364b947", "metadata": {}, "source": [ "**e)**\n", "Déterminer empiriquement la vitesse de convergence de la méthode des rectangles en fonction de $N$." ] }, { "cell_type": "markdown", "id": "f28d8493", "metadata": {}, "source": [ "**f)**\n", "Déterminer analytiquement la convergence de la méthode des rectangles. Quelles sont les hypothèses nécessaires sur $f$ ?\n", "\n", "**Indication.**\n", "Utiliser le théorème des accroissements finis." ] }, { "cell_type": "markdown", "id": "4f3d300c", "metadata": {}, "source": [ "# Exercice 5.2: Méthode des trapèzes" ] }, { "cell_type": "markdown", "id": "4bdcc775", "metadata": {}, "source": [ "
\n", "\n", "La méthode des trapèzes est basée sur une approximation linéaire sur chaque intervalle $[x_n,x_{n+1}]$, plus spécifiquement:" ] }, { "cell_type": "markdown", "id": "ef5773c5", "metadata": {}, "source": [ "$$\n", "J_n = \\int_{x_n}^{x_{n+1}} f(x) \\, \\mathrm{d} x \\approx \\delta \\frac{f(x_n) + f(x_{n+1})}{2} \\,.\n", "$$" ] }, { "cell_type": "markdown", "id": "0cdb318b", "metadata": {}, "source": [ "**a)**\n", "Écrire une fonction Python `trapezes(f,a,b,N)` qui retourne l'approximation de l'intégrale $J$ par la méthode des trapèzes. Tester la fonction `trapezes(f,a,b,N)` pour différentes fonctions $f$." ] }, { "cell_type": "markdown", "id": "219623b8", "metadata": {}, "source": [ "**b)**\n", "L'implémentation de votre fonction `trapezes(f,a,b,N)` est-elle optimale quant au nombre d'évaluations de $f$ effectuées par rapport au nombre d'évaluations nécessaires ? Une implémentation optimale de la fonction `trapezes(f,a,b,N)` devrait effectuer $N+1$ évaluations de $f$." ] }, { "cell_type": "markdown", "id": "b281898c", "metadata": {}, "source": [ "**c)**\n", "Déterminer empiriquement la vitesse de convergence de la méthode des trapèzes en fonction de $N$." ] }, { "cell_type": "markdown", "id": "27d77667", "metadata": {}, "source": [ "**d)**\n", "! Déterminer analytiquement la convergence de la méthode des trapèzes. Quelles sont les hypothèses nécessaires sur $f$ ?" ] }, { "cell_type": "markdown", "id": "28faa553", "metadata": {}, "source": [ "# Exercice 5.3: Méthode de Monte-Carlo" ] }, { "cell_type": "markdown", "id": "8a3cf4b0", "metadata": {}, "source": [ "
\n", "\n", "La méthode de Monte-Carlo (du nom des casinos, pas d'une personne) est une approche probabiliste permettant d'approximer la valeur d'une intégrale. L'idée de base est que l'intégrale $J$ peut être vue comme l'espérance d'une variable aléatoire uniforme $X$ sur l'intervalle $[a,b]$:" ] }, { "cell_type": "markdown", "id": "4189723b", "metadata": {}, "source": [ "$$\n", "J = \\int_a^b f(x) \\, \\mathrm{d} x = (b-a)\\mathbb{E}(f(X)) \\,.\n", "$$" ] }, { "cell_type": "markdown", "id": "9df24ee2", "metadata": {}, "source": [ "Par la loi des grands nombres cette espérance peut être approximée par la moyenne empirique:" ] }, { "cell_type": "markdown", "id": "3f99ea8a", "metadata": {}, "source": [ "$$\n", "\\tilde{J} = \\frac{b-a}{N}\\sum_{i=0}^{N-1} f(x_i) \\,,\n", "$$" ] }, { "cell_type": "markdown", "id": "17ba0294", "metadata": {}, "source": [ "où les $x_i$ sont tirés aléatoirement dans l'intervalle $[a,b]$ avec une loi de probabilité uniforme.\n", "\n", "**a)**\n", "Écrire une fonction `montecarlo(f,a,b,N)` qui détermine une approximation $\\tilde{J}$ de $J$ par la méthode de Monte-Carlo.\n", "\n", "**Indication.**\n", "Pour générer un vecteur de nombres aléatoires, le sous-module `random` de NumPy peut être utile, voir la documentation [ici](https://numpy.org/doc/stable/reference/random/)." ] }, { "cell_type": "markdown", "id": "51621cb4", "metadata": {}, "source": [ "**b)**\n", "Modifier la fonction précédente, pour qu'elle retourne en plus de la moyenne $\\tilde{J}$ également la variance empirique:" ] }, { "cell_type": "markdown", "id": "1e1fcf4b", "metadata": {}, "source": [ "$$\n", "\\tilde{V} = \\frac{(b-a)^2}{N}\\sum_{i=0}^{N-1} \\left(f(x_i)-\\frac{\\tilde{J}}{b-a}\\right)^2 \\,.\n", "$$" ] }, { "cell_type": "markdown", "id": "5f372deb", "metadata": {}, "source": [ "**c)**\n", "Étudier empiriquement la convergence de la méthode de Monte-Carlo en fonction de $N$ en faisant pour chaque valeur de $N$ une statistique sur $k$ exécutions. Plus précisément cela consiste à faire $k$ évaluations de $\\tilde{J}$ par la méthode de Monte-Carlo et de calculer la moyenne et la variance des $k$ résultats obtenus." ] }, { "cell_type": "markdown", "id": "bb20cf74", "metadata": {}, "source": [ "**d)**\n", "Déterminer analytiquement la convergence de la méthode de Monte-Carlo. Quelles sont les hypothèses nécessaires sur $f$ ?\n", "\n", "**Indication.**\n", "Utiliser le théorème central limite." ] }, { "cell_type": "markdown", "id": "606484f4", "metadata": {}, "source": [ "# Exercice 5.4: ! Méthode de Simpson" ] }, { "cell_type": "markdown", "id": "c6ce8161", "metadata": {}, "source": [ "
\n", "\n", "La méthode de Simpson consiste à approximer la fonction $f$ sur chaque intervalle $[x_n,x_{n+1}]$ par un polynôme de degré deux. Le choix le plus naturel est le polynôme $p_n$ de degré deux passant par les points $(x_n,f(x_n))$, $(\\frac{x_n+x_{n+1}}{2},f(\\frac{x_n+x_{n+1}}{2}))$ et $(x_{n+1},f(x_{n+1}))$.\n", "\n", "**a)**\n", "Déterminer la forme explicite du polynôme $p_n$.\n", "\n", "**Indication.**\n", "Le polynôme $L(x) = \\frac{(x-c)(x-b)}{(a-c)(a-b)}$ prend la valeur 1 en $x=a$ et la valeur 0 en $x=b$ et $x=c$. Faire une combinaison linéaire de trois polynômes de ce type." ] }, { "cell_type": "markdown", "id": "5fca9f94", "metadata": {}, "source": [ "**b)**\n", "Calculer l'approximation donnée par $J_n \\approx \\int_{x_n}^{x_{n+1}} p_n(x)\\,\\mathrm{d} x \\,.$\n", "\n", "**Indication.**\n", "Il est possible de calculer cette intégrale à la main ou bien de le faire avec le module SymPy, voir la documentation [ici](https://docs.sympy.org/latest/modules/integrals/integrals.html)." ] }, { "cell_type": "markdown", "id": "c9029c0b", "metadata": {}, "source": [ "**c)**\n", "Simplifier à la main la somme $\\tilde{J}$ des approximations de $J_n$.\n", "\n", "**Réponse.**\n", "Le résultat est:" ] }, { "cell_type": "markdown", "id": "4881b3a0", "metadata": {}, "source": [ "$$\n", "\\tilde{J} = \\frac{\\delta}{3}\\left[\\frac{f(b)-f(a)}{2}+\\sum_{n=0}^{N-1}\\left(f(x_{n})+2f\\left(\\frac{x_{n}+x_{n+1}}{2}\\right)\\right)\\right] \\,.\n", "$$" ] }, { "cell_type": "markdown", "id": "8928e1e7", "metadata": {}, "source": [ "\n", "**d)**\n", "Écrire une fonction `simpson(f,a,b,N)` permettant de calculer une approximation de $J$ avec la méthode de Simpson.\n", "\n" ] }, { "cell_type": "markdown", "id": "76b2929c", "metadata": {}, "source": [ "**e)**\n", "Comparer la précision, c'est-à-dire la vitesse de convergence, des méthodes des rectangles, des trapèzes et de Simpson en fonction de $N$ pour une fonction lisse et la fonction $f(x)=\\sqrt{1-x^2}$ sur $[0,1]$ (dont l'intégrale est $\\frac{\\pi}{4}$)." ] }, { "cell_type": "markdown", "id": "3109896a", "metadata": {}, "source": [ "**f)**\n", "Si ce n'est pas déjà fait, proposer une implémentation parallèle de la méthode de Simpson en utilisant l'indexation NumPy." ] }, { "cell_type": "markdown", "id": "7030a92e", "metadata": {}, "source": [ "# Exercice 5.5: !! Intégration avec Scipy" ] }, { "cell_type": "markdown", "id": "802db586", "metadata": {}, "source": [ "Les méthodes d'intégrations précédentes et d'autres sont définies dans le module `integrate` de Scipy. Ce module permet en particulier de traiter des cas plus compliqués: intégrales singulières, généralisées ou en plusieurs dimensions.\n", "\n", "**a)**\n", "Définir une fonction `E(n,x)` calculant numériquement l'intégrale suivante:" ] }, { "cell_type": "markdown", "id": "9b85b98a", "metadata": {}, "source": [ "$$\n", "E_n(x) = \\int_1^\\infty \\frac{e^{-xt}}{t^n} \\mathrm{d} t \\,.\n", "$$" ] }, { "cell_type": "markdown", "id": "a04c1491", "metadata": {}, "source": [ "**Indication.**\n", "Lire la documentation du sous-module `integrate` de Scipy disponible [ici](https://docs.scipy.org/doc/scipy/tutorial/integrate.html)." ] }, { "cell_type": "markdown", "id": "22e01f7d", "metadata": {}, "source": [ "**b)**\n", "Déterminer une approximation de l'intégrale double:" ] }, { "cell_type": "markdown", "id": "46bdbab5", "metadata": {}, "source": [ "$$\n", "I = \\int_{0}^{\\pi} \\left(\\int_{0}^{y} x \\sin(xy) \\,\\mathrm{d} x \\right) \\mathrm{d} y \\,.\n", "$$" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 5 }