| 1 |
\begin{encadre}{Objectif du chapitre} |
| 2 |
Le monde théorique des mathématiques aiment manipuler des fonctions continues. Le monde réel de l'ingénierie est fait de prise de mesure à différents moments. On obtient ainsi des echantillons de données. Ce chapitre montre des méthodes qui permettent de retrouver un des fonctions continues à partir de points de mesure. |
| 3 |
\end{encadre} |
| 4 |
\\[1cm] |
| 5 |
\begin{encadre}{Connaissances antérieures nécessaires} |
| 6 |
\begin{itemize} |
| 7 |
\item les mathématiques : les polynomes. |
| 8 |
\item programmation de base en Basic ou C : les types, les opérations élémentaires et la structuration de programme en mode console. Excel pour afficher les résultats |
| 9 |
\end{itemize} |
| 10 |
|
| 11 |
\end{encadre} |
| 12 |
|
| 13 |
|
| 14 |
|
| 15 |
\section{Mise en situation} |
| 16 |
Lors d'un essai, la vitesse d'un véhicule est relevée toutes les 5 secondes pour obtenir le tableau de relevés suivant : \\ |
| 17 |
\\ |
| 18 |
\begin{tabular}{|r|r r r r r r r r r r|} |
| 19 |
\hline |
| 20 |
t(s) & 0 & 5 & 10 &15 & 20 & 25 & 30 & 35 & 40 & 45\\ |
| 21 |
v(km/h) & 55 &60 &58 & 54& 55 &60 &54 &57 &52 &49 \\ |
| 22 |
\hline |
| 23 |
\end{tabular} |
| 24 |
\\ |
| 25 |
Ce tableau peut être représenté par la figure suivante. |
| 26 |
|
| 27 |
|
| 28 |
\begin{figure}[h] |
| 29 |
|
| 30 |
\begin{center} |
| 31 |
\includegraphics[width=10cm,bb=0 0 742 513]{./interpolationexemple.jpg} |
| 32 |
% interpolationexemple.jpg: 742x513 pixel, 72dpi, 26.18x18.10 cm, bb=0 0 742 513 |
| 33 |
|
| 34 |
|
| 35 |
\caption{Tracé du relevé de points} |
| 36 |
\end{center} |
| 37 |
|
| 38 |
\end{figure} |
| 39 |
L'objectif de ce chapitre est de trouver une fonction qui passe par ces points pour obtenir une expression analytique de la fonction $v=f(t)$. On passe d'une représentation discrète à une représentation continue. Cette méthode se nomme l'interpolation des points. |
| 40 |
\\ |
| 41 |
|
| 42 |
\huge\danger\hspace{1cm}\normalsize Il faut bien faire la différence entre les méthodes d'interpolation et les méthodes d'approximation.\\ |
| 43 |
Les méthodes d'interpolation recherche une fonction qui passe exactement par les points donnés alors que les méthodes d'approximation recherche une fonction qui passe le plus proche possible des points sans forcement passer par ces points. |
| 44 |
\\Nous nous limitons dans ce cours aux méthodes d'interpolation. |
| 45 |
\section{Approximation par la méthode des moindres carrés} |
| 46 |
L'idée est de faire passer une courbe au plus proche de la série de point $(x_i,y_i)$. Pour cela, nous cherchons à faire correspondre la série de points avec une courbe modèle $f(x,\overrightarrow{\beta})$ où $\overrightarrow{\beta}$ est un vecteur de paramètres. |
| 47 |
L'objectif est de trouver les valeurs des différents paramètres $\beta$ afin que la courbe passe au plus proche des points. |
| 48 |
Pour cela on calcule la somme $S$ des carrés de l'écart de chaque point à la courbe à $m$ paramètres et on minimise cette somme. |
| 49 |
\subsection{Cas général} |
| 50 |
\begin{eqnarray*} |
| 51 |
S(\overrightarrow{\beta})=\sum_{i=1}^n\left(y_i-f(x_i,\overrightarrow{\beta})\right)^2 |
| 52 |
\end{eqnarray*} |
| 53 |
Pour minimiser cette somme il faut s'assurer que la dérivée par rapport à chaque paramètre est nulle : |
| 54 |
\begin{eqnarray*} |
| 55 |
\left \{ |
| 56 |
\begin{array}{l} |
| 57 |
\frac{\partial S(\overrightarrow{\beta})}{\partial \beta_1}=-2\sum_{i=1}^n\frac{\partial f(x_i,\overrightarrow{\beta})}{\partial \beta_1}\left(y_i-f(x_i,\overrightarrow{\beta})\right)=0 |
| 58 |
\\ \frac{\partial S(\overrightarrow{\beta})}{\partial \beta_2}=-2\sum_{i=1}^n\frac{\partial f(x_i,\overrightarrow{\beta})}{\partial \beta_2}\left(y_i-f(x_i,\overrightarrow{\beta})\right)=0 |
| 59 |
\\ \vdots\\ |
| 60 |
\frac{\partial S(\overrightarrow{\beta})}{\partial \beta_m}=-2\sum_{i=1}^n\frac{\partial f(x_i,\overrightarrow{\beta})}{\partial \beta_m}\left(y_i-f(x_i,\overrightarrow{\beta})\right)=0 |
| 61 |
\end{array} |
| 62 |
\right. |
| 63 |
\end{eqnarray*} |
| 64 |
On aboutit à un système d'équation de $m$ inconnues à $m$ variables. |
| 65 |
|
| 66 |
|
| 67 |
\subsection{Application à la régression linéaire} |
| 68 |
Dans le cas de la régression linéaire cela veut dire que la courbe recherchée est une droite de la forme $y=\beta_0+x\beta_1$. C'est le cas de l'exemple du paragraphe précédent. |
| 69 |
La fonction $S$ s'écrit alors |
| 70 |
\begin{eqnarray*} |
| 71 |
S(\beta_0,\beta_1)=\sum_{i=1}^n\left(y_i-\beta_0-x_i\beta_1\right)^2 |
| 72 |
\end{eqnarray*} |
| 73 |
La minimisation de S s'écrit |
| 74 |
\begin{eqnarray*} |
| 75 |
\left \{ |
| 76 |
\begin{array}{l} |
| 77 |
\frac{\partial S(\beta_0,\beta_1)}{\partial \beta_0}=-2\sum_{i=1}^n\left(y_i-\beta_0-x_i\beta_1\right)=0\\ |
| 78 |
\frac{\partial S(\beta_0,\beta_1)}{\partial \beta_1}=-2\sum_{i=1}^nx_i\left(y_i-\beta_0-x_i\beta_1\right)=0 |
| 79 |
\end{array} |
| 80 |
\right. |
| 81 |
\end{eqnarray*} |
| 82 |
On déduit de la première équation que |
| 83 |
\begin{eqnarray*} |
| 84 |
\sum_{i=1}^n\left(y_i-\beta_0-x_i\beta_1\right)=0\\ |
| 85 |
\sum_{i=1}^n y_i-\sum_{i=1}^n \beta_0-\sum_{i=1}^n x_i\beta_1=0\\ |
| 86 |
\sum_{i=1}^n y_i-n\beta_0-\beta_1\sum_{i=1}^n x_i=0\\ |
| 87 |
n\overline{y}-n\beta_0-\beta_1n\overline{x}=0\\ |
| 88 |
\overline{y}-\beta_1\overline{x}=\beta_0\\ |
| 89 |
\end{eqnarray*} |
| 90 |
En remplaçant $\beta_0$ dans le système précédent on a |
| 91 |
\begin{eqnarray*} |
| 92 |
\left \{ |
| 93 |
\begin{array}{l} |
| 94 |
\sum_{i=1}^n\left(y_i-\overline{y}+\beta_1\overline{x}-x_i\beta_1\right)=0\\ |
| 95 |
\sum_{i=1}^nx_i\left(y_i-\overline{y}+\beta_1\overline{x}-x_i\beta_1\right)=0 |
| 96 |
\end{array} |
| 97 |
\right. |
| 98 |
\end{eqnarray*} |
| 99 |
|
| 100 |
\begin{eqnarray*} |
| 101 |
\left \{ |
| 102 |
\begin{array}{l} |
| 103 |
\sum_{i=1}^n\left((y_i-\overline{y})-\beta_1(x_i-\overline{x})\right)=0\\ |
| 104 |
\sum_{i=1}^nx_i\left((y_i-\overline{y})-\beta_1(x_i-\overline{x})\right)=0 |
| 105 |
\end{array} |
| 106 |
\right. |
| 107 |
\end{eqnarray*} |
| 108 |
En multipliant la ligne 1 par $\overline{x}$ et en soustrayant les 2 équations on a |
| 109 |
\begin{eqnarray*} |
| 110 |
\sum_{i=1}^n(x_i-\overline{x})\left((y_i-\overline{y})-\beta_1(x_i-\overline{x})\right)=0\\ |
| 111 |
\sum_{i=1}^n(x_i-\overline{x})(y_i-\overline{y})-\beta_1\sum_{i=1}^n(x_i-\overline{x})^2=0\\ |
| 112 |
\beta_1=\frac{\sum_{i=1}^n(x_i-\overline{x})(y_i-\overline{y})}{\sum_{i=1}^n(x_i-\overline{x})^2}\\ |
| 113 |
\beta_1=\frac{\sum_{i=1}^n(x_iy_i+\overline{x}*\overline{y}-x_i\overline{y}-y_i\overline{x})}{\sum_{i=1}^n(x_i^2+\overline{x}^2-2x_i\overline{x})}\\ |
| 114 |
\beta_1=\frac{\sum_{i=1}^nx_iy_i+n*\overline{x}*\overline{y}-\sum_{i=1}^nx_i\overline{y}-\sum_{i=1}^ny_i\overline{x}}{\sum_{i=1}^nx_i^2+n*\overline{x}^2-2\overline{x}\sum_{i=1}^nx_i}\\ |
| 115 |
\beta_1=\frac{\sum_{i=1}^nx_iy_i+n*\overline{x}*\overline{y}-n*\overline{x}*\overline{y}-n*\overline{y}*\overline{x}}{\sum_{i=1}^nx_i^2+n*\overline{x}^2-2\overline{x}*n*\overline{x}}\\ |
| 116 |
\beta_1=\frac{\sum_{i=1}^nx_iy_i-n*\overline{x}*\overline{y}}{\sum_{i=1}^nx_i^2-n*\overline{x}^2}\\ |
| 117 |
\end{eqnarray*} |
| 118 |
Dans l'exemple donné on a $n=10$. On peut calculer $\beta_0$ et $\beta_1$ : \\ \\ |
| 119 |
\begin{tabular}{|r|r|r|r|r|} |
| 120 |
\hline |
| 121 |
&$x_i$ & $y_i$ &$x_i^2$ & $x_iy_i$ \\ |
| 122 |
\hline |
| 123 |
& $0$&$55$&$0$&$0$\\ |
| 124 |
&$5$&$60$&$25$&$300$\\ |
| 125 |
&$10$&$58$&$100$&$580$\\ |
| 126 |
&$15$&$54$&$225$&$810$\\ |
| 127 |
&$20$&$55$&$400$&$1100$\\ |
| 128 |
&$25$&$60$&$625$&$1500$\\ |
| 129 |
&$30$&$54$&$925$&$1620$\\ |
| 130 |
&$35$&$51$&$1225$&$1785$\\ |
| 131 |
&$40$&$52$&$1600$&$2080$\\ |
| 132 |
&$45$&$49$&$2025$&$2205$\\ |
| 133 |
\hline |
| 134 |
Total&$225$&$548$&$7125$&$11980$\\ |
| 135 |
Moyenne&$22.5$&$54.8$&&\\ |
| 136 |
\hline |
| 137 |
\end{tabular} |
| 138 |
\begin{eqnarray*} |
| 139 |
\beta_1&=&\frac{\sum_{i=1}^nx_iy_i-n*\overline{x}*\overline{y}}{\sum_{i=1}^nx_i^2-n*\overline{x}^2}\\ |
| 140 |
\beta_1&=&\frac{11980-10*22.5*54.8}{7125-10*22.5*22.5}=-0.16969696\\ |
| 141 |
\beta_0&=&\overline{y}-\beta_1\overline{x}=54.8+0.16969696*22.5=58.618181818\\ |
| 142 |
\end{eqnarray*} |
| 143 |
|
| 144 |
\begin{figure}[h] |
| 145 |
\begin{center} |
| 146 |
\includegraphics[width=10cm,bb=0 0 589 418]{./approximation.jpg} |
| 147 |
% approximation.jpg: 0x0 pixel, 300dpi, 0.00x0.00 cm, bb= |
| 148 |
\caption{Approximation de la vitesse d'un véhicule par une régression linéaire et vérification avec un logiciel (LibreOffice)} |
| 149 |
\end{center} |
| 150 |
\end{figure} |
| 151 |
\section{Méthodes des moindres carrées par les équations normales} |
| 152 |
L'idée de la méthode est de dire que l'on veut faire passer au plus proche de $n$ points une courbe $y=f(x,\overrightarrow{\beta})$ où $\overrightarrow{\beta}$ est un vecteur de $m$ paramètres |
| 153 |
\\ Pour les $n$ points on peut écrire que |
| 154 |
\begin{eqnarray*} |
| 155 |
y_i=f(x_i,\overrightarrow{\beta})\quad 1\leq i\leq n |
| 156 |
\end{eqnarray*} |
| 157 |
soit $n$ équations à $m$ variables. On obtient dont un système de $n$ inconnues à $m$ paramètres : |
| 158 |
\begin{eqnarray*} |
| 159 |
A(n,m)*x(m)=B(n) |
| 160 |
\end{eqnarray*} |
| 161 |
Ce système se transforme en un système d'équations normales de $m$ équations à $m$ inconnues |
| 162 |
\begin{eqnarray*} |
| 163 |
Ax=B\\ |
| 164 |
A^tAx=A^tB |
| 165 |
\end{eqnarray*} |
| 166 |
Ce système peut se résoudre grâce aux méthodes vues au chapitre précédent. |
| 167 |
\\[1cm] En reprenant l'exemple précédent il vient que l'on peut construire le système d'équations suivant : |
| 168 |
\begin{eqnarray*} |
| 169 |
\left \{ |
| 170 |
\begin{array}{l} |
| 171 |
\beta_0+0\beta_1=55\\ |
| 172 |
\beta_0+5\beta_1=60\\ |
| 173 |
\beta_0+10\beta_1=58\\ |
| 174 |
\beta_0+15\beta_1=54\\ |
| 175 |
\beta_0+20\beta_1=55\\ |
| 176 |
\beta_0+25\beta_1=60\\ |
| 177 |
\beta_0+30\beta_1=54\\ |
| 178 |
\beta_0+35\beta_1=51\\ |
| 179 |
\beta_0+40\beta_1=52\\ |
| 180 |
\beta_0+45\beta_1=49\\ |
| 181 |
\end{array} |
| 182 |
\right. |
| 183 |
\end{eqnarray*} |
| 184 |
soit sous un système matriciel |
| 185 |
\begin{eqnarray*} |
| 186 |
\begin{pmatrix} |
| 187 |
1&0\\ |
| 188 |
1&5\\ |
| 189 |
1&10\\ |
| 190 |
1&15\\ |
| 191 |
1&20\\ |
| 192 |
1&25\\ |
| 193 |
1&30\\ |
| 194 |
1&35\\ |
| 195 |
1&40\\ |
| 196 |
1&45\\ |
| 197 |
\end{pmatrix} |
| 198 |
\begin{pmatrix} |
| 199 |
\beta_0\\ |
| 200 |
\beta_1 |
| 201 |
\end{pmatrix} |
| 202 |
= |
| 203 |
\begin{pmatrix} |
| 204 |
55\\ |
| 205 |
60\\ |
| 206 |
58\\ |
| 207 |
54\\ |
| 208 |
55\\ |
| 209 |
60\\ |
| 210 |
54\\ |
| 211 |
51\\ |
| 212 |
52\\ |
| 213 |
49\\ |
| 214 |
\end{pmatrix} |
| 215 |
\end{eqnarray*} |
| 216 |
\begin{eqnarray*} |
| 217 |
\begin{pmatrix} |
| 218 |
0&5&10&15&20&25&30&35&40&45\\ |
| 219 |
1&1&1&1&1&1&1&1&1&1 |
| 220 |
\end{pmatrix} |
| 221 |
\begin{pmatrix} |
| 222 |
1&0\\ |
| 223 |
1&5\\ |
| 224 |
1&10\\ |
| 225 |
1&15\\ |
| 226 |
1&20\\ |
| 227 |
1&25\\ |
| 228 |
1&30\\ |
| 229 |
1&35\\ |
| 230 |
1&40\\ |
| 231 |
1&45\\ |
| 232 |
\end{pmatrix} |
| 233 |
\begin{pmatrix} |
| 234 |
\beta_0\\ |
| 235 |
\beta_1 |
| 236 |
\end{pmatrix} |
| 237 |
=\\ |
| 238 |
\begin{pmatrix} |
| 239 |
0&5&10&15&20&25&30&35&40&45\\ |
| 240 |
1&1&1&1&1&1&1&1&1&1 |
| 241 |
\end{pmatrix} |
| 242 |
\begin{pmatrix} |
| 243 |
55\\ |
| 244 |
60\\ |
| 245 |
58\\ |
| 246 |
54\\ |
| 247 |
55\\ |
| 248 |
60\\ |
| 249 |
54\\ |
| 250 |
51\\ |
| 251 |
52\\ |
| 252 |
49\\ |
| 253 |
\end{pmatrix} |
| 254 |
\end{eqnarray*} |
| 255 |
\begin{eqnarray*} |
| 256 |
\begin{pmatrix} |
| 257 |
225&7125\\ |
| 258 |
10&225\\ |
| 259 |
\end{pmatrix} |
| 260 |
\begin{pmatrix} |
| 261 |
\beta_0\\ |
| 262 |
\beta_1 |
| 263 |
\end{pmatrix} |
| 264 |
= |
| 265 |
\begin{pmatrix} |
| 266 |
11980\\548\\ |
| 267 |
\end{pmatrix} |
| 268 |
\end{eqnarray*} |
| 269 |
\begin{eqnarray*} |
| 270 |
\beta_0=\frac{11980*225-7125*548}{225*225-10*7125}=58.61818181\\ |
| 271 |
\beta_1=\frac{225*548-11980*10}{225*225-10*7125}=-0.169696969696 |
| 272 |
\end{eqnarray*} |
| 273 |
On retrouve exactement la même droite que précédemment $y=-0.1696969696x+58.6181818181$\\ |
| 274 |
On peut passer à un autre exemple pour faire passer une courbe de degré $2$ au travers des mêmes points. Dans ce cas la courbe a trois paramètres et s'écrit $y=\beta_0+\beta_1 x+\beta_2 x^2$. |
| 275 |
Les calculs précédents deviennent : |
| 276 |
\begin{eqnarray*} |
| 277 |
\left \{ |
| 278 |
\begin{array}{l} |
| 279 |
\beta_0+0\beta_1+0\beta_2=55\\ |
| 280 |
\beta_0+5\beta_1+25\beta_2=60\\ |
| 281 |
\beta_0+10\beta_1+100\beta_2=58\\ |
| 282 |
\beta_0+15\beta_1+225\beta_2=54\\ |
| 283 |
\beta_0+20\beta_1+400\beta_2=55\\ |
| 284 |
\beta_0+25\beta_1+625\beta_2=60\\ |
| 285 |
\beta_0+30\beta_1+900\beta_2=54\\ |
| 286 |
\beta_0+35\beta_1+1225\beta_2=57\\ |
| 287 |
\beta_0+40\beta_1+1600\beta_2=52\\ |
| 288 |
\beta_0+45\beta_1+2025\beta_2=49\\ |
| 289 |
\end{array} |
| 290 |
\right. |
| 291 |
\end{eqnarray*} |
| 292 |
\begin{eqnarray*} |
| 293 |
\begin{pmatrix} |
| 294 |
1&0&0\\ |
| 295 |
1&5&25\\ |
| 296 |
1&10&100\\ |
| 297 |
1&15&225\\ |
| 298 |
1&20&400\\ |
| 299 |
1&25&625\\ |
| 300 |
1&30&900\\ |
| 301 |
1&35&1225\\ |
| 302 |
1&40&1600\\ |
| 303 |
1&45&2025\\ |
| 304 |
\end{pmatrix} |
| 305 |
\begin{pmatrix} |
| 306 |
\beta_0\\ |
| 307 |
\beta_1\\ |
| 308 |
\beta_2\\ |
| 309 |
\end{pmatrix} |
| 310 |
= |
| 311 |
\begin{pmatrix} |
| 312 |
55\\ |
| 313 |
60\\ |
| 314 |
58\\ |
| 315 |
54\\ |
| 316 |
55\\ |
| 317 |
60\\ |
| 318 |
54\\ |
| 319 |
57\\ |
| 320 |
52\\ |
| 321 |
49\\ |
| 322 |
\end{pmatrix} |
| 323 |
\end{eqnarray*} |
| 324 |
\begin{eqnarray*} |
| 325 |
\begin{pmatrix} |
| 326 |
0&25&1000&225&400&625&900&1225&1600&2025\\ |
| 327 |
0&5&10&15&20&25&30&35&40&45\\ |
| 328 |
1&1&1&1&1&1&1&1&1&1 |
| 329 |
\end{pmatrix} |
| 330 |
\begin{pmatrix} |
| 331 |
1&0&0\\ |
| 332 |
1&5&25\\ |
| 333 |
1&10&100\\ |
| 334 |
1&15&225\\ |
| 335 |
1&20&400\\ |
| 336 |
1&25&625\\ |
| 337 |
1&30&900\\ |
| 338 |
1&35&1225\\ |
| 339 |
1&40&1600\\ |
| 340 |
1&45&2025\\ |
| 341 |
\end{pmatrix} |
| 342 |
\begin{pmatrix} |
| 343 |
\beta_0\\ |
| 344 |
\beta_1\\ |
| 345 |
\beta_2\\ |
| 346 |
\end{pmatrix} |
| 347 |
=\\ |
| 348 |
\begin{pmatrix} |
| 349 |
0&25&1000&225&400&625&900&1225&1600&2025\\ |
| 350 |
0&5&10&15&20&25&30&35&40&45\\ |
| 351 |
1&1&1&1&1&1&1&1&1&1 |
| 352 |
\end{pmatrix} |
| 353 |
\begin{pmatrix} |
| 354 |
55\\ |
| 355 |
60\\ |
| 356 |
58\\ |
| 357 |
54\\ |
| 358 |
55\\ |
| 359 |
60\\ |
| 360 |
54\\ |
| 361 |
57\\ |
| 362 |
52\\ |
| 363 |
49\\ |
| 364 |
\end{pmatrix} |
| 365 |
\end{eqnarray*} |
| 366 |
\begin{eqnarray*} |
| 367 |
\begin{pmatrix} |
| 368 |
10 & 245 &7150\\ |
| 369 |
245 & 8325 &261875\\ |
| 370 |
7150 & 261875 &9628750\\ |
| 371 |
\end{pmatrix} |
| 372 |
\begin{pmatrix} |
| 373 |
\beta_0\\ |
| 374 |
\beta_1\\ |
| 375 |
\beta_2\\ |
| 376 |
\end{pmatrix} |
| 377 |
= |
| 378 |
\begin{pmatrix} |
| 379 |
548\\ |
| 380 |
13080\\ |
| 381 |
373800 |
| 382 |
\end{pmatrix} |
| 383 |
\end{eqnarray*} |
| 384 |
\begin{eqnarray*} |
| 385 |
\begin{pmatrix} |
| 386 |
\beta_0\\ |
| 387 |
\beta_1\\ |
| 388 |
\beta_2\\ |
| 389 |
\end{pmatrix} |
| 390 |
= |
| 391 |
\begin{pmatrix} |
| 392 |
57.6540770222\\ |
| 393 |
-0.000126148741\\ |
| 394 |
-0.003987393535\\ |
| 395 |
\end{pmatrix} |
| 396 |
\end{eqnarray*} |
| 397 |
La courbe a pour équation $y=57.6540770222-0.000126148741x-0.003987393535x^2$ |
| 398 |
\\[1cm]Le problème principal de cette méthode est que les équations normales sont des systèmes d'équations linéaires souvent mal conditionnés. |
| 399 |
Il est préférable se solutionner le problème original non carré à l'aide des méthodes de Householder (méthode du QR) ou des transformations de Givens. |
| 400 |
|
| 401 |
|
| 402 |
|
| 403 |
|
| 404 |
|
| 405 |
\section{Interpolation par un polynôme} |
| 406 |
L'idée de base est de construire un polynôme d'interpolation (ou de collocation) qui passe par les points donnés. |
| 407 |
\\ |
| 408 |
Un polynôme de degré $n$ s'écrit |
| 409 |
\begin{eqnarray*} |
| 410 |
P_n(x)&=&a_0+a_1x+...+a_nx^n\\ |
| 411 |
avec \quad a_n&\neq&0 |
| 412 |
\end{eqnarray*} |
| 413 |
$P_n(x)$ possède $n$ racines complexes ou réelles. Les racines sont $r_i$ et elles sont définies par $P_n(r_i)=0$. |
| 414 |
Il existe un seul polynôme de degré $n$ passant par $n+1$ points. |
| 415 |
|
| 416 |
Démonstration : |
| 417 |
Si $Pn(x)$ n'est pas unique alors il existe au moins deux polynômes ($P_{1n}(x)$ et $P_{2n}(x)$) qui passent par $n+1$ points. On calcul alors $d_n(x)$ un polynôme de degré $n$ |
| 418 |
\begin{eqnarray*} |
| 419 |
d_n(x)=P_{1n}(x)-P_{2n}(x)\\ |
| 420 |
\end{eqnarray*} |
| 421 |
On calcule ensuite la valeur de $d_n(x)$ pour chaque $n+1$ points d'interpolation $(x_i,y_i)$. |
| 422 |
\begin{eqnarray*} |
| 423 |
d_n(x_i)&=&P_{1n}(x_i)-P_{2n}(x_i)\\ |
| 424 |
&=&P_{1n}(x_i)-P_{2n}(x_i)\\ |
| 425 |
&=&y_i-y_i\\ |
| 426 |
&=&0\\ |
| 427 |
\end{eqnarray*} |
| 428 |
On constate que $d_n(x)$ un polynôme de degré $n$ possède $n+1$ racines. Ce qui est contraire aux propriétés des polynômes. Donc l'hypothèse de non unicité est fausse. $Pn(x)$ est unique. |
| 429 |
|
| 430 |
\subsection{Méthode de la matrice de Vandermonde} |
| 431 |
La première méthode pour calculer le polynôme d'interpolation est de simplement dire que le polynôme passe par $n+1$ points. On construit donc $n+1$ équations et comme il y a $n+1$ inconnues (les $a_i$), on obtient un système linéaire de dimension $(n+1)*(n+1)$ à résoudre. |
| 432 |
En écrivant que le point $(x_i,y_i)$ appartient au polynôme on a |
| 433 |
\begin{eqnarray*} |
| 434 |
P_n(x_i)=a_0+a_1x_i+...+a_nx_i^n=y_i |
| 435 |
\end{eqnarray*} |
| 436 |
et on obtient le système |
| 437 |
\begin{eqnarray*} |
| 438 |
\begin{pmatrix} |
| 439 |
1 & x_0 & ... & x_0^n\\ |
| 440 |
1 & x_1 & ... & x_1^n\\ |
| 441 |
& & \vdots&\\ |
| 442 |
1 & x_n & ... & x_n^n\\ |
| 443 |
\end{pmatrix} |
| 444 |
\begin{pmatrix} |
| 445 |
a_0\\ |
| 446 |
a_1\\ |
| 447 |
\vdots\\ |
| 448 |
a_n\\ |
| 449 |
\end{pmatrix} |
| 450 |
= |
| 451 |
\begin{pmatrix} |
| 452 |
y_0\\ |
| 453 |
y_1\\ |
| 454 |
\vdots\\ |
| 455 |
y_n\\ |
| 456 |
\end{pmatrix} |
| 457 |
\end{eqnarray*} |
| 458 |
La matrice $\begin{pmatrix} |
| 459 |
1 & x_0 & ... & x_0^n\\ |
| 460 |
1 & x_1 & ... & x_1^n\\ |
| 461 |
& & \vdots&\\ |
| 462 |
1 & x_n & ... & x_n^n\\ |
| 463 |
\end{pmatrix} |
| 464 |
$ s'appelle la matrice de Vandermonde. |
| 465 |
Il suffit de résoudre ce système pour obtenir le polynôme. |
| 466 |
|
| 467 |
Exemple : Calculer le polynôme d'interpolation qui passent par les points $(0,1)$,$(1,2)$,$(2,9)$ et $(3,28)$. |
| 468 |
\\Nous avons 4 points, nous devons donc déterminer $P_3(x)$. Dans ce cas le système s'écrit |
| 469 |
\begin{eqnarray*} |
| 470 |
\begin{pmatrix} |
| 471 |
1 & 0 & 0 & 0\\ |
| 472 |
1 & 1 & 1 & 1\\ |
| 473 |
1 & 2 & 4 & 8\\ |
| 474 |
1 & 3 & 9 & 27\\ |
| 475 |
\end{pmatrix} |
| 476 |
\begin{pmatrix} |
| 477 |
a_0\\ |
| 478 |
a_1\\ |
| 479 |
a_2\\ |
| 480 |
a_3\\ |
| 481 |
\end{pmatrix} |
| 482 |
= |
| 483 |
\begin{pmatrix} |
| 484 |
1\\ |
| 485 |
2\\ |
| 486 |
9\\ |
| 487 |
28\\ |
| 488 |
\end{pmatrix} |
| 489 |
\end{eqnarray*} |
| 490 |
La solution est |
| 491 |
\begin{eqnarray*} |
| 492 |
\begin{pmatrix} |
| 493 |
a_0\\ |
| 494 |
a_1\\ |
| 495 |
a_2\\ |
| 496 |
a_3\\ |
| 497 |
\end{pmatrix} |
| 498 |
= |
| 499 |
\begin{pmatrix} |
| 500 |
1\\ |
| 501 |
0\\ |
| 502 |
0\\ |
| 503 |
1\\ |
| 504 |
\end{pmatrix} |
| 505 |
\end{eqnarray*} |
| 506 |
et le polynôme d'interpolation s'écrit $P_3(x)=1+x^3$. |
| 507 |
\begin{figure}[h] |
| 508 |
|
| 509 |
\begin{center} |
| 510 |
\begin{center} |
| 511 |
\includegraphics[width=12cm,bb=0 0 746 481]{./interpolationex.jpg} |
| 512 |
% interpolationex.jpg: 995x641 pixel, 96dpi, 26.33x16.96 cm, bb=0 0 746 481 |
| 513 |
\end{center} |
| 514 |
|
| 515 |
|
| 516 |
\caption{Tracé de l'interpolation des points $(0,1),(1,2),(2,9),(3,28)$} |
| 517 |
\end{center} |
| 518 |
|
| 519 |
\end{figure} |
| 520 |
Cette méthode apparaît correcte pour obtenir le résultat souhaité. Cependant elle a des désavantages majeurs : |
| 521 |
\begin{itemize} |
| 522 |
\item Elle nécessite une résolution d'un système linéaire ce qui peut s'avérer coûteux en temps CPU. |
| 523 |
\item La matrice de Vandermonde présente des arguments pour dire que son conditionnement peut poser problème. En effet chaque colonne est obtenue en élevant de degré de la colonne précédente de 1. Ce qui a pour effet de faire augmenter en fonction de $n$ l'écart d'ordre entre les nombres de la matrices. Tout est réuni pour augmenter le conditionnement de la matrice dès que $n$ grandit. |
| 524 |
\item Si on ajoute un point à une liste de points, tout le travail est à refaire. On ne peut pas déduire $P_n(x)$ à partir de $P_{n-1}(x)$. Ceci est problématique pour l'utilisation en temps réel. |
| 525 |
\end{itemize} |
| 526 |
|
| 527 |
\subsection{Méthode de Lagrange} |
| 528 |
|
| 529 |
La méthode de Lagrange est un autre moyen d'obtenir le même résultat que la méthode de Vandermonde en corrigeant ses désavantages. |
| 530 |
\\L'idée de la méthode est de construire des polynômes $L_i(x)$ de degré $n$ tel que pour tous les points d'interpolation $(x_i,y_i)$ on a |
| 531 |
\begin{eqnarray*} |
| 532 |
L_i(x_i)=1\quad et\quad L_i(x_j)=0\quad pour \quad 0\le i\le n |
| 533 |
\end{eqnarray*} |
| 534 |
Cette définition conduit à la définition de $n+1$ polynômes de degré $n$. |
| 535 |
\\Nous avons alors |
| 536 |
\begin{eqnarray*} |
| 537 |
P_n(x)=\sum_{i=0}^ny_iL_i(x) |
| 538 |
\end{eqnarray*} |
| 539 |
\\Démonstration |
| 540 |
\begin{eqnarray*} |
| 541 |
P_n(x_j)=\sum_{i=0}^ny_iL_i(x_j)=y_j*L_j(x_j)+\sum_{i=0,i\ne j}^ny_iL_i(x_j)=y_j |
| 542 |
\end{eqnarray*} |
| 543 |
|
| 544 |
Construction des polynômes $L$: |
| 545 |
\begin{itemize} |
| 546 |
\item degré 1 : polynôme passant par les point $(x_0,y_0)$ et $(x_1,y_1)$. |
| 547 |
\begin{eqnarray*} |
| 548 |
\left. |
| 549 |
\begin{array}{l} |
| 550 |
L_0(x_0)=1\\ |
| 551 |
L_0(x_1)=0\\ |
| 552 |
\end{array} |
| 553 |
\right \} |
| 554 |
L_0(x)=\frac{x-x_1}{x_0-x_1}\\ |
| 555 |
\left. |
| 556 |
\begin{array}{l} |
| 557 |
L_1(x_0)=0\\ |
| 558 |
L_1(x_1)=1\\ |
| 559 |
\end{array} |
| 560 |
\right \} |
| 561 |
L_1(x)=\frac{x-x_0}{x_1-x_0}\\ |
| 562 |
P_1(x)=y_0\frac{x-x_1}{x_0-x_1}+y_1\frac{x-x_0}{x_1-x_0} |
| 563 |
\end{eqnarray*} |
| 564 |
\item degré 2 : polynôme passant par les point $(x_0,y_0)$, $(x_1,y_1)$ et $(x_2,y_2)$. |
| 565 |
\begin{eqnarray*} |
| 566 |
\left. |
| 567 |
\begin{array}{l} |
| 568 |
L_0(x_0)=1\\ |
| 569 |
L_0(x_1)=0\\ |
| 570 |
L_0(x_2)=0\\ |
| 571 |
\end{array} |
| 572 |
\right \} |
| 573 |
L_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}\\ |
| 574 |
\left. |
| 575 |
\begin{array}{l} |
| 576 |
L_1(x_0)=0\\ |
| 577 |
L_1(x_1)=1\\ |
| 578 |
L_1(x_2)=0\\ |
| 579 |
\end{array} |
| 580 |
\right \} |
| 581 |
L_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}\\ |
| 582 |
\left. |
| 583 |
\begin{array}{l} |
| 584 |
L_2(x_0)=0\\ |
| 585 |
L_2(x_1)=0\\ |
| 586 |
L_2(x_2)=1\\ |
| 587 |
\end{array} |
| 588 |
\right \} |
| 589 |
L_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}\\ |
| 590 |
P_2(x)=y_0\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}+y_1\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}+y_2\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)} |
| 591 |
\end{eqnarray*} |
| 592 |
\item degré $n$ |
| 593 |
\end{itemize} |
| 594 |
|
| 595 |
\begin{eqnarray*} |
| 596 |
L_i(x)=\frac{(x-x_0)...(x-x_{i-1})(x-x_{i+1})...(x-x_n)}{(x_i-x_0)...(x_i-x_{i-1})(x_i-x_{i+1})...(x_I-x_n)} |
| 597 |
\end{eqnarray*} |
| 598 |
En reprenant l'exemple du paragraphe précédent qui consiste à rechercher le polynôme d'interpolation qui passe par les points $(0,1)$,$(1,2)$,$(2,9)$ et $(3,28)$. |
| 599 |
\\On calcule les polynômes $L$ : |
| 600 |
\begin{eqnarray*} |
| 601 |
L_0(x)&=&\frac{(x-1)(x-2)(x-3)}{(0-1)(0-2)(0-3)}=-\frac{1}{6}(x^3-6x^2+11x-6)\\ |
| 602 |
L_1(x)&=&\frac{(x-0)(x-2)(x-3)}{(1-0)(1-2)(1-3)}=\frac{1}{2}(x^3-5x^2+6x)\\ |
| 603 |
L_2(x)&=&\frac{(x-0)(x-1)(x-3)}{(2-0)(2-1)(2-3)}=-\frac{1}{2}(x^3-4x^2+3x)\\ |
| 604 |
L_3(x)&=&\frac{(x-0)(x-1)(x-2)}{(3-0)(3-1)(3-2)}=\frac{1}{6}(x^3-3x^2+2x)\\ |
| 605 |
P_3(x)&=&(1)\frac{-1}{6}(x^3-6x^2+11x-6)+(2)\frac{1}{2}(x^3-5x^2+6x)+(9)\frac{-1}{2}(x^3-4x^2+3x)+(28)\frac{1}{6}(x^3-3x^2+2x)\\ |
| 606 |
&=&x^3+1 |
| 607 |
\end{eqnarray*} |
| 608 |
Cette méthode est efficace mais non récursive. Les polynômes de degré $n+1$ ne peuvent pas être calculé à partir des polynômes de degré $n$. L'utilisation pour des processus en temps réel peut être un problème. |
| 609 |
|
| 610 |
\subsection{Méthode de Newton} |
| 611 |
On écrit le polynôme $P_n(x)$ sous la forme |
| 612 |
\begin{eqnarray*} |
| 613 |
P_n(x)=a_0+a_1(x-x_0)+a_2(x-x_0)(x-x_1)+...+a_n(x-x_0)(x-x_1)...(x-x_{n-1}) |
| 614 |
\end{eqnarray*} |
| 615 |
et on identifie les $a_i$ en calculant successivement $P_n(x_i)=y_i$ |
| 616 |
\begin{eqnarray*} |
| 617 |
P_n(x_0)&=&a_0=y_0=f(x_0)\\ |
| 618 |
P_n(x_1)&=&a_0+a_1(x_1-x_0)=y_1\\ |
| 619 |
& &y_0+a_1(x_1-x_0)=y_1\quad a_1=\frac{y_1-y_0}{x_1-x_0}=\frac{f(x_1)-f(x_0)}{x_1-x_0}\\ |
| 620 |
\end{eqnarray*} |
| 621 |
On pose $f[x_i,x_{i+1}]=\frac{f(x_{i+1})-f(x_i)}{x_{i+1}-x_i}$ d'où $a_1=f[x_0,x_1]$\\ |
| 622 |
\begin{eqnarray*} |
| 623 |
P_n(x_2)&=&a_0+a_1(x_2-x_0)+a_2(x_2-x_0)(x_2-x_1)=y_2\\ |
| 624 |
& &f(x_0)+f[x_0,x_1](x_2-x_0)+a_2(x_2-x_0)(x_2-x_1)=f(x_2)\\ |
| 625 |
a_2&=&\frac{1}{(x_2-x_0)(x_2-x_1)}\left(f(x_2)-f(x_0)-(x_2-x_0)f[x_0,x_1]\right)\\ |
| 626 |
&=&\frac{1}{x_2-x_0}\left(\frac{f(x_2)-f(x_0)}{x_2-x_1}-\frac{x_2-x_0}{x_2-x_1}f[x_0,x_1]\right)\\ |
| 627 |
&=&\frac{1}{x_2-x_0}\left(\frac{f(x_2)-f(x_1)+f(x_1)-f(x_0)}{x_2-x_1}-\frac{x_2-x_0}{x_2-x_1}f[x_0,x_1]\right)\\ |
| 628 |
&=&\frac{1}{x_2-x_0}\left(\frac{f(x_2)-f(x_1)}{x_2-x_1}+\frac{f(x_1)-f(x_0)}{x_1-x_0}\frac{x_1-x_0}{x_2-x_1}-\frac{x_2-x_0}{x_2-x_1}f[x_0,x_1]\right)\\ |
| 629 |
&=&\frac{1}{x_2-x_0}\left(f[x_1,x_2]+f[x_0,x_1]\frac{x_1-x_0}{x_2-x_1}-\frac{x_2-x_0}{x_2-x_1}f[x_0,x_1]\right)\\ |
| 630 |
&=&\frac{1}{x_2-x_0}\left(f[x_1,x_2]-f[x_0,x_1]\right)\\ |
| 631 |
\end{eqnarray*} |
| 632 |
En posant $f[x_i,x_{i+1},x_{i+2}]=\frac{f[x_{i+1},x_{i+2}]-f[x_i,x_{i+1}]}{x_{i+2}-x_i}$ il vient $a_2=f[x_0,x_1,x_2]$ |
| 633 |
|
| 634 |
En généralisant la démarche de calcul de $a_2$ et en posant $f[x_i,..,x_j]=\frac{f[x_{i+1},..,x_j]-f[x_i,..,x_{j-1}]}{x_j-x_i}$ pour $j>i+1$ on a |
| 635 |
\begin{eqnarray*} |
| 636 |
a_i=f[x_0,...,x_i] |
| 637 |
\end{eqnarray*} |
| 638 |
On évalue le polynôme d'interpolation en construisant la table des différences divisées.\\ |
| 639 |
\begin{tabular}{|r|r|r|r|r|r|} |
| 640 |
\hline |
| 641 |
$x_i$ & $f(x_i)$ & $f[x_i,x_{i+1}]$ & $f[x_i,x_{i+1},x_{i+2}]$ & $...$ & $f[x_i,...x_n]$ \\ |
| 642 |
\hline |
| 643 |
$x_0$ & $f(x_0)=a_0$ & & & & \\ |
| 644 |
& & $f[x_0,x_1]=a_1$ & & & \\ |
| 645 |
$x_1$ & $f(x_1)$ & & $f[x_0,x_1,x_2]=a_2$ & & \\ |
| 646 |
& & $f[x_1,x_2]$ & & ... & $f[x_1,...,x_n]=a_n$ \\ |
| 647 |
$x_2$ & $f(x_2)$ & & $f[x_1,x_2,x_3]$ & & \\ |
| 648 |
& & $f[x_2,x_3]$ & & & \\ |
| 649 |
$x_3$ & $f(x_3)$ & & & & \\ |
| 650 |
|
| 651 |
\hline |
| 652 |
\end{tabular}\\ |
| 653 |
\\En reprenant l'exemple du paragraphe précédent qui consiste à rechercher le polynôme d'interpolation qui passe par les points $(0,1)$,$(1,2)$,$(2,9)$ et $(3,28)$ on calcule la table des différences divisées pour cet exemple \\ |
| 654 |
\\ |
| 655 |
\begin{tabular}{|r|r|l|l|l|} |
| 656 |
\hline |
| 657 |
$x_i$ & $f(x_i)$ & $f[x_i,x_{i+1}]$ & $f[x_i,x_{i+1},x_{i+2}]$ & $f[x_i,x_{i+1},x_{i+2},x_{i+3}]$ \\ |
| 658 |
\hline |
| 659 |
$0$ & $1$ & & & \\ |
| 660 |
& & $\frac{2-1}{1-0}=1 $ & & \\ |
| 661 |
$1$ & $2$ & & $\frac{7-1}{2-0}=3$ & \\ |
| 662 |
& & $\frac{9-2}{2-1}=7$ & &$\frac{6-3}{3-0}=1$ \\ |
| 663 |
$2$ & $9$ & & $\frac{19-7}{3-1}=6$ & \\ |
| 664 |
& & $\frac{28-9}{3-2}=19 $ & & \\ |
| 665 |
$3$ & $28$ & & & \\ |
| 666 |
|
| 667 |
\hline |
| 668 |
\end{tabular} |
| 669 |
\\ |
| 670 |
\\On calcule alors le polynôme d'interpolation |
| 671 |
\begin{eqnarray*} |
| 672 |
P_3(x)&=&1+1(x-0)+3(x-0)(x-1)+1(x-0)(x-1)(x-2)\\ |
| 673 |
&=&x^3+1\\ |
| 674 |
\end{eqnarray*} |
| 675 |
on remarque que |
| 676 |
\begin{eqnarray*} |
| 677 |
P_2(x)&=&1+1(x-0)+3(x-0)(x-1)\\ |
| 678 |
&=&3x^2-2x+1\\ |
| 679 |
\end{eqnarray*} |
| 680 |
ou que |
| 681 |
\begin{eqnarray*} |
| 682 |
P_3(x)&=&P_2(x)+1(x-0)(x-1)(x-2)\\ |
| 683 |
\end{eqnarray*} |
| 684 |
Si on ajoute des points à l'interpolation on peut trouver le nouveau polynôme en ajoutant une correction au polynôme de degré inférieur. |
| 685 |
|
| 686 |
|
| 687 |
\subsection{Erreur d'interpolation} |
| 688 |
Soit $E_n(x)$ l'erreur d'interpolation alors |
| 689 |
\begin{eqnarray*} |
| 690 |
E_n(x)=f(x)-P_n(x) |
| 691 |
\end{eqnarray*} |
| 692 |
Puisque on fait de l'interpolation, on a |
| 693 |
\begin{eqnarray*} |
| 694 |
E_n(x_i)=0 |
| 695 |
\end{eqnarray*} |
| 696 |
Tout comme l'erreur de la formule de Taylor peut être définie sans être calculée, l'erreur d'interpolation se calcule de la manière suivante |
| 697 |
\\ Il existe $\zeta (x)\in ]x_0,x_n[$ tel que |
| 698 |
\begin{eqnarray*} |
| 699 |
E_n(x)=\frac{f^{(n+1)}\zeta (x)}{(n+1)!}(x-x_0)...(x-x_n) |
| 700 |
\end{eqnarray*} |
| 701 |
|
| 702 |
\begin{itemize} |
| 703 |
\item Tout comme dans la formule d erreur de la formule de Taylor, on sait que $\zeta (x)$ existe mais on ne sait pas le calculer. |
| 704 |
\item L'erreur est nulle aux points d'interpolation. |
| 705 |
\item L'erreur est petite autour des points d'interpolation |
| 706 |
\item L'erreur est un polynôme de degré $n+1$. Si $n$ est grand (plus grand que $3$) le polynôme est de degré important et l'erreur oscille beaucoup. L'erreur devient ainsi importante quand le degré est important. Et comme le degré est lié aux nombre de points d'interpolation cette manière d'interpoler est peu intéressante. |
| 707 |
\end{itemize} |
| 708 |
|
| 709 |
|
| 710 |
|
| 711 |
|
| 712 |
\section{Interpolation par des polynômes par morceau} |
| 713 |
L'objectif est de choisir le degré des polynômes d'interpolation quelque soit le nombre de points d'interpolation tout en conservant des courbes lisses et régulières. |
| 714 |
Pour obtenir des courbes lisses, il faut des fonctions dérivables plusieurs fois. Plus le degré est grand plus la courbe est lisse mais plus le degré est grand plus l'oscillation est importante. Il faut faire un compromis pour faire le bon choix. |
| 715 |
Ainsi nous nous arrêtons sur une interpolation par des polynômes de degrés $3$. Nous choisissons la méthode des splines cubiques qui consiste à relier les points par des polynômes de degré $3$. |
| 716 |
\subsection{Les splines cubiques} |
| 717 |
Soit $n+1$ points d'interpolation noté $(x_i,y_i=f(x_i)=f_i)$ pour $0\le i \le n$. |
| 718 |
\\Pour les $n$ intervalles $[x_i,x_{i+1}]$ avec $0\le i \le n-1$ on pose |
| 719 |
\begin{eqnarray*} |
| 720 |
h_i&=&x_{i+1}-x_i\\ |
| 721 |
p_i(x)&=&f_i+f'_i(x-x_i)+\frac{f''_i}{2!}(x-x_i)^2+\frac{f'''_i}{3!}(x-x_i)^3\\ |
| 722 |
\end{eqnarray*} |
| 723 |
On a donc $4n$ coefficients à déterminer : $f_i,f'_i,f''_i,f'''_i$. |
| 724 |
\\On va essayer d'exprimer toutes les inconnues en fonctions des $f''_i$ Pour cela on ajoute 1 inconnue supplémentaire qui est $f''_n$ pour aboutir à $4n+1$ inconnues. |
| 725 |
Cette nouvelle inconnue peut s'exprimer en fonction des autres inconnues : |
| 726 |
\begin{eqnarray} |
| 727 |
\label{eqnspline} |
| 728 |
f''_n(x)=f''_{n-1}(x_n)+f'''_{n-1}(x_n-x_{n-1})=f''_{n-1}(x_n)+h_{n-1}f'''_{n-1} |
| 729 |
\end{eqnarray} |
| 730 |
Nous allons écrire maintenant les différentes conditions de régularité de l'interpolation : |
| 731 |
\begin{itemize} |
| 732 |
\item Nous faisons une interpolation : $p_i(x)=f(x_i)=f_i$ pour $0\le i \le n$ |
| 733 |
\item Continuité de la dérivée seconde pour les $n-1$ points intérieurs |
| 734 |
\begin{eqnarray*} |
| 735 |
p''_{i+1}(x_{i+1})&=&p''_{i}(x_{i+1}) \quad 0\le i \le n-2\\ |
| 736 |
f''_{i+1}&=&f''_i+f'''_i(x_{i+1}-x_i)=f''_i+f'''_ih_i\\ |
| 737 |
f'''_i&=&\frac{f''_{i+1}-f''_i}{h_i} |
| 738 |
\end{eqnarray*} |
| 739 |
En ajoutant la relation précédente \eqref{eqnspline} il vient |
| 740 |
\begin{eqnarray*} |
| 741 |
f'''_i&=&\frac{f''_{i+1}-f''_i}{h_i} \quad 0\le i \le n-1 |
| 742 |
\end{eqnarray*} |
| 743 |
\item Continuité de la fonction pour les $n-1$ points intérieurs et le point final |
| 744 |
\begin{eqnarray*} |
| 745 |
p_{i+1}(x_{i+1})&=&f(x_{i+1})=f_{i+1} \quad 0\le i \le n-1\\ |
| 746 |
&=&f_i+f'_i(x-x_i)+\frac{f''_i}{2!}(x-x_i)^2+\frac{f'''_i}{3!}(x-x_i)^3 \quad 0\le i \le n-1\\ |
| 747 |
&=&f_i+f'_ih_i+\frac{f''_i}{2}h_i^2+\frac{f'''_i}{6}h_i^3 \\ |
| 748 |
h_if'_i&=&f_{i+1}-f_i-\frac{f''_i}{2}h_i^2-\frac{f'''_i}{6}h_i^3 \\ |
| 749 |
f'_i&=&\frac{f_{i+1}-f_i}{h_i}-\frac{f''_i}{2}h_i-\frac{f'''_i}{6}h_i^2 \\ |
| 750 |
f'_i&=&f[x_i.x_{i+1}]-\frac{f''_i}{2}h_i-\frac{f'''_i}{6}h_i^2 \\ |
| 751 |
f'_i&=&f[x_i.x_{i+1}]-\frac{f''_i}{2}h_i-\frac{\frac{f''_{i+1}-f''_i}{h_i}}{6}h_i^2 \\ |
| 752 |
f'_i&=&f[x_i.x_{i+1}]-\frac{f''_i}{3}h_i-\frac{f''_{i+1}}{6}h_i \\ |
| 753 |
\end{eqnarray*} |
| 754 |
\item Continuité de la dérivée première pour les $n-1$ points intérieurs |
| 755 |
\begin{eqnarray*} |
| 756 |
p'_i(x_{i+1})&=& p'_{i+1}(x_{i+1}) \quad 0\le i \le n-2\\ |
| 757 |
f'_i+(x_{i+1}-x_i)f''_i+(x_{i+1}-x_i)^2\frac{f'''_i}{2}&=&f'_{i+1}\\ |
| 758 |
f'_i+h_i f''_i+h_i^2\frac{f'''_i}{2}&=&f'_{i+1}\\ |
| 759 |
f[x_i.x_{i+1}]-\frac{f''_i}{3}h_i-\frac{f''_{i+1}}{6}h_i+h_i f''_i+h_i^2\frac{f'''_i}{2}&=&f[x_{i+1},x_{i+2}]-\frac{f''_{i+1}}{3}h_{i+1}-\frac{f''_{i+2}}{6}h_{i+1}\\ |
| 760 |
f[x_i.x_{i+1}]-\frac{f''_i}{3}h_i-\frac{f''_{i+1}}{6}h_i+h_i f''_i+h_i^2\frac{\frac{f''_{i+1}-f''_i}{h_i}}{2}&=&f[x_{i+1},x_{i+2}]-\frac{f''_{i+1}}{3}h_{i+1}-\frac{f''_{i+2}}{6}h_{i+1}\\ |
| 761 |
f[x_i.x_{i+1}]-\frac{f''_i}{3}h_i-\frac{f''_{i+1}}{6}h_i+h_i f''_i+h_i\frac{f''_{i+1}-f''_i}{2}&=&f[x_{i+1},x_{i+2}]-\frac{f''_{i+1}}{3}h_{i+1}-\frac{f''_{i+2}}{6}h_{i+1}\\ |
| 762 |
h_if''_i+2(h_i+h_{i+1})f''_{i+1}+h_{i+1}f''_{i+2}&=&6f[x_{i+1},x_{i+2}]-6f[x_{i},x_{i+1}]\\ |
| 763 |
\frac{h_i}{h_i+h_{i+1}}f''_i+2f''_{i+1}+\frac{h_{i+1}}{h_i+h_{i+1}}f''_{i+2}&=&\frac{6f[x_{i+1},x_{i+2}]-6f[x_{i},x_{i+1}]}{h_i+h_{i+1}}\\ |
| 764 |
\frac{h_i}{h_i+h_{i+1}}f''_i+2f''_{i+1}+\frac{h_{i+1}}{h_i+h_{i+1}}f''_{i+2}&=&6f[x_i,x_{i+1},x_{x+2}]\\ |
| 765 |
\end{eqnarray*} |
| 766 |
\end{itemize} |
| 767 |
On obtient ainsi $n-1$ équations pour les $n+1$ coefficients $f''_i$. Pour les deux autres équations on fixe la courbure aux deux extrémités : $f''_0=a$ et $f''_n=b$. |
| 768 |
\\Si $a=b=0$ on parle de spline cubique naturelle. |
| 769 |
\\ On aboutit alors au système suivant |
| 770 |
|
| 771 |
\begin{eqnarray*} |
| 772 |
\begin{pmatrix} |
| 773 |
1 & 0 & 0 & 0 & ... & 0\\ |
| 774 |
\frac{h_0}{h_0+h_1} & 2 & \frac{h_1}{h_0+h_1} & 0 & ... & 0\\ |
| 775 |
0 &\frac{h_1}{h_1+h_2} & 2 & \frac{h_2}{h_1+h_2} & ... & 0\\ |
| 776 |
& & & &\vdots & &\\ |
| 777 |
0 &0 & 0 & 0 & ... & \frac{h_{n-1}}{h_{n-2}+h_{n-1}}\\ |
| 778 |
0 & 0 & 0 & 0 & ... & 1\\ |
| 779 |
\end{pmatrix} |
| 780 |
\begin{pmatrix} |
| 781 |
f''_0\\ |
| 782 |
f''_1\\ |
| 783 |
f''_2\\ |
| 784 |
\vdots\\ |
| 785 |
f''_{n-1}\\ |
| 786 |
f''_n\\ |
| 787 |
\end{pmatrix} |
| 788 |
= |
| 789 |
\begin{pmatrix} |
| 790 |
a\\ |
| 791 |
6f[x_0,x_1,x_2]\\ |
| 792 |
6f[x_1,x_2,x_3]\\ |
| 793 |
\vdots\\ |
| 794 |
6f[x_{n-2},x_{n-1},x_n]\\ |
| 795 |
b\\ |
| 796 |
\end{pmatrix} |
| 797 |
\end{eqnarray*} |
| 798 |
|
| 799 |
Pour finir les $f''_i$ sont solutions de ce système tridiagonal avec pivot toujours différent de $0$ et les autres inconnues sont |
| 800 |
\begin{eqnarray*} |
| 801 |
f_i&=&f(x_i)=y_i\\ |
| 802 |
f'_i&=&f[x_i.x_{i+1}]-\frac{f''_i}{3}h_i-\frac{f''_{i+1}}{6}h_i\\ |
| 803 |
f'''_i&=&\frac{f''_{i+1}-f''_i}{h_i}\\ |
| 804 |
p_i(x)&=&f_i+f'_i(x-x_i)+\frac{f''_i}{2!}(x-x_i)^2+\frac{f'''_i}{3!}(x-x_i)^3\\ |
| 805 |
avec\quad 0 &\le& i \le n-1 |
| 806 |
\end{eqnarray*} |
| 807 |
\\ |
| 808 |
\\ |
| 809 |
Exemple : interpolation d'une spline cubique naturelle pour les points $(1,1),(2,9),(4,2),(5,11)$ |
| 810 |
\\ |
| 811 |
\\ |
| 812 |
On construit d'abord la table des différences divisées \\ \\ |
| 813 |
\begin{tabular}{|r|r|l|l|l|} |
| 814 |
\hline |
| 815 |
$x_i$ & $f(x_i)$ & $f[x_i,x_{i+1}]$ & $f[x_i,x_{i+1},x_{i+2}]$ & $h_i$ \\ |
| 816 |
\hline |
| 817 |
$1$ & $1$ & & & $1$ \\ |
| 818 |
& & $\frac{9-1}{2-1}=8 $ & & \\ |
| 819 |
$2$ & $9$ & & $\frac{\frac{-7}{2}-8}{4-1}=\frac{-23}{6}$ & $2$ \\ |
| 820 |
& & $\frac{2-9}{4-2}=\frac{-7}{2}$ & & \\ |
| 821 |
$4$ & $2$ & & $\frac{9-\frac{-7}{2}}{5-2}=\frac{25}{6}$ & $1$ \\ |
| 822 |
& & $\frac{11-2}{5-4}=9 $ & & \\ |
| 823 |
$5$ & $11$ & & & \\ |
| 824 |
|
| 825 |
\hline |
| 826 |
\end{tabular} |
| 827 |
\\ |
| 828 |
\\ |
| 829 |
On peut ensuite écrire le système : |
| 830 |
\\ |
| 831 |
\begin{eqnarray*} |
| 832 |
\begin{pmatrix} |
| 833 |
1 & 0 & 0 & 0 \\ |
| 834 |
\frac{1}{3} & 2 & \frac{2}{3} & 0 & \\ |
| 835 |
0 &\frac{2}{3} & 2 & \frac{1}{3} \\ |
| 836 |
0 & 0 & 0 & 1\\ |
| 837 |
\end{pmatrix} |
| 838 |
\begin{pmatrix} |
| 839 |
f''_0\\ |
| 840 |
f''_1\\ |
| 841 |
f''_2\\ |
| 842 |
f''_3\\ |
| 843 |
\end{pmatrix} |
| 844 |
= |
| 845 |
\begin{pmatrix} |
| 846 |
0\\ |
| 847 |
6\frac{-23}{6}\\ |
| 848 |
6\frac{25}{6}\\ |
| 849 |
0\\ |
| 850 |
\end{pmatrix} |
| 851 |
= |
| 852 |
\begin{pmatrix} |
| 853 |
0\\ |
| 854 |
-23\\ |
| 855 |
25\\ |
| 856 |
0\\ |
| 857 |
\end{pmatrix} |
| 858 |
\end{eqnarray*} |
| 859 |
La solution de ce système est |
| 860 |
\begin{eqnarray*} |
| 861 |
\begin{pmatrix} |
| 862 |
f''_0\\ |
| 863 |
f''_1\\ |
| 864 |
f''_2\\ |
| 865 |
f''_3\\ |
| 866 |
\end{pmatrix} |
| 867 |
= |
| 868 |
\begin{pmatrix} |
| 869 |
0\\ |
| 870 |
\frac{-141}{8}\\ |
| 871 |
\frac{147}{8}\\ |
| 872 |
0\\ |
| 873 |
\end{pmatrix} |
| 874 |
\end{eqnarray*} |
| 875 |
L'interpolation est donc |
| 876 |
\begin{itemize} |
| 877 |
\item pour $x \in [1,2]$ |
| 878 |
\begin{eqnarray*} |
| 879 |
f_0&=&1\\ |
| 880 |
f'_0&=&f[x_0,x_1]-ho\frac{f''_0}{3}-h_0\frac{f''_1}{6}=8-1\frac{0}{3}-1\frac{\frac{-141}{8}}{6}=\frac{175}{16}\\ |
| 881 |
f''_0&=&0\\ |
| 882 |
f'''_0&=&\frac{f''_1-f''_0}{h_0}=\frac{\frac{-141}{8}-0}{1}=\frac{-141}{8}\\ |
| 883 |
p_0(x)&=&1+\frac{175}{16}(x-1)+\frac{0}{2}(x-1)^2+\frac{-141}{6*8}(x-1)^3 |
| 884 |
\end{eqnarray*} |
| 885 |
\item pour $x \in [2,4]$ |
| 886 |
\begin{eqnarray*} |
| 887 |
f_1&=&9\\ |
| 888 |
f'_1&=&f[x_1,x_2]-h1\frac{f''_1}{3}-h_1\frac{f''_2}{6}=\frac{-7}{2}-2\frac{\frac{-141}{8}}{3}-2\frac{\frac{147}{8}}{6}=\frac{17}{8}\\ |
| 889 |
f''_1&=&\frac{-141}{8}\\ |
| 890 |
f'''_1&=&\frac{f''_2-f''_1}{h_1}=\frac{\frac{147}{8}-\frac{-141}{8}}{2}=18\\ |
| 891 |
p_1(x)&=&9+\frac{17}{8}(x-2)+\frac{-141}{2*8}(x-2)^2+\frac{18}{6}(x-2)^3 |
| 892 |
\end{eqnarray*} |
| 893 |
\item pour $x \in [4,5]$ |
| 894 |
\begin{eqnarray*} |
| 895 |
f_2&=&2\\ |
| 896 |
f'_2&=&f[x_2,x_3]-h_2\frac{f''_2}{3}-h_2\frac{f''_3}{6}=9-1\frac{\frac{147}{8}}{3}-1\frac{0}{6}=\frac{23}{8}\\ |
| 897 |
f''_2&=&\frac{147}{8}\\ |
| 898 |
f'''_2&=&\frac{f''_3-f''_2}{h_2}=\frac{0-\frac{147}{8}}{1}=\frac{-147}{8}\\ |
| 899 |
p_2(x)&=&2+\frac{23}{8}(x-4)+\frac{147}{2*8}(x-4)^2+\frac{-147}{8*6}(x-4)^3 |
| 900 |
\end{eqnarray*} |
| 901 |
|
| 902 |
\end{itemize} |
| 903 |
|
| 904 |
\subsection{Les splines paramétrées} |
| 905 |
\subsubsection{Construction} |
| 906 |
En CAO, souvent on utilise des splines pour faire passer une courbe par une série de points. Ces courbes ne sont pas de la forme $y=f(x)$ ce qui fait que les méthodes vues ne sont pas directement utilisables. |
| 907 |
\\Le problème est de faire passer une courbe par les points $(x_0,y_0,z_0),...,(x_n,y_n,z_n)$. Pour cela, nous allons transformer ce problème en un problème paramétrique, la courbe est définie par un paramètre $t$. |
| 908 |
\\Ainsi les points les points s'écrivent $(x(t_0),y(t_0),z(t_0)),...,(x(t_n),y(t_n),z(t_n))$. On obtient ainsi une courbe paramétrée $C(t)=\overrightarrow{x}[x(t),y(t),z(t)]$ |
| 909 |
\\ On construit une série de paramètre $t$ appelé vecteur noeud ou ``knot'' et on réalise une interpolation dans chacune des directions de l'espace pour déterminer les interpolations de $x(t),y(t),z(t)$. |
| 910 |
\\ Pour la série $t$, on a une infinité de choix. Les plus courant sont \begin{itemize} |
| 911 |
\item $t_i=i$. |
| 912 |
\item $t_0=0$ et $t_i=t_{i-1}+\| \overrightarrow{x_i}-\overrightarrow{x_{i-1}}\|_2$ |
| 913 |
\end{itemize} |
| 914 |
|
| 915 |
Exemple : Tracer la courbe qui passe les points $(1,0)$,$(\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2})$,$(0,1)$,$(\frac{-\sqrt{2}}{2},\frac{\sqrt{2}}{2})$,$(-1,0)$ ,$(\frac{-\sqrt{2}}{2},\frac{-\sqrt{2}}{2})$,$(0.-1)$,$(\frac{\sqrt{2}}{2},\frac{-\sqrt{2}}{2})$ et $(1,0)$. |
| 916 |
\\ |
| 917 |
\\On construit un vecteur de $t=[0$ $1$ $2$ $3$ $4$ $5$ $6$ $7$ $8]$ et on réalise l'interpolation $x(t)$ et $(y(t)$ pour obtenir la figure suivante |
| 918 |
\begin{center} |
| 919 |
\includegraphics[width=12cm,bb=0 0 499 347]{./splineex.jpg} |
| 920 |
% splineex.jpg: 665x463 pixel, 96dpi, 17.59x12.25 cm, bb=0 0 499 347 |
| 921 |
\end{center} |
| 922 |
|
| 923 |
Le résultat montre que le cercle n'est vraiment un cercle parfait. |
| 924 |
\subsubsection{Exemple de modification des splines cubiques pour les courbes fermées} |
| 925 |
Pour que la courbe précédente paraisse bien lisse au point de départ et au point d'arrivée, il faut utiliser des relations pour fixer le début et la fin de la courbe au lieu de prendre des splines cubiques naturelles. |
| 926 |
Les conditions supplémentaires à imposer sont |
| 927 |
\begin{eqnarray*} |
| 928 |
\left \{ |
| 929 |
\begin{array}{l} |
| 930 |
P'_0(x_0)=P'_{n-1}(x_n)\\ |
| 931 |
P''_0(x_0)=P''_{n-1}(x_n)\\ |
| 932 |
\end{array} |
| 933 |
\right. |
| 934 |
\end{eqnarray*} |
| 935 |
\begin{eqnarray*} |
| 936 |
\left \{ |
| 937 |
\begin{array}{l} |
| 938 |
f'_0=f'_{n-1}+h_{n-1}f''_{n-1}+\frac{h^2_{n-1}}{2}f'''_{n-1}\\ |
| 939 |
f''_0=f''_{n-1}+h_{n-1}f'''_{n-1}\\ |
| 940 |
\end{array} |
| 941 |
\right. |
| 942 |
\end{eqnarray*} |
| 943 |
\begin{eqnarray*} |
| 944 |
\left \{ |
| 945 |
\begin{array}{l} |
| 946 |
f[x_0,x_1]-h_0\frac{f''_0}{3}-h_0\frac{f''_1}{6}=f[x_{n-1},x_n]-h_{n-1}\frac{f''_{n-1}}{3}-h_{n-1}\frac{f''_{n+1}}{6}+h_{n-1}f''_{n-1}+\frac{h^2_{n-1}}{2}\frac{f''_n-f''_{n-1}}{h_{n-1}}\\ |
| 947 |
f''_0=f''_{n-1}+h_{n-1}\frac{f''_n-f''_{n-1}}{h_{n-1}}\\ |
| 948 |
\end{array} |
| 949 |
\right. |
| 950 |
\end{eqnarray*} |
| 951 |
\begin{eqnarray*} |
| 952 |
\left \{ |
| 953 |
\begin{array}{l} |
| 954 |
h_0\frac{f''_0}{3}+h_0\frac{f''_1}{6}+h_{n-1}\frac{f''_{n-1}}{6}+h_{n-1}\frac{f''_{n}}{3}=f[x_0,x_1]-f[x_{n-1},x_n]\\ |
| 955 |
f''_0-f''_{n}=0\\ |
| 956 |
\end{array} |
| 957 |
\right. |
| 958 |
\end{eqnarray*} |
| 959 |
En remplaçant la première et la dernière équations par ces équations dans le système, nous obtenons une courbe parfaitement lisse. Dans ce cas le système n'est plus tridiagonal l'algorithme LU fourni en annexe ne fonctionne plus. Il faut utiliser un algorithme de LU plus général comme celui vu au chapitre précédent. |
| 960 |
Le résultat donne la courbe suivante : |
| 961 |
\begin{center} |
| 962 |
\begin{center} |
| 963 |
\includegraphics[width=12cm,bb=0 0 929 604]{./splineex2.jpg} |
| 964 |
% splineex2.jpg: 1238x805 pixel, 96dpi, 32.76x21.30 cm, bb=0 0 929 604 |
| 965 |
\end{center} |
| 966 |
\end{center} |
| 967 |
\begin{encadre}{À retenir} |
| 968 |
La compréhension de la différence entre l'approximation et l'interpolation est fondamentale. A partir de cette différence, il est nécessaire d'être capable d'approximer ou d'interpoler une série de points de mesure. |
| 969 |
\end{encadre} |
