{ "cells": [ { "cell_type": "markdown", "id": "7e0247c7", "metadata": {}, "source": [ "# TP1 — Intégration numérique et méthodes d’interpolation" ] }, { "cell_type": "markdown", "id": "5863edad", "metadata": {}, "source": [ "#### Préambule\n", "La fiche suivante traite de quelques méthodes d’intégration numérique, ainsi que d’interpolation de fonctions.\n", "Il n’est pas attendu que vous soyez capable de la terminer endéans les trois heures de TP.\n", "L’important est d’essayer d’avancer à votre rythme, et de manipuler à la fois des mathématiques et de l’implémentation numérique.\n", "La fiche a été conçue pour être suffisamment longue pour occuper même celles et ceux d’entre vous qui seraient les plus rapides, motivés, et curieux." ] }, { "cell_type": "markdown", "id": "75c911ff", "metadata": {}, "source": [ "## Initialisation des packages" ] }, { "cell_type": "code", "execution_count": 1, "id": "43d1862e", "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "from random import uniform" ] }, { "cell_type": "markdown", "id": "4af541a4", "metadata": {}, "source": [ "## I. Méthode des rectangles et du point milieu" ] }, { "cell_type": "markdown", "id": "a69c91dc", "metadata": {}, "source": [ "### I.1 Méthode des rectangles" ] }, { "cell_type": "markdown", "id": "6ea088fe", "metadata": {}, "source": [ "Supposons qu’on souhaite évaluer numériquement l’intégrale\n", "$$\n", " \\int_{a}^{b} f(x)\\,\\mathrm{d}x\\text{.}\n", "$$\n", "Dans ce TP, nous allons considérer différentes méthodes basées sur une décomposition de l’intervalle $ [a,b] $ en sous-intervalles.\n", "À cette fin, on définit\n", "$$\n", " x_{i} = a + \\frac{i}{n}(b-a)\n", " \\quad\n", " \\mbox{pour tout $ i \\in \\{0,\\dotsc,n\\} $.}\n", "$$" ] }, { "cell_type": "markdown", "id": "962eb1f5", "metadata": {}, "source": [ "#### Question 1\n", "Représenter graphiquement les points $ x_{i} $ sur l’intervalle $ [a,b] $." ] }, { "cell_type": "markdown", "id": "de85c4ef", "metadata": {}, "source": [ "On définit ci-après trois méthodes d’intégration numérique basées sur le calcul d’aires de rectangles.\n", "La méthode des rectangles bas consiste à approximer\n", "$$\n", " \\int_{a}^{b} f(x)\\,\\mathrm{d}x \\approx I_{\\mathrm{Rb}}\\text{,}\n", "$$\n", "où on définit\n", "$$\n", " I_{\\mathrm{Rb}} = \\sum_{i=1}^{n} f(x_{i-1})(x_{i}-x_{i-1})\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "0615c341", "metadata": {}, "source": [ "La méthode des rectangles hauts consiste à approximer\n", "$$\n", " \\int_{a}^{b} f(x)\\,\\mathrm{d}x \\approx I_{\\mathrm{Rh}}\\text{,}\n", "$$\n", "où on définit\n", "$$\n", " I_{\\mathrm{Rh}} = \\sum_{i=1}^{n} f(x_{i})(x_{i}-x_{i-1})\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "9b95b7ab", "metadata": {}, "source": [ "#### Question 2\n", "Représenter graphiquement le calcul effectué avec les méthodes des rectangles hauts et bas pour $ n = 3 $ , $ 4 $ , $ 5 $, etc. " ] }, { "cell_type": "markdown", "id": "e0959ddd", "metadata": {}, "source": [ "#### Question 3\n", "Compléter les fonctions int_Rb et int_Rh ci-après selon les spécifications données.\n", "Ces deux fonctions devraient, à partir d’une fonction $ f $ , de deux points $ a $ et $ b $, et d’un entier $ n $, renvoyer l’approximation numérique de\n", "$$\n", " \\int_{a}^{b} f(x)\\,\\mathrm{d}x\n", "$$\n", "par la méthode des rectangles bas et hauts respectivement." ] }, { "cell_type": "code", "execution_count": 2, "id": "130e67ba", "metadata": {}, "outputs": [], "source": [ "def int_Rb(f, a, b, n):\n", " '''\n", " Input : f est une fonction reelle definie sur l’intervalle [a,b], a < b sont deux reels, n est un naturel non nul.\n", " Output : renvoyer I_Rb, l’approximation numerique de int_a^b f dx par la methode des rectangles bas.\n", " '''\n", " # A COMPLETER\n", " return I_Rb" ] }, { "cell_type": "code", "execution_count": 3, "id": "ef96eb8b", "metadata": {}, "outputs": [], "source": [ "def int_Rh(f, a, b, n):\n", " '''\n", " Input : f est une fonction reelle définie sur l’intervalle [a,b], a < b sont deux reels, n est un naturel non nul.\n", " Output : renvoyer I_Rh, l’approximation numerique de int_a^b f dx par la methode des rectangles hauts.\n", " '''\n", " # A COMPLETER\n", " return I_Rh" ] }, { "cell_type": "markdown", "id": "8d5e0ff7", "metadata": {}, "source": [ "#### Question 4\n", "Quelle est la complexité algorithmique de ces deux méthodes en fonction de $ n $, en termes du nombre d’appels à la fonction $ f $ ?" ] }, { "cell_type": "markdown", "id": "99d6099a", "metadata": {}, "source": [ "#### Question 5\n", "Calculez explicitement \n", "$$\n", " \\int_{0}^{1} \\frac{1}{1+x^{2}}\\,\\mathrm{d}x\\text{.}\n", "$$\n", "En utilisant les fonctions int_Rb et int_Rb pour différentes valeurs de $ n $ de votre choix, déterminez ensuite une approximation numérique de cette intégrale.\n", "Finalement, représentez sur un graphique la valeur de l’erreur d’approximation en fonction de $ n $ pour $ n $ allant de $1$ à $100$." ] }, { "cell_type": "markdown", "id": "c63553ad", "metadata": {}, "source": [ "#### Question 6\n", "Même question pour \n", "$$\n", " \\int_{0}^{2\\pi} \\cos{x}\\,\\mathrm{d}x\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "f720ad13", "metadata": {}, "source": [ "#### Question 7\n", "Important : la matière permettant de traiter cet exercice n’ayant pas été vue en cours au moment de la séance, il n’est pas attendu que vous soyez capables de le résoudre.\n", "Nous vous encourageons à passer cette question pour le moment, et à y revenir lorsque la dérivabilité et le théorème des accroissements finis auront été traités en cours.\n", "\n", "Soit $ f \\colon [0,1] \\to \\mathbb{R} $ une fonction de classe $C^1$.\n", "L’objectif de cette question est de démontrer que la méthode des rectangles bas converge vers la valeur exacte de l’intégrale\n", "$$\n", " \\int_{0}^{1} f(x)\\,\\mathrm{d}x\n", "$$\n", "lorsque $ n \\to +\\infty $." ] }, { "cell_type": "markdown", "id": "92fd82f5", "metadata": {}, "source": [ "#### (a)\n", "On pose\n", "$$\n", " E_{\\mathrm{Rb}}(f,n) = \\int_{0}^{1} f(x)\\,\\mathrm{d}x - I_{\\mathrm{Rb}} = \\int_{0}^{1} f(x)\\,\\mathrm{d}x - \\sum_{i=1}^{n} f(x_{i-1})(x_{i}-x_{i-1})\n", "$$\n", "l’erreur d’approximation.\n", "\n", "Démontrer que\n", "$$\n", " E_{\\mathrm{Rb}}(f,n) = \\sum_{i=1}^{n} \\int_{x_{i-1}}^{x_{i}} f(x) - f(x_{i-1})\\,\\mathrm{d}x\\text{,}\n", "$$\n", "et en déduire que\n", "$$\n", " \\lvert E_{\\mathrm{Rb}}(f,n) \\rvert \n", " \\leq\n", " \\sum_{i=1}^{n} \\int_{x_{i-1}}^{x_{i}} \\lvert f(x) - f(x_{i-1}) \\rvert \\,\\mathrm{d}x\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "43b274dc", "metadata": {}, "source": [ "#### (b)\n", "On suppose que \n", "$$\n", " \\lvert f'(x) \\rvert \\leq M\n", "$$\n", "pour tout $ x \\in [0,1] $.\n", "Démontrer que, pour tout $ x \\in [x_{i-1},x_{i}] $, on a \n", "$$\n", " \\lvert f(x) - f(x_{i-1}) \\rvert \\leq \\frac{M}{n}\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "f76bd465", "metadata": {}, "source": [ "#### (c)\n", "En déduire que \n", "$$\n", " \\lvert E_{\\mathrm{Rb}}(f,n) \\rvert\n", " \\leq\n", " \\frac{M}{n}\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "968945a5", "metadata": {}, "source": [ "#### (d)\n", "Pour les fonctions des questions 5 et 6, déterminez la valeur optimale de $ M $ ci-dessus, et représentez graphiquement l’erreur d’approximation pour $ n $ allant de $ 1 $ à $ 20 $ ainsi que la valeur $ \\frac{M}{n} $.\n", "Vérifiez que l’inégalité ci-haut est bien satisfaite pour ces deux fonctions.\n", "La convergence semble-t-elle meilleure que celle annoncée par l’inégalité ?" ] }, { "cell_type": "markdown", "id": "9fa8a7aa", "metadata": {}, "source": [ "### I.2 Méthode du point milieu et des trapèzes" ] }, { "cell_type": "markdown", "id": "d5780b16", "metadata": {}, "source": [ "La méthode du point milieu consiste à approximer\n", "$$\n", " \\int_{a}^{b} f(x)\\,\\mathrm{d}x \\approx I_{\\mathrm{M}}\\text{,}\n", "$$\n", "où on définit\n", "$$\n", " I_{\\mathrm{M}} = \\sum_{i=1}^{n} f(\\xi_{i})(x_{i}-x_{i-1})\\text{,}\n", "$$\n", "avec \n", "$$\n", " \\xi_{i} = \\frac{x_{i} + x_{i-1}}{2}\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "1b6c09ac", "metadata": {}, "source": [ "La méthode des trapèzes consiste à approximer\n", "$$\n", " \\int_{a}^{b} f(x)\\,\\mathrm{d}x\n", " \\approx\n", " I_{T}\\text{,}\n", "$$\n", "où on définit\n", "$$\n", " I_{T} = \\sum_{i=1}^{n} \\frac{f(x_{i-1}) + f(x_{i})}{2}(x_{i}-x_{i-1})\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "18b98677", "metadata": {}, "source": [ "#### Question 8\n", "Répéter les questions 2 et 3 avec les méthodes ci-haut.\n", "Les fonctions à compléter sont données ci-dessous." ] }, { "cell_type": "code", "execution_count": 4, "id": "82986239", "metadata": {}, "outputs": [], "source": [ "def int_M(f, a, b, n):\n", " '''\n", " Input : f est une fonction reelle definie sur l’intervalle [a,b], a < b sont deux reels, n est un naturel non nul.\n", " Output : renvoyer I_M, l’approximation numerique de int_a^b f dx par la methode du point milieu.\n", " '''\n", " # A COMPLETER\n", " return I_M" ] }, { "cell_type": "code", "execution_count": 5, "id": "1731a64e", "metadata": {}, "outputs": [], "source": [ "def int_T(f, a, b, n):\n", " '''\n", " Input : f est une fonction reelle definie sur l’intervalle [a,b], a < b sont deux reels, n est un naturel non nul.\n", " Output : renvoyer I_T, l’approximation numerique de int_a^b f dx par la methode des trapezes.\n", " '''\n", " # A COMPLETER\n", " return I_T" ] }, { "cell_type": "markdown", "id": "64845c61", "metadata": {}, "source": [ "### I.3 Ordre d'une méthode d'intégration et convergence" ] }, { "cell_type": "markdown", "id": "1b256b8f", "metadata": {}, "source": [ "#### Question 9\n", "On dit qu’une méthode d’intégration numérique est d’ordre $ m $ lorsqu’elle donne la valeur exacte de l’intégrale de tout polynôme d’ordre $ m $." ] }, { "cell_type": "markdown", "id": "05dd2795", "metadata": {}, "source": [ "#### (a)\n", "Montrer que les méthodes des rectangles sont d’ordre $ 0 $ mais pas d’ordre $ 1 $.\n", "Montrer que les méthodes du point milieu et des trapèzes sont d’ordre $ 1 $." ] }, { "cell_type": "markdown", "id": "0a94c070", "metadata": {}, "source": [ "#### (b) \n", "Pour $ f(x) = x^{2} + x + 1 $, représentez graphiquement $ n\\lvert E(f,n) \\rvert $ pour les différentes méthodes vues ci-haut, pour $ n $ allant de $ 1 $ à $ 20 $.\n", "Faites de même avec $ n^{2}\\lvert E(f,n) \\rvert $.\n", "Qu’observez-vous ?\n", "(Ici, on rappelle que $ E(f,n) $ désigne l’erreur d’approximation d’une méthode numérique, c’est-à-dire, l’écart entre la valeur exacte de l’intégrale et la valeur approchée.)" ] }, { "cell_type": "markdown", "id": "9980974f", "metadata": {}, "source": [ "### I.4 Applications" ] }, { "cell_type": "markdown", "id": "07e7ade7", "metadata": {}, "source": [ "#### Question 10\n", "Appliquez la méthode du point milieu pour approximer\n", "$$\n", " \\int_{0}^{1} \\frac{1}{\\sqrt{x}}\\,\\mathrm{d}x\n", "$$\n", "et\n", "$$\n", " \\int_{0}^{1} \\frac{1}{\\sqrt{x}^{3}}\\,\\mathrm{d}x\\text{,}\n", "$$\n", "pour $ n $ allant de $ 1 $ à $ 100 $.\n", "Qu’observez-vous ?" ] }, { "cell_type": "markdown", "id": "7a8fefe2", "metadata": {}, "source": [ "#### Question 11\n", "On admet que pour $M$ très grand,\n", "$$\n", " \\int_{-M}^M e^{-x^2} \\, \\mathrm{d} x \\approx \\sqrt{\\pi}\\text{.}\n", "$$\n", "En utilisant l'une des méthodes précédentes pour certaines valeurs de $M$, en déduire une approximation de $\\pi$. " ] }, { "cell_type": "markdown", "id": "7fce26e5", "metadata": {}, "source": [ "## Méthode de Monte-Carlo" ] }, { "cell_type": "markdown", "id": "9dc9a10a", "metadata": {}, "source": [ "On rappelle que la fonction uniform du module random importée en début de fiche prend en argument deux réels $a < b$ et renvoie un nombre aléatoire de l'intervalle $[a,b]$ choisi uniformément. \n", "\n", "La méthode de Monte-Carlo est une méthode d'intégration aléatoire. Elle consiste, étant donnée une fonction $f$ positive sur $[a,b]$ à valeur dans $[0,M]$ pour une certaine constante $M > 0$, à choisir aléatoirement uniformément des points $(x_1,y_1),\\dotsc,(x_n,y_n)$ avec $x_i \\in [a,b]$ et $y_i \\in [0,M]$. \n", "\n", "On approxime alors l'intégrale de $f$ sur $[a,b]$ par $I_{MC} = M(b-a)\\frac{1}{n} \\sum_{i=1}^n \\delta_i$, où $\\delta_i = 1$ si $y_i \\leq f(x_i)$, et $0$ sinon.\n", "\n", "Pour être précis, cette méthode se nomme *méthode de Monte-Carlo hit-and-miss*.\n", "Ceci la distingue de la méthode de Monte-Carlo *sample mean*, où on tirerait des points au hasard dans l’intervalle $[a,b]$ en vue d’approximer l’intégrale de $f$ à l’aide des valeurs de $f$ au points choisis.\n", "Les plus curieux d’entre vous pourront se renseigner plus avant à l’aide de ces mots-clés." ] }, { "cell_type": "markdown", "id": "8c4d45b9", "metadata": {}, "source": [ "#### Question 1\n", "Dessiner ce qu'il se passe. Intuitivement, pourquoi s'attendrait-on à ce que $I_{MC}$ soit une approximation de l'intégrale de $f$ sur $[a,b]$ ?" ] }, { "cell_type": "markdown", "id": "be0693dc", "metadata": {}, "source": [ "#### Question 2\n", "Compléter l'implémentation suivante de la méthode de Monte-Carlo." ] }, { "cell_type": "code", "execution_count": 6, "id": "2e765de8", "metadata": {}, "outputs": [], "source": [ "def int_MC(f, a, b, n, M):\n", " '''\n", " Input : f est une fonction reelle définie sur l’intervalle [a,b] a valeurs dans [0,M] avec M > 0, a < b sont deux reels, n est un naturel non nul.\n", " Output : renvoyer I_M, l’approximation numerique de int_a^b f dx par la methode de Monte-Carlo\n", " '''\n", " # A COMPLETER\n", " return I_MC" ] }, { "cell_type": "markdown", "id": "a15e1699", "metadata": {}, "source": [ "#### Question 3\n", "Afin de contrer l'effet aléatoire, on peut itérer plusieurs fois la méthode de Monte-Carlo et prendre la moyenne des valeurs obtenues. Complémeter l'implémentation suivante du calcul d'une telle moyenne." ] }, { "cell_type": "code", "execution_count": 7, "id": "c95693dc", "metadata": {}, "outputs": [], "source": [ "def moy_int_MC(f, a, b, n, M, N):\n", " '''\n", " Input : f est une fonction reelle définie sur l’intervalle [a,b] a valeurs dans [0,M] avec M > 0, a < b sont deux reels, n est un naturel non nul. Et N > 0 un entier donnant le nombre d'iteration de la methode de Monte-Carlo \n", " Output : renvoyer moy_I_M, la moyenne de N appels a la methode de Monte-Carlo. \n", " '''\n", " # A COMPLETER\n", " return moy_I_MC" ] }, { "cell_type": "markdown", "id": "89c07438", "metadata": {}, "source": [ "#### Question 4\n", "Appliquer la méthode de Monte-Carlo à la fonction $f(x) = \\frac{1}{x^2+1}$ sur $[0,1]$ pour une valeur de $M$ à choisir pour $n = 1,\\ldots,100$. Puis représenter graphiquement $\\sqrt{n} \\lvert E(f,n) \\rvert$ et $n \\lvert E(f,n) \\rvert$ pour ces valeurs. Qu’observe-t-on ?\n" ] }, { "cell_type": "markdown", "id": "42310868", "metadata": {}, "source": [ "#### Question 5\n", "Adapter la méthode de Monte-Carlo afin de calculer une approximation de l'aire d'un cercle de rayon 1. En déduire une méthode d'approximation de $\\pi$, et la comparer à la méthode donnée par la question 11 pour différentes valeurs de $n$." ] }, { "cell_type": "markdown", "id": "6fac9763", "metadata": {}, "source": [ "## III. Bonus : Méthodes d'interpolation\n" ] }, { "cell_type": "markdown", "id": "e3793eb4", "metadata": {}, "source": [ "L'idée derrière les méthodes d'interpolation est que si $f$ n'est pas très loin d'un polynôme $L$, alors l'intégrale de $f$ sur $[a,b]$ ne doit pas être très loin de l'intégrale de $L$ sur $[a,b]$. \n", "\n", "Elle se divise en deux étapes de préparation :\n", "1. On divise $[a,b]$ en $n+1$ valeurs $x_i = a + i\\frac{b-a}{n}$ comme précédemment.\n", "2. Sur chaque intervalle $[x_{i},x_{i+1}]$, on trouve un polynôme de degré $d$, dit polynôme d'interpolation, qui approxime $f$ sur cet intervalle. \n", "\n", "La méthode d'interpolation de degré $d$ est la méthode approximant $\\int_a^b f(x) \\, \\mathrm{d} x$ par \n", "$$\n", " I_d = \\frac{1}{n} \\sum_{i=0}^{n-1} \\int_{x_{i}}^{x_{i+1}} L_i(x) \\, \\mathrm{d} x\\text{.}\n", "$$\n", "\n", "On va expliquer dans cette partie comment trouver un tel polynôme $L_i$ par la méthode d'interpolation de Lagrange. " ] }, { "cell_type": "markdown", "id": "cf4861d7", "metadata": {}, "source": [ "#### Question 1\n", "Pour simplifier, on considère $a = 0$ et $b = 1$. \n", "Pour $j=0,\\dotsc,d$ on pose $x_{i,j} := x_i + j \\frac{x_{i+1} - x_{i}}{d}$, et on définit \n", "$$\n", " L_i(X) = \\sum_{j=0}^d f(x_{i,j}) \\prod_{k \\neq j} \\frac{X - x_{i,j}}{x_{i,k} - x_{i,j}}\\text{.}\n", "$$\n", "En simplifiant l'expression de $x_{i,j}$, montrer qu'on a\n", "$$\n", " L_i(X) = \\sum_{j=0}^d f(x_{i,j}) \\prod_{k \\neq j} \\frac{n d X - d i - j}{k - j}\\text{.}\n", "$$" ] }, { "cell_type": "markdown", "id": "6aa803bf", "metadata": {}, "source": [ "#### Question 2\n", "Montrer que pour tous $i$ et $j$, on a $L_i(x_{i,j}) = f(x_{i,j})$. En déduire que si $f$ est un polynôme de degré $d$, alors $L_i(x) = f(x)$.\n", "Conclure que la méthode est d'ordre au moins $d$. " ] }, { "cell_type": "markdown", "id": "84b9e316", "metadata": {}, "source": [ "#### Question 4\n", "Trouver $L_i$ lorsque $d = 1$. Calculer ensuite $\\int_{x_i}^{x_{i+1}} L_i(x)\\, \\mathrm{d} x$. En déduire que la méthode d'interpolation de degré $1$ est exactement la méthode des trapèzes. " ] }, { "cell_type": "markdown", "id": "a17c8811", "metadata": {}, "source": [ "#### Question 3\n", "Trouver une forme étendue de $L_i(X)$ pour $d = 2$ sous la forme $a_i X^2 + b_i X + c_i$ pour des coefficients $a_i,b_i,c_i$ à identifier. En déduire la valeur de $\\int_{x_i}^{x_{i+1}} L_i(x) \\, \\mathrm{d} x$. \n" ] }, { "cell_type": "markdown", "id": "1f5949ac", "metadata": {}, "source": [ "#### Question 4\n", "Compléter l'implémentation suivante de la méthode d'interpolation pour $d = 2$." ] }, { "cell_type": "code", "execution_count": 3, "id": "dfe8dc14", "metadata": {}, "outputs": [], "source": [ "def int_2(f,n):\n", " '''\n", " Input : f est une fonction reelle définie sur l’intervalle [0,1] et n est un naturel non nul.\n", " Output : renvoyer I_2, l'approximation numerique de int_0^1 f par la methode d'interpolation de degre 2\n", " '''\n", " # A COMPLETER\n", " return I_2" ] }, { "cell_type": "markdown", "id": "da400eb4", "metadata": {}, "source": [ "#### Question 5\n", "On considère $f(x) = x^3 + x^2 + x + 1$. Calculer $\\int_0^1 f(x) \\, \\mathrm{d} x$, puis, pour $n=1,\\dotsc,100$, tracer $n^2 \\lvert E(f,n) \\rvert$, $n^3 \\lvert E(f,n)\\rvert$ et $n^4 \\lvert E(f,n)\\rvert$ pour la méthode d'interpolation de degré $2$ ainsi que pour la méthode du point milieu. Qu'observez-vous ?" ] }, { "cell_type": "markdown", "id": "30fca173", "metadata": {}, "source": [ "#### Question 6\n", "On souhaite à présent implémenter une fonction qui calcule le polynôme interpolatoire de Lagrange de degré $ d $ d’une fonction $ f $.\n", "Pour fixer la notation, on considère $ f \\colon [a,b] \\to \\mathbb{R} $ ainsi que les points $ x_{j} = a + j\\frac{b-a}{d} $.\n", "Le polynôme interpolatoire de Lagrange de $ f $ de degré $ d $ est donné par\n", "$$\n", " L_{d}(X) = \\sum_{j=0}^{d}f(x_{j})\\prod_{k \\neq j} \\frac{X-x_{j}}{x_{k}-x_{j}}\\text{.}\n", "$$\n", "\n", "Le calcul du polynôme interpolatoire peut se faire de façon relativement efficace et précise à l’aide d’une implémentation récursive.\n", "Dans ce TP, on se limitera à une implémentation naïve, directement à l’aide de la formule ci-dessus.\n", "\n", "Compléter la fonction Lagrange ci-dessous pour calculer le polynôme interpolatoire de Lagrange d’une fonction donnée." ] }, { "cell_type": "code", "execution_count": null, "id": "d22ade50", "metadata": {}, "outputs": [], "source": [ "def Lagrange(f,a,b,d):\n", " '''\n", " Input : f est une fonction réelle définie sur [a,b], avec a < b deux réels, et d un entier representant le degre du polynome.\n", " Output : L_{d}, le polynome de Lagrange de degre d de f, qui devrait etre une fonction d'une variable reelle.\n", " '''\n", " # A COMPLETER\n", " return L" ] }, { "cell_type": "markdown", "id": "892bb62e", "metadata": {}, "source": [ "#### Question 7\n", "Utiliser la fonction Lagrange pour calculer le polynôme interpolatoire des fonctions définies ci-après sur $[-5,5]$, pour un degré $ d $ allant de $ 0 $ à $ 10 $.\n", "Représenter, pour chacun de ces fonctions, le graphe de la fonction ainsi que le graphe des polynômes interpolatoires associé.\n", "(On fera un graphique par fonction, et sur ce graphique, on représentera simultanément la fonction et tous les polynômes interpolatoires. On pourra sélectionner uniquement certains d’entre eux, particulièrement représentatifs, dans un souci de lisibilité.)\n", "Qu’observez-vous ?\n", "\n", "$$\n", " f(x) = x^{2} + x + 1\n", " \\quad\n", " g(x) = x^{5} + x^{3} + x\n", " \\quad\n", " h(x) = \\sin(x)\n", " \\quad\n", " i(x) = \\mathrm{e}^{x}\n", " \\quad\n", " j(x) = \\frac{1}{1+x^{2}}\n", "$$" ] }, { "cell_type": "markdown", "id": "33d91a78", "metadata": {}, "source": [ "#### Remarque \n", "On peut montrer que la méthode d'interpolation de degré $n$ est de complexité $d n$ en terme du nombre d'appel à la fonction $f$, et converge théoriquement à la vitesse $\\frac{1}{n^{d+2}}$ si $d$ impair, et $\\frac{1}{n^{d+3}}$ si $n$ pair. Au vu de la complexité linéaire et de la vitesse de convergence, on pourrait se demander pour ne pas toujours utiliser cette méthode pour $d$ très grand.\n", "Il se pose en fait un autre problème inhérent aux approximations numériques dans les différents calculs. Ce phénomène dit de Runge prouve qu'augmenter $d$ n'est pas une bonne stratégie dans de nombreux cas : https://fr.wikipedia.org/wiki/Phénomène_de_Runge.\n", "C'est un phénomène qui peut se produire assez souvent en approximation numérique : un algorithme qui semble théoriquement efficace peut ne pas l'être à cause d'une accumulation d'erreurs machine. " ] }, { "cell_type": "markdown", "id": "b6189322", "metadata": {}, "source": [ "#### Pour aller plus loin : courbes de Bézier et splines\n", "Comme nous l’avons observé, interpoler une fonction à l’aide d’un polynôme de haut degré est en général une assez mauvaise idée, en raison du risque de détérioration de la précision de l’approximation, notamment à cause du phénomène de Runge.\n", "D’un autre côté, on conçoit aisément qu’une fonction assez compliquée ne puisse pas être interpolée par un polynôme de bas degré (ainsi, que pensez-vous de la possibilité d’interpoler un sinus ou un cosinus par un polynôme de bas degré ?).\n", "\n", "Une manière de surmonter ce problème consiste, un peu dans l’esprit de ce que nous avons fait pour l’intégration, à découper l’intervalle sur lequel nous souhaitons interpoler en nombreux sous-intervalles de taille réduite, et à interpoler la fonction sur chacun de ces intervalles par un polynôme de bas degré.\n", "Une difficulté avec cette approche est que la fonction obtenue après le recollement n’est en général pas dérivable, mais seulement continue, ce qui n’est pas toujours un comportement souhaitable.\n", "(Si vous le souhaitez, vous pouvez essayer par vous-même sur les fonctions de la question 7 ci-haut.)\n", "\n", "Pour obtenir une fonction interpolatoire plus régulière, on peut se reposer sur d’autres méthodes d’interpolation, par exemple les splines ou les courbes de Bézier.\n", "Le principe de base reste identique : on découpe l’intervalle sur lequel on souhaite interpoler avec $ d+1 $ + points, et on construit un polynôme de degré $ d $ à partir de ces $ d+1 $ points de contrôle.\n", "Une différence importante est que, contrairement au polynôme de Lagrange, qui passe par tous les points de contrôle, les courbes de Bézier et splines passent seulement par les $ 2 $ points de contrôle aux extrémités, mais restent dans l’enveloppe convexe des $ d+1 $ points.\n", "Ceci limite grandement l’apparition d’un phénomène de Runge.\n", "Par ailleurs, ce procédé permet aisément de recoller les courbes pour que la courbe résultante soit au moins différentiable.\n", "\n", "Pour la petite histoire, les courbes de Bézier furent développées aux alentours des années 1960 par les ingénieurs français Paul de Casteljau (employé chez Citroën) et Pierre Bézier (employé chez Renault), bien que leur principe théorique fut connu depuis 1920.\n", "Elles connurent leur premier usage dans la modélisation des composants des châssis de voitures.\n", "De nos jours, elles sont également largement utilisées dans le graphisme numérique.\n", "Par exemple, il est fort probable que les lettres avec lesquelles ce texte est écrit soient encodées par des courbes de Bézier." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.10.12" } }, "nbformat": 4, "nbformat_minor": 5 }