{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# 1 Interpolation et approximation de données\n",
"\n",
"## 1.1 Position du problème"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Interpolation de données\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 degré $n=4$ tel que $\\Pi_n(t_j) = y_j, j =1,...,5$ avec \n",
"les données 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 le note $p=\\Pi_n$. 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 polynôme d'interpolation\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** Soient $$t_1=1, t_2=1.75, t_3=2.5, t_4=3.25, t_5=4$$ les points d'interpolation et $$f(t) = t \\sin(2\\pi t).$$ On cherche l'interpolant $\\Pi_n f$ de degré $n=4$\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)\n",
"\n",
"# The interpolation must occour at points t=1, 1.75, 2.5, 3.25, 4\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([0, 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",
"Il 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 meilleure solution.\n",
"\n",
"Nous cherchons les coefficients du polynôme $p(t) = a_0 + a_1 t + ... + a_n t^n$ qui satisfait les $(n+1)$ équations $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 polynôme d'interpolation de degré $n=4$ \n",
"des valeurs 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 fonctions `polyfit` et `polyval` de `numpy` font essentiellement la même chose 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 à interpoler, $n$ le degré du polynôme recherché\n",
" * outut : les coefficients du polynôme _dans l'ordre inverse_ de 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
}