{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 1 Interpolation et approximation de donnés\n",
"\n",
"## 1.1 Position du problème"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Interpolation de donnée\n",
"\n",
"Soit $n \\geq 0$ un nombre entier. Etant donnés $n+1$ noeuds \n",
"distincts $t_0$, $t_1$,$\\dots$ $t_n$ et $n+1$ valeurs $y_0$,\n",
"$y_1$,$\\dots$ $y_n$, on cherche un polynôme $p$\n",
" de degré $n$, tel que\n",
"\n",
"$$p(t_j)=y_j \\qquad \\text{ pour } \\, 0\\leq j\\leq n.$$\n",
"\n",
"**Exemple** On cherche le polynôme $\\Pi_n$ de dégrée $n=4$ tel que $\\Pi_n(t_j) = y_j, j =1,...,5$ avec \n",
"les donnée suivantes \n",
"\n",
"| $t_k$ | $y_k$ |\n",
"| --- | --- |\n",
"| 1 | 3 |\n",
"| 1.5 | 4 |\n",
"| 2 | 2 |\n",
"| 2.5 | 5 |\n",
"| 3 | 1 |\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"slideshow": {
"slide_type": "slide"
}
},
"outputs": [],
"source": [
"# importing libraries used in this book\n",
"import numpy as np\n",
"import matplotlib.pyplot as plt"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"\n",
"# Some data given: t=1, 1.5, 2, 2.5, 3 and y = 3,4,2,5,1 \n",
"t = np.linspace(1, 3, 5) # equivalent to np.array([ 1, 1.5, 2, 2.5, 3 ])\n",
"y = np.array([3, 4, 2, 5, 1])\n",
"\n",
"# Plot the points using matplotlib\n",
"plt.plot(t, y, 'ro')\n",
"\n",
"plt.xlabel('t'); plt.ylabel('y'); #plt.title('data')\n",
"plt.legend(['data'])\n",
"plt.show()\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Si ce polynôme existe, on note $p=\\Pi_n$ et on appelle $\\Pi_n$ le\n",
"polynôme d'interpolation des valeurs $y_j$ aux noeuds $t_j,\\, j=0,\\dots,n$."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Plot the interpolating function\n",
"\n",
"# Defining the polynomial function \n",
"def p(t):\n",
" # coefficients of the interpolating polynomial\n",
" a = np.array([-140.0, 343.0, -872./3., 104.0, -40./3.])\n",
" \n",
" # value of the polynomial in all the points t\n",
" return a[0] + a[1]*t + a[2]*(t**2) + a[3]*(t**3) + a[4]*(t**4)\n",
"\n",
"\n",
"# points used to plot the graph \n",
"z = np.linspace(1, 3, 100)\n",
"\n",
"plt.plot(t, y, 'ro', z, p(z))\n",
"plt.xlabel('t'); plt.ylabel('y'); #plt.title('data')\n",
"plt.legend(['data','$\\Pi_2(t)$'])\n",
"plt.show()\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Interpolation de fonctions\n",
"\n",
"\n",
"Soit $f\\in C^0(I)$ et $t_0,\\ldots,t_n\\in I$. \n",
"Si on prend $$y_j=f(t_j),\\quad 0\\leq j\\leq n,$$ \n",
"alors le polynome d'interpôlation\n",
"$\\Pi_n(t)$ est noté $\\Pi_n f(t)$ et est appelé l'interpolant de $f$ aux\n",
"noeuds $t_0$,$\\dots$ $t_n$.\n",
"\n",
"**Exemple** Donné les points d'interpolation $$t_1=1, t_2=1.75, t_3=2.5, t_4=3.25, t_5=4$$ et $$f(t) = t \\sin(2\\pi t)$$ on cherche le polynome $\\Pi_n$ de dégrée $n=4$ tel que $\\Pi_n(t_j) = f(t_j), j =1,...,5$\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# defining the fonction that we want to interpolate\n",
"def f(t):\n",
" return t*np.sin(t*2.*np.pi)+2\n",
"\n",
"# The interpolation must occour at points t=1, 1.5, 2, 2.5, 3\n",
"t = np.linspace(1, 4, 5)\n",
"\n",
"# points used to plot the graph \n",
"z = np.linspace(1, 4, 100)\n",
"\n",
"# (Complete the code below)\n",
"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Plot the interpolating function\n",
"\n",
"# Defining the polynomial function \n",
"def p(t):\n",
" # coefficients of the interpolating polynomial\n",
" a = np.array([2, 7.9012, -13.037, 5.9259, -0.79012])\n",
" \n",
" # value of the polynomial in all the points t\n",
" return a[0] + a[1]*t + a[2]*(t**2) + a[3]*(t**3) + a[4]*(t**4)\n",
"\n",
"\n",
"# points where to evaluate the polynomial\n",
"z = np.linspace(1, 4, 100)\n",
"\n",
"# (Complete the code below)\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Une méthode naïve\n",
"\n",
"C'est possible d'écrire un système d'équations et de trouver les coefficients de manière directe.\n",
"Comme expliqué dans le MOOC, ce n'est pas toujours la meilleures solution.\n",
"\n",
"Nous cherchons les coefficients du polinôme $p(t) = a_0 + a_1 t + ... + a_n t^n$ qui satisfait les $n+1$ equations $p(t_k) = y_k, k=0,...,n$, c'est à dire\n",
"\n",
"$$a_0 + a_1 t_k + ... + a_n t_k^n = y_k, k=0,...,n$$\n",
"\n",
"Ce système s'écrit sous forme matricielle\n",
"\n",
"$$\\begin{pmatrix}\n",
"1 & t_0 & t_0^2 & \\cdots & t_0^n \\\\\n",
"\\vdots & & & & \\vdots \\\\\n",
"1 & t_n & t_n^2 & \\cdots & t_n^n\n",
"\\end{pmatrix}\n",
"\\begin{pmatrix} a_0 \\\\ \\vdots \\\\ a_n \\end{pmatrix}\n",
"=\\begin{pmatrix} y_0 \\\\ \\vdots \\\\ y_n \\end{pmatrix}$$\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"**Exemple** On cherche les coefficients du polynome $\\Pi_n$ de dégrée $n=4$ tel que $\\Pi_n(t_j) = y_j, j =1,...,5$ avec \n",
"les donnée suivantes \n",
"\n",
"| t_k | y_k |\n",
"| --- | --- |\n",
"| 1 | 3 |\n",
"| 1.5 | 4 |\n",
"| 2 | 2 |\n",
"| 2.5 | 5 |\n",
"| 3 | 1 |\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Some data given: t=1, 1.5, 2, 2.5, 3 and y = 3,4,2,5,1 \n",
"t = np.linspace(1, 3, 5)\n",
"y = np.array([3, 4, 2, 5, 1])\n",
"n = t.size - 1\n",
"\n",
"# The following is a trick to put toghether the matrix A. Don't need to learn by heart ...\n",
"# np.tile(t, (n+1, 1)) : repete n+1 times of the array t \n",
"# .T : transpose\n",
"# np.linspace(0,n,n+1) : [0,...,n+1]\n",
"# np.tile : again: repete n+1 times the array [0,...,n+1]\n",
"# np.power : element by element power funcion\n",
"A = np.power( np.tile(t, (n+1, 1)).T , np.tile(np.linspace(0,n,n+1), (n+1, 1)))\n",
"# print(A)\n",
"\n",
"# (Complete the code below)\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Now we can define the polynomial\n",
"p = lambda t : a[0] + a[1]*t + a[2]*(t**2) + a[3]*(t**3) + a[4]*(t**4)\n",
"\n",
"# points used to plot the graph \n",
"z = np.linspace(1, 3, 100)\n",
"\n",
"# (Complete the code below)\n",
"\n",
"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Alternatives : polyfit et polyval\n",
"\n",
"Les functions `polyfit` et `polyval` de `numpy` font essentiellement la même choses que les paragraphes ci dessous. Plus tard nous verrons des méthodes plus performantes.\n",
"\n",
"`a = numpy.polyfit(t, y, n, ... )` :\n",
"\n",
" * input : $t,y$ les données, $n$ le degrée du polynôme\n",
" * outut : $a$ qui contient les coefficients du polynome _dans l'ordre inverse_ à ce que nous avons vu !\n",
" "
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"# Some data given: t=1, 1.5, 2, 2.5, 3 and y = 3,4,2,5,1 \n",
"t = np.linspace(1, 3, 5)\n",
"y = np.array([3, 4, 2, 5, 1])\n",
"n = t.size - 1\n",
"\n",
"a = np.polyfit(t,y,n)\n",
"\n",
"# Now we can define the polynomial, with coeffs in the reverse order !\n",
"p = lambda t : a[4] + a[3]*t + a[2]*(t**2) + a[1]*(t**3) + a[0]*(t**4)\n",
"\n",
"# We can also use polyval instead !\n",
"# np.polyval(a,t)\n",
"\n",
"# points used to plot the graph \n",
"z = np.linspace(1, 3, 100)\n",
"\n",
"plt.plot(t, y, 'ro', z, p(z), '.', z, np.polyval(a,z))\n",
"plt.xlabel('t'); plt.ylabel('y'); #plt.title('data')\n",
"plt.legend(['data','p(t)','polyval'])\n",
"plt.show()\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"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.7.6"
}
},
"nbformat": 4,
"nbformat_minor": 4
}