{ "cells": [ { "cell_type": "markdown", "id": "ef674ab4-d343-474a-9b6e-a3888c353796", "metadata": {}, "source": [ "## MT09 - TP6 - Automne 2024\n", "## Interpolation polynomiale\n" ] }, { "cell_type": "markdown", "id": "f2e7f71c-6313-4917-a489-9cea671cfcc7", "metadata": { "tags": [] }, "source": [ "#### 1. Algorithme de Horner de calcul des polynômes\n", "Ecrire une fonction\n", "```\n", "p = horn(a, t, theta)\n", "```\n", "qui, étant donné le tableau $a$ de coefficients $(a_0, a_1, ...,a_n)$, le tableau $t$\n", "de valeurs $(t_0,t_1,...,t_{n-1})$ et le point courant $\\theta$, calcule\n", "\n", "$$\n", "P(\\theta) = a_0 + a_1(\\theta-t_0)\n", "+a_2(\\theta-t_0)(\\theta-t_1)\n", "+...+ a_n (\\theta-t_0)(\\theta-t_1)...(\\theta-t_{n-1})\n", "$$\n", "\n", "à l'aide de l'algorithme de Horner vu en cours (attention : appliqué ici à la base de Newton)." ] }, { "cell_type": "code", "execution_count": null, "id": "c7cd03d2-5a55-4f48-acf6-7b68281d11c0", "metadata": { "tags": [] }, "outputs": [], "source": [ "def horn(a, t, theta):\n", " # Algo : \n", " # p = a_n\n", " # pour k= n-1 à 0 par pas de -1 faire:\n", " # p = a_k + (t-t_k)*p\n", " # fin pour\n", " # \n", " #" ] }, { "cell_type": "markdown", "id": "1ecd2cd7-4b7b-4f9f-9673-685a5d8d85e2", "metadata": {}, "source": [ "Vérification. - Appliquez l'algorithme au calcul du polynôme $p(x) = -1+2x-x^2+x^3$ et vérifiez que vous obtenez les bonnes valeurs de $p$ en $x=0$, $x=1$ et $x=2$." ] }, { "cell_type": "code", "execution_count": null, "id": "7db1ce79-55e3-4dd5-85b6-6b8287674928", "metadata": { "tags": [] }, "outputs": [], "source": [ "import numpy as np\n", "t = np.zeros(3)\n", "a = np.array([-1, 2, -1, 1])\n", "x=0; px = horn(a, t, x); print(px)\n", "# ..." ] }, { "cell_type": "markdown", "id": "ed96cd06-4950-4810-a0c7-75279d2ccb08", "metadata": { "tags": [] }, "source": [ "### 2. Polynômes d'interpolation, forme de Newton\n", "#### Différences divisées\n", "Ecrire une fonction\n", "```\n", "d = diffdiv(y, t)\n", "```\n", "qui, étant donné le tableau $t=(t_0, t_1, .. t_{n})$, le tableau\n", "$y=(y_0,...,y_n)$ avec\n", "$y_0=f(t_0), \\ y_1=f(t_1), ..., y_{n}=f(t_{n})$, calcule les différences divisées $f_0=f[t_0]$, $f_1=f[t_0,t_1]$, ..., $f_{n} = f[t_0, ..., t_n]$\n", "(on suppose que les $t_i$ sont distincts deux à deux)." ] }, { "cell_type": "code", "execution_count": null, "id": "2af5cf8a-1729-4aa1-91d4-f40219b80ab8", "metadata": { "tags": [] }, "outputs": [], "source": [ "def diffdiv(y,t):\n", " n = y.size - 1\n", " # Algorithme : voir polycopié\n", " # Init\n", " # d = y\n", " # boucle pour k de 1 à n\n", " # boucle pour i de n à (k-1) par pas de (-1)\n", " # d_i = (d_i - d_{i-1)} / (t_i - t_{i-k}}\n", " # fin pour\n", " # fin pour\n", " #" ] }, { "cell_type": "markdown", "id": "aacdf36a-e3e8-40b9-ae4c-e722b4b015a4", "metadata": {}, "source": [ "Application numérique et vérification : considérer\n", "$t=(1,\\ 3,\\ 4.5,\\ 5,\\ 6)$ et $y=(1,\\ 5,\\ 3,\\ 7,\\ -1)$.\n", "Vous devez obtenir : \n", "\n", "`\n", "d = [ 1. 2. -0.95238095 1.4047619 -1.3031746 ]\n", "`" ] }, { "cell_type": "code", "execution_count": null, "id": "314b4d91-82c8-46ac-a420-c47af5835430", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "3e72642c-57e4-4ccf-85a7-40cfa465c866", "metadata": { "tags": [] }, "source": [ "#### Interpolation polynomiale\n", "En utilisant ```diffdiv()``` et ```horn()```, écrire une fonction\n", "```\n", "p = interpol(y, t, theta)\n", "```\n", "qui, étant donné $(y_0, y_1, ..., y_n)$, $(t_0, t_1, ..., t_n)$,\n", "$\\theta$ réels, calcule $p=P(\\theta)$ où $P$ est le polynôme de degré inférieur ou égal à $n$ tel que $P(t_i)=y_i$. " ] }, { "cell_type": "markdown", "id": "f264a8e4-23d3-4161-92a5-2fbe56872798", "metadata": {}, "source": [ "Application numérique : considérer $t=(1, \\ 3, \\ 4.5, \\ 5, \\ 6)$, $y=(1, \\ 5, \\ 3, \\ 7, \\ -1)$. Calculer $p$ dans le cas $\\theta=3$ puis\n", "$\\theta=4$." ] }, { "cell_type": "code", "execution_count": null, "id": "f06a963a-cf76-4c70-b353-538470415f35", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "f09384e8-cde5-4968-bd8c-b48897080db3", "metadata": { "tags": [] }, "source": [ "#### Tracé du polynôme d'interpolation\n", "En considérant le tableau de valeurs de $\\theta$\n", "```\n", "theta = np.linspace(1, 6, 200)\n", "```\n", "dans un graphique, tracez le polynôme d'interpolation $p$ pour les tableaux $t$ et $y$ ci-dessus. Sur le même graphique, affichez d'une autre couleur les points d'interpolationn $(t_i, y_i)$ ainsi que la fonction $f$ en ligne continue." ] }, { "cell_type": "code", "execution_count": null, "id": "f78b3bcb-72bc-4cae-9818-7dc9736ca1c7", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "a9acf430-dc23-4ad6-929f-6f8a6642b854", "metadata": { "tags": [] }, "source": [ "#### Phénomène de Runge\n", "On considère maintenant la fonction \n", "\n", "$$\n", "f(x) = \\frac{1}{1+x^2}\n", "$$\n", "\n", "sur l'intervalle $[-5, 5]$. Considérez les tableaux de $t$, $y$ et $\\theta$ définis par\n", "\n", "```\n", "t = np.linspace(-5, 5, N)\n", "y = f(t)\n", "theta = np.linspace(-5, 5, 200)\n", "```\n", "\n", "pour les valeurs de $N$ respectives : $N=5,\\ 7,\\ 10, 12, 13, 24$. Est-ce satisfaisant ?\n", "\n", "ps : le phénomène observé se nomme le phénomène de Runge." ] }, { "cell_type": "code", "execution_count": null, "id": "8090d816-ffe2-452e-bf27-457214b356e7", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "id": "d065861f-8ab1-419e-93d8-8e3b052665c6", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "c5e7182e-6aab-4d2f-bbb1-b69e525bc088", "metadata": { "tags": [] }, "source": [ "#### Points de Tchebychev\n", "Refaire la même tâche mais en considérant cette fois-ci les points d'interpolation donnés par le tableau `tcheb` (points de Tchebychev) :\n", "\n", "```\n", "tcheb = np.cos( np.linspace(np.pi/(2*N) , (2*N-1)*np.pi/(2*N), N) ) # dans [-1, 1]\n", "t = 5 * tcheb # dans [-5, 5]\n", "y = f(t)\n", "theta = np.linspace(-5, 5, 200)\n", "```" ] }, { "cell_type": "code", "execution_count": null, "id": "1337dd31-d4d3-46da-8bf4-b28ee8df6a76", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "7db2c28d-0b9f-4023-a4c0-b9d5e9138a63", "metadata": {}, "source": [ "### 3. Polynômes de Hermite\n", "\n", "Sur le même graphique, tracer les 4 polynômes suivants sur l'intervalle $[0,1]$ (vus en TD) :\n", "\n", "\\begin{align*}\n", "& p_1(x) = (1-x)^2(2x+1), \\\\\n", "& p_2(x) = x^2(3-2x), \\\\\n", "& p_3(x) = x(1-x)^2, \\\\\n", "& p_4(x) = -(1-x)x^2.\n", "\\end{align*}\n", "\n", "Quelles sont les propriétés de $p_1$, $p_2$, $p_3$, $p_4$ ?" ] }, { "cell_type": "code", "execution_count": null, "id": "337951ff-e9c5-4fc8-baaf-405d9bf742db", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "1a13139e-09bc-4196-b547-c4f034e66b97", "metadata": {}, "source": [ "À partir de $(p_1,p_2,p_3,p_4)$, construire le polynôme d'interpolation $p$ de degré inférieur ou égal à 3 tel que\n", "\n", "$$\n", "p(0) = y_0, \\quad p'(0) = d_0, \\quad p(1) = y_1, \\quad p'(1)= d_1.\n", "$$\n", "Application : on prendra les valeurs $y_0 = 3$, $d_0 = 0$, $y_1 = 2$, $d_1=1$." ] }, { "cell_type": "code", "execution_count": null, "id": "90623c89-3794-4680-abf8-f6a6f997657d", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "990b1808-3925-4c28-b547-592da9561708", "metadata": {}, "source": [ "Dans une fonction python, définir une fonction $q$ polynomiale de degré 3 par morceaux telle que\n", "* $q(x) = p_1(x)$ sur l'intervalle $[0,1]$\n", "* $q(x) = p_2(x+1)$ sur l'intervalle $[-1,0]$\n", "* $q(x) = 0$ ailleurs\n", "\n", "Tracer $q$ sur l'intervalle $[-2,2]$. Quelles sont les propriétés de $q$ autres que les conditions données ?" ] }, { "cell_type": "code", "execution_count": null, "id": "2ac9bf2f-09f6-49f8-8c9b-5a28f1ea89d4", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "49d95f17-da70-4d0f-b611-65eb5668d98d", "metadata": {}, "source": [ "Dans une fonction python, définir une fonction $r$ polynomiale de degré 3 par morceaux telle que\n", "* $r(x) = p_3(x)$ sur l'intervalle $[0,1]$\n", "* $r(x) = p_4(x+1)$ sur l'intervalle $[-1,0]$\n", "* $r(x) = 0$ ailleurs\n", "\n", "Tracer $r$ sur l'intervalle $[-2,2]$. Quelles sont les propriétés de $r$ autres que les conditions données ?" ] }, { "cell_type": "code", "execution_count": null, "id": "795379e2-6acd-4c4b-ab63-3216c780fe86", "metadata": { "tags": [] }, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "ffdab76d-260e-42c4-814c-32ff52cb1c1b", "metadata": {}, "source": [ "À partir de $q$ et $r$, on va pouvoir définir une fonction d'interpolation polynomiale par morceaux (mais non globalement polynomiale). On considère le tableau de points d'interpolation\n", "\n", "$$\n", "t = [-5, -4, ..., 0, ..., 4, 5]\n", "$$\n", "\n", "et la fonction $s(\\theta)$ définie par\n", "\n", "$$\n", "s(\\theta) = \\sum_{i=0}^N \\left\\{ f(t_i)\\, q(\\theta-t_i)\n", "+ f'(t_i)\\, r(\\theta-t_i) \\right\\}\n", "$$\n", "\n", "Définir d'abord une fonction ```fprim(t)``` qui calcule la dérivée de $f$ en $x$.\n", "Définir ensuite une fonction ```interpol(y, z, t, theta)``` qui calcule $s(\\theta)$\n", "étant donné les tableaux $t$ (```t = np.arange(-5.0, 6.0, 1.0)```) et\n", "\n", "$$\n", "y=(f(t_0), f(t_1), ... , f(t_N)),\\qquad \n", "z=(f'(t_0), f'(t_1), ... , f'(t_N)). \n", "$$\n", "\n", "Tracer enfin la fonction $s$ sur l'intervalle $[-5,5]$ et comparer à la fonction $f$." ] }, { "cell_type": "code", "execution_count": null, "id": "ca1e4379-bd07-40be-ad3b-1ec1ba115cda", "metadata": { "tags": [] }, "outputs": [], "source": [] } ], "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.11.5" } }, "nbformat": 4, "nbformat_minor": 5 }