{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "from matplotlib.pyplot import *\n",
    "from numpy import *\n",
    "#from scipy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Méthodes numériques \n",
    "\n",
    "## TP n° 1 - Interpolation polynomiale\n",
    "\n",
    "### Exercice 1\n",
    "\n",
    "1) On considère les abscisses $x = \\left[ -2, 0, 1, 2 \\right]$ et $y = \\left[ 4, 0, 0 ,4 \\right]$. Parmi les polynômes suivants, lequel est le polynôme d'interpolation aux points $x,y$ ?\n",
    "\n",
    "- $\\displaystyle p_1(x) = x^4 - \\frac{2}{3} x^3 - 3\\, x^2 + \\frac{8}{3} x$\n",
    "- $\\displaystyle p_2(x) = \\frac{4}{3}x^2 - \\frac{4}{3}$\n",
    "- $\\displaystyle p_3(x) = \\frac{1}{3}x^3 + x^2 - \\frac{4}{3} x$\n",
    "\n",
    "2) Représentez sur une même figure les points d'interpolation, ainsi que les polynômes $p_1$, $p_2$ et $p_3$ respectivement en noir, vert et rouge, sur l'intervalle $[-2.5, 2.5]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 2\n",
    "\n",
    " Pour $(x_0,\\ldots, x_n) \\in \\mathbb{R}^{n+1}$, on considère la matrice\n",
    "$$\n",
    " V(x_0,\\ldots,x_n) = \\left( \\begin{array}{ccccc} \n",
    "1 & x_0 & x_0^2 & \\ldots & x_0^n \\\\\n",
    "1 & x_1 & x_1^2 & \\ldots & x_1^n \\\\\n",
    "\\vdots & \\vdots & \\vdots & \\ldots & \\vdots \\\\\n",
    "\\vdots & \\vdots & \\vdots & \\ldots & \\vdots \\\\\n",
    "1 & x_n & x_n^2 & \\ldots  & x_n^n\n",
    "\\end{array} \\right).\n",
    "$$\n",
    "\n",
    "1) Écrire un programme `PolIntLag(Xint,Yint)` qui calcule les coefficients dans la base canonique de $\\mathbb{R}^n$\n",
    "du polynôme d'interpolation de Lagrange aux points $X_{int} = (x_0,\\ldots, x_n)$ et $Y_{int} = (y_0, \\ldots, y_n)$,\n",
    "en utilisant la matrice $V$.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) Écrire une fonction `EvalPol(x,Coef)` qui retourne la valeur prise par le polynôme $P(X) = Coef[0] + Coef[1] \\,X + Coef[2] \\, X^2 + \\ldots + Coef[n]\\, X^n$ au point réel $x$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 3 (Base de Lagrange)\n",
    "\n",
    "Soit $x_0,\\ldots, x_n$ (n+1) réels distincts deux à deux. Pour $k \\in \\left\\lbrace 0, \\ldots, n \\right\\rbrace$, on\n",
    "note \n",
    "$$\n",
    "L_k(X) = \\prod_{j \\in \\left\\lbrace 0, \\ldots , n \\right\\rbrace, j \\neq k} \\frac{X-x_j}{x_k-x_j}\n",
    "$$\n",
    "le $k$-ième polynôme de Lagrange.\n",
    "\n",
    "1) Écrire une fonction `PolLagrange(x,Xint,k)` qui calcule la valeur au réel $x$ prise par le $k$-ième polynôme de la base de Lagrange associé aux abscisses $X_{int} = (x_0, \\ldots , x_n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) Écrire une fonction `PolIntLag2(x,Xint,Yint)` qui calcule la valeur prise en $x$ par le polynôme d'interpolation de Lagrange aux abscisses $X_{int} = (x_0, \\ldots, x_n)$ et\n",
    "$Y_{int} = (y_0, \\ldots, y_n)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 4 (Base de Newton)\n",
    "\n",
    "1) Ecrire une fonction evalpolyNew(X,DD,x) qui évalue en x un polynôme écrit dans la base de Newton. X est la liste des abcisses et DD la liste des différences divisées correspondantes. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) Ecrire une fonction  diffdiv(X,DD,nx,nv) de mise à jour des différences divisées (DD) par ajout d'une nouvelle abscisse nx  et d'une nouvelle valeur d'interpolation nv. La fonction donnera la nouvelle liste des abscisses nX avec nx en première position suivi de la liste X (utiliser pour cela la commande somme de listes) et la nouvelle liste des différences divisées nDD relatives à nX. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3) Ecrire une fonction vtodiffdiv(X,Y) qui calcule les différences divisées DD relatives aux abscisses X et aux valeurs Y associées. On utilisera pour ça la fonction précédente diffdiv.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4) Ecrire une fonction diffdivg(X,DD,nx,nv) qui réalise la mise à jour d'un  polynôme d'interpolation écrit dans la base de Newton lorsqu'un nouveau point d'interpolation (nx, nv) est ajouté et un ancien point d'interpolation est supprimé (interpolation glissante). Le polynôme est donné par la liste X des abscisses et la  liste DD des différences divisées correspondantes. On supprime les derniers éléments des listes X et DD. \n",
    "La fonction diffdivg(X,DD,nx,nv) donne la nouvelle liste nX des abscisses constituée de nx complété par la liste X privée de sa dernière valeur ainsi que la nouvelle liste nDD des différences divisées relatives à nX. La fonction  diffdivg s'obtient facilement à partir de la fonction diffdiv en modifiant quelques instructions.    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 5 (Phénomène de Runge)\n",
    "\n",
    "On considère la fonction $ \\displaystyle f : x \\in \\mathbb{R} \\mapsto \\frac{1}{1+25\\, x^2}$.\n",
    "\n",
    "1) On choisit, pour interpoler la fonction $f$, $n$ abscisses equidistribuées sur $[-1,1]$. Tracer sur un même graphique, sur $[-1,1]$, la fonction $f$, les points d'interpolation et le polynôme d'interpolation correspondant, pour $n = 5$, $10$, $15$ et $20$. Que remarque-t-on ? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2) Même question, mais cette fois en choisissant $X_{int} = (x_0,\\ldots, x_n)$ avec $\\displaystyle x_i = \\cos\\left(\\pi\\frac{i}{n}\\right)$, $i = 0 , \\ldots, n$. Que remarque-t-on ? "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercice 6 (Interpolation par morceaux )\n",
    "\n",
    "On reprend la fonction $f$ de l'exercice précédent. On voit que si on ne choisit pas correctement les abscisses d'interpolation sur $[-1,1]$, des oscillations apparaissent (phénomène de Runge), et le polynôme d'interpolation ne converge pas vers la fonction $f$.\n",
    "\n",
    "Pour contrer cela, on se propose non plus de faire de l'interpolation polynomiale, mais de l'interpolation polynomiale par morceau, c'est-à-dire :\n",
    "\n",
    "  - on découpe l'intervalle $[-1,1]$ en $N$ sous-intervalles de même longueur\n",
    "  - sur chaque sous-intervalle, on interpole la fonction $f$ en utilisant $n$ abscisses équidistribuées\n",
    "  \n",
    "Écrire un programme dessinant la fonction $f$ et son interpolé par morceaux. Le tester pour différentes valeurs de $N$ et $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
