interpol.tex

   1 Soit $f: I \to \R$ une fonction connue seulement en  $n+1$
   2 points $x_0$, $x_1$, \ldots, $x_n$,
   3 tous dans $I$. Ce sont par exemples les points
   4 en lesquels la fonction $f$ a pu être évaluée.
   5 Peut-on déterminer un polynôme $p$ de degré au plus égal à $n$ prenant les
   6 mêmes valeurs que la fonction $f$ en $x_0$, $x_1$, \ldots, $x_n$.
   7 Si un tel polynôme $p$ existe, on dit alors que $p$ interpole $f$ aux points
   8 (au n{\oe}uds) $x_0$, $x_1$, \ldots, $x_n$.
   9
  10 \section{Formalisation du problème}
  11 \begin{Def}[Interpolation]
  12   On dit qu'un polynôme $p$ de degré $n$ interpole $f$ aux points
  13   $x_0$, $x_1$, \ldots, $x_n$ si pour tout $i$, $0 \le i \le n$, on a
  14   $p(x_i) = f(x_i)$.
  15 \end{Def}
  16
  17
  18
  19 \begin{Prop}[Unicité du polynome d'interpolation]
  20 Si $p$ de degré inférieur ou égal à $n$ interpole $f$ en
  21 $x_0$, $x_1$, \ldots, $x_n$, alors $p$ est unique.
  22 \end{Prop}
  23
  24 \begin{Def}[Base de Lagrange]
  25   On appelle base de Lagrange associée au support
  26   $\{x_0, x_1, \ldots, x_n\}$ l'ensemble des polynômes $l_i$,
  27   $0 \le i \le n $ définis par
  28   $$
  29   l_i = \prod_{
  30     \begin{scriptsize}
  31     \begin{array}{ll}
  32         j = 0 \\
  33       j \neq i
  34     \end{array}
  35   \end{scriptsize}
  36 }^n
  37 \dfrac{x - x_j}{x_i - x_j}
  38   $$
  39 \end{Def}
  40
  41 \begin{Prop}[Existence du polynome d'interpolation]
  42   Le polynôme $p$ défini par
  43   $p(x) = \sum_{i=0}^n f(x_i)l_i(x)$, où les $l_i$ forment la base de Lagrange,
  44   interpole $f$
  45   en $x_0$, $x_1$, \ldots, $x_n$.
  46   On parle d'\emph{interpolation de Lagrange} dans ce cas.
  47 \end{Prop}
  48
  49 \begin{Exo}
  50 Montrer les résultats suivants:
  51 \begin{enumerate}
  52 \item Le polynôme de degré 0 qui interpole $f$ en $x_0$ est donné par
  53   $p(x) = f(x_0)$.
  54 \item Soit $x_0$ et $x_1$ deux réels distincts.
  55   Le polynôme de degré inférieur 1 qui interpole $f$ en $x_0$ et $x_1$
  56   est donné par  $p(x) = f(x_0) + \frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0)$.
  57 \end{enumerate}
  58 \end{Exo}
  59
  60 \section{Détermination efficace du polynôme d'interpolation}
  61 On peut écrire le polynôme $p$ qui interpole $f$
  62 en $x_0$, $x_1$, \ldots, $x_n$ sous sa forme \og de Newton \fg{}
  63 $$
  64 p(x) = \sum_{i=0}^n d_i \left[  \prod_{j=0}^{i-1} (x - x_j)\right],
  65 $$
  66 où les $d_i$ sont à déterminer.
  67
  68 On peut alors démontrer le résultat suivant.
  69
  70 \begin{Prop}[Construction iterrative selon la forme de Newton]
  71 Pour tout $k \in \{1, \ldots, n\}$, on a:
  72 $$p_i(x) = p_{i-1}(x) + d_i  \left[  \prod_{j=0}^{i-1} (x - x_j)\right].$$
  73 \end{Prop}
  74
  75 Ainsi pour obtenir $p$ sur $x_0$, $x_1$, \ldots, $x_n$, il suffit:
  76 \begin{itemize}
  77 \item de calculer $d_0$, pour définir $p_0$ qui interpole $f$ sur $x_0$,
  78 \item de calculer $d_1$, pour définir $p_1$  qui interpole $f$ sur $x_0$
  79   et $x_1$,
  80 \item \ldots
  81 \item de calculer $d_n$, pour définir $p_n$  qui interpole $f$ sur
  82   $x_0$, $x_1$, \ldots, $x_n$.
  83 \end{itemize}
  84
  85 Le coefficient $d_i$ est le coefficient dominant de $p_i$: il dépend
  86 de $f$ et de $x_0$, $x_1$, \ldots, $x_i$. On appelle ce nombre la
  87 \og différence divisée\fg{} et on le note $d_i = f[x_0, \ldots,x_i]$.
  88 On admettra la méthode suivante pour calculer la table des différences
  89 divisées.
  90
  91
  92 \begin{Prop}[Calcul des différences divisées]
  93 On a:
  94 \begin{enumerate}
  95 \item $f[x_i] = f(x_i)$ pour tout $i \in \{0, \ldots, n\}$;
  96 \item $f[x_i,x_{i+1}, \ldots, x_{i+j}] =
  97   \dfrac{f[x_{i+1}, \ldots, x_{i+j}]- f[x_i,x_{i+1}, \ldots, x_{i+j-1}]}{x_{i+j}-x_{i}}$
  98 \end{enumerate}
  99 Ainsi on obtient:
 100 $$
 101 \begin{array}{llllll}
 102 x_0 & \bf{f[x_0]} & \bf{f[x_0,x_1]} & \bf{f[x_0,x_1,x_2]} & \ldots &
 103 \bf{f[x_0,x_1,x_2,x_3\ldots,x_n]}\\
 104 x_1 & f[x_1]      & f[x_1,x_2]         &  \ldots & f[x_1,x_2,x_3,\ldots,x_n] \\
 105 \ldots \\
 106 x_{n-1} & f[x_{n-1}] & f[x_{n-1},x_n]\\
 107 x_n & f[x_n]
 108 \end{array}
 109 $$
 110 \end{Prop}
 111
 112
 113 Les coefficients sur la première ligne fournissent les coefficients
 114 de la forme de Newton de $p_n$ relative aux centres
 115 $x_0$, \ldots $x_{n}$:
 116 $p_n(x) =
 117 f[x_0] + f[x_0,x_1](x-x_0) +  f[x_0,x_1,x_2](x-x_0)(x-x_1) + \ldots
 118 + f[x_0,\ldots,x_n](x-x_0)(x-x_1)\ldots(x-x_{n-1})
 119 $
 120
 121 \begin{Exo}
 122 On donne trois valeurs d'une fonction $f$ définie sur $[1,6]$:
 123 $f(1) = 1,5709$,
 124 $f(4) = 1,5727$ et
 125 $f(6) = 1,5751$.
 126 \begin{enumerate}
 127 \item En utilisant les polynômes de Lagrange relatifs au support $\{1,4\}$,
 128 fournir une valeur approchée de $f(3,5)$ grâce au polynôme d'interpolation
 129 de $f$ de degré un.
 130 \item En utilisant les polynômes de Lagrange relatifs au support $\{1,4,6\}$,
 131 fournir une valeur approchée de $f(3,5)$ grâce au polynôme d'interpolation
 132 de $f$ de degré deux.
 133 \item Traiter de nouveau ces deux questions en utilisant une forme de Newton.
 134 \item Comparer ces deux méthodes et conclure.
 135 \end{enumerate}
 136 \end{Exo}
 137
 138
 139
 140 \begin{TP}[Première interpolation]
 141 \begin{enumerate}
 142 \item Construire l'algorithme qui:
 143 \begin{itemize}
 144 \item prend en entrée $x_0, \ldots,x_n$ et $f(x_0), \ldots, f(x_n)$;
 145 \item retourne la matrice \verb+diff_div+ de taille $(n+1)\times(n+1)$ telle
 146 que \verb+diff_div[i][j]+$=f[x_i, \ldots,x_{i+j}]$ pour
 147 $i\in\{0,\ldots,n\}$ et $j\in \{0, \ldots, n-i\}$ comme définie
 148 dans la proposition précédente.
 149 \end{itemize}
 150 \item Dans le cadre d'un processus industriel, on a noté le temps d'exécution
 151 $T(n)$ d'un algorithme sur des données de taille $n$ dans le tableau suivant:
 152 $$
 153 \begin{array}{|l||l|l|l|}
 154 \hline
 155 n & 10 & 25 & 60 \\
 156 \hline
 157 T(n) & 2,3 & 8,0 & 24,6 \\
 158 \hline
 159 \end{array}
 160 $$
 161 \begin{enumerate}
 162 \item Déterminer le polynôme $p$ d'interpolation de $T$ sur le support
 163 $\{10,25,60\}$ en utilisant la méthode développée à la première partie.
 164 \item En déduire le temps $T(n)$ pour un traitement de données de
 165 taille $n$, avec $n \in \{15,40,100\}$.
 166 \item Représenter le tracé de $p$.
 167 \end{enumerate}
 168 \end{enumerate}
 169 \end{TP}
 170
 171 \begin{TP}[Choix du support]
 172 L'objectif du TP est de montrer que des points régulièrement répartis sur
 173 un support contraint peu le polynôme sur les bords de celui-ci.
 174 Ainsi l'approximation peu s'en trouver dégradée sur les bords.
 175
 176 On se place sur $[a,b]= [-1,1]$ et on considère deux
 177 interpolations de $f(x)=e^x$ correspondant à deux choix de supports.
 178 \begin{enumerate}
 179 \item Premier choix: Pour tout $i \in \{0,\ldots,8\}$, on construit
 180   $x_i = -1 + 0,25i$.
 181 \begin{enumerate}
 182 \item Déterminer le polynôme $p_1$ d'interpolation de $f$ sur
 183   $\{x_0,\ldots,x_8\}$ à l'aide de la méthode développée au TP précédent.
 184 \item Représenter $p_1$ en faisant apparaître les points d'abscisse $x_0$,\ldots,
 185 $x_8$.
 186 \item Représenter la fonction $e_1(x) = | f(x)-p_1(x) |$  pour tout $x\in[-1,1]$.
 187 \end{enumerate}
 188 \item Second choix: Pour tout $i \in \{0,\ldots,8\}$, on construit
 189   $t_i = \cos(\frac{\pi}{2}\frac{2i+1}{9})$.
 190 \begin{enumerate}
 191 \item Déterminer le polynôme $p_2$ d'interpolation de $f$ sur
 192   $\{t_0,\ldots,t_8\}$ à l'aide de la méthode développée au TP précédent.
 193 \item Représenter $p_2$ en faisant apparaître les points d'abscisse
 194   $t_0$,\ldots, $t_8$.
 195 \item Représenter la fonction $e_2(x) = | f(x)-p_2(x) |$  pour tout $x\in[-1,1]$.
 196 \end{enumerate}
 197 \item Conclure
 198 \end{enumerate}
 199 \end{TP}