| 1 |
\section{Mise en situation} |
| 2 |
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 : \\ |
| 3 |
\\ |
| 4 |
\begin{tabular}{|r|r r r r r r r r r r|} |
| 5 |
\hline |
| 6 |
t(s) & 0 & 5 & 10 &15 & 20 & 25 & 30 & 35 & 40 & 45\\ |
| 7 |
v(km/h) & 55 &60 &58 & 54& 55 &60 &54 &57 &52 &49 \\ |
| 8 |
\hline |
| 9 |
\end{tabular} |
| 10 |
\\ |
| 11 |
Ce tableau peut être représenté par la figure suivante. |
| 12 |
|
| 13 |
|
| 14 |
\begin{figure}[h] |
| 15 |
|
| 16 |
\begin{center} |
| 17 |
\includegraphics[width=10cm,bb=0 0 742 513]{./interpolationexemple.jpg} |
| 18 |
% interpolationexemple.jpg: 742x513 pixel, 72dpi, 26.18x18.10 cm, bb=0 0 742 513 |
| 19 |
|
| 20 |
|
| 21 |
\caption{Tracé du relevé de points} |
| 22 |
\end{center} |
| 23 |
|
| 24 |
\end{figure} |
| 25 |
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. |
| 26 |
\\ |
| 27 |
|
| 28 |
\huge\danger\hspace{1cm}\normalsize Il faut bien faire la différence entre les méthodes d'interpolation et les méthodes d'approximation.\\ |
| 29 |
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. |
| 30 |
\\Nous nous limitons dans ce cours aux méthodes d'interpolation. |
| 31 |
|
| 32 |
|
| 33 |
\section{Interpolation par un polynôme} |
| 34 |
L'idée de base est de construire un polynôme d'interpolation (ou de collocation) qui passe par les points donnés. |
| 35 |
\\ |
| 36 |
Un polynôme de degré $n$ s'écrit |
| 37 |
\begin{eqnarray*} |
| 38 |
P_n(x)&=&a_0+a_1x+...+a_nx^n\\ |
| 39 |
avec \quad a_n&\neq&0 |
| 40 |
\end{eqnarray*} |
| 41 |
$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$. |
| 42 |
Il existe un seul polynôme de degré $n$ passant par $n+1$ points. |
| 43 |
|
| 44 |
Démonstration : |
| 45 |
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$ |
| 46 |
\begin{eqnarray*} |
| 47 |
d_n(x)=P_{1n}(x)-P_{2n}(x)\\ |
| 48 |
\end{eqnarray*} |
| 49 |
On calcule ensuite la valeur de $d_n(x)$ pour chaque $n+1$ points d'interpolation $(x_i,y_i)$. |
| 50 |
\begin{eqnarray*} |
| 51 |
d_n(x_i)&=&P_{1n}(x_i)-P_{2n}(x_i)\\ |
| 52 |
&=&P_{1n}(x_i)-P_{2n}(x_i)\\ |
| 53 |
&=&y_i-y_i\\ |
| 54 |
&=&0\\ |
| 55 |
\end{eqnarray*} |
| 56 |
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. |
| 57 |
|
| 58 |
\subsection{Méthode de la matrice de Vandermonde} |
| 59 |
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. |
| 60 |
En écrivant que le point $(x_i,y_i)$ appartient au polynôme on a |
| 61 |
\begin{eqnarray*} |
| 62 |
P_n(x_i)=a_0+a_1x_i+...+a_nx_i^n=y_i |
| 63 |
\end{eqnarray*} |
| 64 |
et on obtient le système |
| 65 |
\begin{eqnarray*} |
| 66 |
\begin{pmatrix} |
| 67 |
1 & x_0 & ... & x_0^n\\ |
| 68 |
1 & x_1 & ... & x_1^n\\ |
| 69 |
& & \vdots&\\ |
| 70 |
1 & x_n & ... & x_n^n\\ |
| 71 |
\end{pmatrix} |
| 72 |
\begin{pmatrix} |
| 73 |
a_0\\ |
| 74 |
a_1\\ |
| 75 |
\vdots\\ |
| 76 |
a_n\\ |
| 77 |
\end{pmatrix} |
| 78 |
= |
| 79 |
\begin{pmatrix} |
| 80 |
y_0\\ |
| 81 |
y_1\\ |
| 82 |
\vdots\\ |
| 83 |
y_n\\ |
| 84 |
\end{pmatrix} |
| 85 |
\end{eqnarray*} |
| 86 |
La matrice $\begin{pmatrix} |
| 87 |
1 & x_0 & ... & x_0^n\\ |
| 88 |
1 & x_1 & ... & x_1^n\\ |
| 89 |
& & \vdots&\\ |
| 90 |
1 & x_n & ... & x_n^n\\ |
| 91 |
\end{pmatrix} |
| 92 |
$ s'appelle la matrice de Vandermonde. |
| 93 |
Il suffit de résoudre ce système pour obtenir le polynôme. |
| 94 |
|
| 95 |
Exemple : Calculer le polynôme d'interpolation qui passent par les points $(0,1)$,$(1,2)$,$(2,9)$ et $(3,28)$. |
| 96 |
\\Nous avons 4 points, nous devons donc déterminer $P_3(x)$. Dans ce cas le système s'écrit |
| 97 |
\begin{eqnarray*} |
| 98 |
\begin{pmatrix} |
| 99 |
1 & 0 & 0 & 0\\ |
| 100 |
1 & 1 & 1 & 1\\ |
| 101 |
1 & 2 & 4 & 8\\ |
| 102 |
1 & 3 & 9 & 27\\ |
| 103 |
\end{pmatrix} |
| 104 |
\begin{pmatrix} |
| 105 |
a_0\\ |
| 106 |
a_1\\ |
| 107 |
a_2\\ |
| 108 |
a_3\\ |
| 109 |
\end{pmatrix} |
| 110 |
= |
| 111 |
\begin{pmatrix} |
| 112 |
1\\ |
| 113 |
2\\ |
| 114 |
9\\ |
| 115 |
28\\ |
| 116 |
\end{pmatrix} |
| 117 |
\end{eqnarray*} |
| 118 |
La solution est |
| 119 |
\begin{eqnarray*} |
| 120 |
\begin{pmatrix} |
| 121 |
a_0\\ |
| 122 |
a_1\\ |
| 123 |
a_2\\ |
| 124 |
a_3\\ |
| 125 |
\end{pmatrix} |
| 126 |
= |
| 127 |
\begin{pmatrix} |
| 128 |
1\\ |
| 129 |
0\\ |
| 130 |
0\\ |
| 131 |
1\\ |
| 132 |
\end{pmatrix} |
| 133 |
\end{eqnarray*} |
| 134 |
et le polynôme d'interpolation s'écrit $P_3(x)=1+x^3$. |
| 135 |
\begin{figure}[h] |
| 136 |
|
| 137 |
\begin{center} |
| 138 |
\begin{center} |
| 139 |
\includegraphics[width=12cm,bb=0 0 746 481]{./interpolationex.jpg} |
| 140 |
% interpolationex.jpg: 995x641 pixel, 96dpi, 26.33x16.96 cm, bb=0 0 746 481 |
| 141 |
\end{center} |
| 142 |
|
| 143 |
|
| 144 |
\caption{Tracé de l'interpolation des points $(0,1),(1,2),(2,9),(3,28)$} |
| 145 |
\end{center} |
| 146 |
|
| 147 |
\end{figure} |
| 148 |
Cette méthode apparaît correcte pour obtenir le résultat souhaité. Cependant elle a des désavantages majeurs : |
| 149 |
\begin{itemize} |
| 150 |
\item Elle nécessite une résolution d'un système linéaire ce qui peut s'avérer coûteux en temps CPU. |
| 151 |
\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. |
| 152 |
\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. |
| 153 |
\end{itemize} |
| 154 |
|
| 155 |
\subsection{Méthode de Lagrange} |
| 156 |
|
| 157 |
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. |
| 158 |
\\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 |
| 159 |
\begin{eqnarray*} |
| 160 |
L_i(x_i)=1\quad et\quad L_i(x_j)=0\quad pour \quad 0\le i\le n |
| 161 |
\end{eqnarray*} |
| 162 |
Cette définition conduit à la définition de $n+1$ polynômes de degré $n$. |
| 163 |
\\Nous avons alors |
| 164 |
\begin{eqnarray*} |
| 165 |
P_n(x)=\sum_{i=0}^ny_iL_i(x) |
| 166 |
\end{eqnarray*} |
| 167 |
\\Démonstration |
| 168 |
\begin{eqnarray*} |
| 169 |
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 |
| 170 |
\end{eqnarray*} |
| 171 |
|
| 172 |
Construction des polynômes $L$: |
| 173 |
\begin{itemize} |
| 174 |
\item degré 1 : polynôme passant par les point $(x_0,y_0)$ et $(x_1,y_1)$. |
| 175 |
\begin{eqnarray*} |
| 176 |
\left. |
| 177 |
\begin{array}{l} |
| 178 |
L_0(x_0)=1\\ |
| 179 |
L_0(x_1)=0\\ |
| 180 |
\end{array} |
| 181 |
\right \} |
| 182 |
L_0(x)=\frac{x-x_1}{x_0-x_1}\\ |
| 183 |
\left. |
| 184 |
\begin{array}{l} |
| 185 |
L_1(x_0)=0\\ |
| 186 |
L_1(x_1)=1\\ |
| 187 |
\end{array} |
| 188 |
\right \} |
| 189 |
L_1(x)=\frac{x-x_0}{x_1-x_0}\\ |
| 190 |
P_1(x)=y_0\frac{x-x_1}{x_0-x_1}+y_1\frac{x-x_0}{x_1-x_0} |
| 191 |
\end{eqnarray*} |
| 192 |
\item degré 2 : polynôme passant par les point $(x_0,y_0)$, $(x_1,y_1)$ et $(x_2,y_2)$. |
| 193 |
\begin{eqnarray*} |
| 194 |
\left. |
| 195 |
\begin{array}{l} |
| 196 |
L_0(x_0)=1\\ |
| 197 |
L_0(x_1)=0\\ |
| 198 |
L_0(x_2)=0\\ |
| 199 |
\end{array} |
| 200 |
\right \} |
| 201 |
L_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}\\ |
| 202 |
\left. |
| 203 |
\begin{array}{l} |
| 204 |
L_1(x_0)=0\\ |
| 205 |
L_1(x_1)=1\\ |
| 206 |
L_1(x_2)=0\\ |
| 207 |
\end{array} |
| 208 |
\right \} |
| 209 |
L_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}\\ |
| 210 |
\left. |
| 211 |
\begin{array}{l} |
| 212 |
L_2(x_0)=0\\ |
| 213 |
L_2(x_1)=0\\ |
| 214 |
L_2(x_2)=1\\ |
| 215 |
\end{array} |
| 216 |
\right \} |
| 217 |
L_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}\\ |
| 218 |
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)} |
| 219 |
\end{eqnarray*} |
| 220 |
\item degré $n$ |
| 221 |
\end{itemize} |
| 222 |
|
| 223 |
\begin{eqnarray*} |
| 224 |
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)} |
| 225 |
\end{eqnarray*} |
| 226 |
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)$. |
| 227 |
\\On calcule les polynômes $L$ : |
| 228 |
\begin{eqnarray*} |
| 229 |
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)\\ |
| 230 |
L_1(x)&=&\frac{(x-0)(x-2)(x-3)}{(1-0)(1-2)(1-3)}=\frac{1}{2}(x^3-5x^2+6x)\\ |
| 231 |
L_2(x)&=&\frac{(x-0)(x-1)(x-3)}{(2-0)(2-1)(2-3)}=-\frac{1}{2}(x^3-4x^2+3x)\\ |
| 232 |
L_3(x)&=&\frac{(x-0)(x-1)(x-2)}{(3-0)(3-1)(3-2)}=\frac{1}{6}(x^3-3x^2+2x)\\ |
| 233 |
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)\\ |
| 234 |
&=&x^3+1 |
| 235 |
\end{eqnarray*} |
| 236 |
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. |
| 237 |
|
| 238 |
\subsection{Méthode de Newton} |
| 239 |
On écrit le polynôme $P_n(x)$ sous la forme |
| 240 |
\begin{eqnarray*} |
| 241 |
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}) |
| 242 |
\end{eqnarray*} |
| 243 |
et on identifie les $a_i$ en calculant successivement $P_n(x_i)=y_i$ |
| 244 |
\begin{eqnarray*} |
| 245 |
P_n(x_0)&=&a_0=y_0=f(x_0)\\ |
| 246 |
P_n(x_1)&=&a_0+a_1(x_1-x_0)=y_1\\ |
| 247 |
& &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}\\ |
| 248 |
\end{eqnarray*} |
| 249 |
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]$\\ |
| 250 |
\begin{eqnarray*} |
| 251 |
P_n(x_2)&=&a_0+a_1(x_2-x_0)+a_2(x_2-x_0)(x_2-x_1)=y_2\\ |
| 252 |
& &f(x_0)+f[x_1,x_0](x_2-x_0)+a_2(x_2-x_0)(x_2-x_1)=f(x_2)\\ |
| 253 |
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)\\ |
| 254 |
&=&\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)\\ |
| 255 |
&=&\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)\\ |
| 256 |
&=&\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)\\ |
| 257 |
&=&\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)\\ |
| 258 |
&=&\frac{1}{x_2-x_0}\left(f[x_1,x_2]-f[x_0,x_1]\right)\\ |
| 259 |
\end{eqnarray*} |
| 260 |
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]$ |
| 261 |
|
| 262 |
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 |
| 263 |
\begin{eqnarray*} |
| 264 |
a_i=f[x_0,...,x_i] |
| 265 |
\end{eqnarray*} |
| 266 |
On évalue le polynôme d'interpolation en construisant la table des différences divisées.\\ |
| 267 |
\begin{tabular}{|r|r|r|r|r|r|} |
| 268 |
\hline |
| 269 |
$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]$ \\ |
| 270 |
\hline |
| 271 |
$x_0$ & $f(x_0)=a_0$ & & & & \\ |
| 272 |
& & $f[x_0,x_1]=a_1$ & & & \\ |
| 273 |
$x_1$ & $f(x_1)$ & & $f[x_0,x_1,x_2]=a_2$ & & \\ |
| 274 |
& & $f[x_1,x_2]$ & & ... & $f[x_1,...,x_n]=a_n$ \\ |
| 275 |
$x_2$ & $f(x_2)$ & & $f[x_1,x_2,x_3]$ & & \\ |
| 276 |
& & $f[x_2,x_3]$ & & & \\ |
| 277 |
$x_3$ & $f(x_3)$ & & & & \\ |
| 278 |
|
| 279 |
\hline |
| 280 |
\end{tabular}\\ |
| 281 |
\\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 \\ |
| 282 |
\\ |
| 283 |
\begin{tabular}{|r|r|l|l|l|} |
| 284 |
\hline |
| 285 |
$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}]$ \\ |
| 286 |
\hline |
| 287 |
$0$ & $1$ & & & \\ |
| 288 |
& & $\frac{2-1}{1-0}=1 $ & & \\ |
| 289 |
$1$ & $2$ & & $\frac{7-1}{2-0}=3$ & \\ |
| 290 |
& & $\frac{9-2}{2-1}=7$ & &$\frac{6-3}{3-0}=1$ \\ |
| 291 |
$2$ & $9$ & & $\frac{19-7}{3-1}=6$ & \\ |
| 292 |
& & $\frac{28-9}{3-2}=19 $ & & \\ |
| 293 |
$3$ & $28$ & & & \\ |
| 294 |
|
| 295 |
\hline |
| 296 |
\end{tabular} |
| 297 |
\\ |
| 298 |
\\On calcule alors le polynôme d'interpolation |
| 299 |
\begin{eqnarray*} |
| 300 |
P_3(x)&=&1+1(x-0)+3(x-0)(x-1)+1(x-0)(x-1)(x-2)\\ |
| 301 |
&=&x^3+1\\ |
| 302 |
\end{eqnarray*} |
| 303 |
on remarque que |
| 304 |
\begin{eqnarray*} |
| 305 |
P_2(x)&=&1+1(x-0)+3(x-0)(x-1)\\ |
| 306 |
&=&3x^2-2x+1\\ |
| 307 |
\end{eqnarray*} |
| 308 |
ou que |
| 309 |
\begin{eqnarray*} |
| 310 |
P_3(x)&=&P_2(x)+1(x-0)(x-1)(x-2)\\ |
| 311 |
\end{eqnarray*} |
| 312 |
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. |
| 313 |
|
| 314 |
|
| 315 |
\subsection{Erreur d'interpolation} |
| 316 |
Soit $E_n(x)$ l'erreur d'interpolation alors |
| 317 |
\begin{eqnarray*} |
| 318 |
E_n(x)=f(x)-P_n(x) |
| 319 |
\end{eqnarray*} |
| 320 |
Puisque on fait de l'interpolation, on a |
| 321 |
\begin{eqnarray*} |
| 322 |
E_n(x_i)=0 |
| 323 |
\end{eqnarray*} |
| 324 |
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 |
| 325 |
\\ Il existe $\zeta (x)\in ]x_0,x_n[$ tel que |
| 326 |
\begin{eqnarray*} |
| 327 |
E_n(x)=\frac{f^{(n+1)}\zeta (x)}{(n+1)!}(x-x_0)...(x-x_n) |
| 328 |
\end{eqnarray*} |
| 329 |
|
| 330 |
\begin{itemize} |
| 331 |
\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. |
| 332 |
\item L'erreur est nulle aux points d'interpolation. |
| 333 |
\item L'erreur est petite autour des points d'interpolation |
| 334 |
\item L'erreur est un polynôme de degré $n$. 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. |
| 335 |
\end{itemize} |
| 336 |
|
| 337 |
|
| 338 |
|
| 339 |
|
| 340 |
\section{Interpolation par des polynômes par morceau} |
| 341 |
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. |
| 342 |
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. |
| 343 |
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$. |
| 344 |
\subsection{Les splines cubiques} |
| 345 |
Soit $n+1$ points d'interpolation noté $(x_i,y_i=f(x_i)=f_i)$ pour $0\le i \le n$. |
| 346 |
\\Pour les $n$ intervalles $[x_i,x_{i+1}]$ avec $0\le i \le n-1$ on pose |
| 347 |
\begin{eqnarray*} |
| 348 |
h_i&=&x_{i+1}-x_i\\ |
| 349 |
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\\ |
| 350 |
\end{eqnarray*} |
| 351 |
On a donc $4n$ coefficients à déterminer : $f_i,f'_i,f''_i,f'''_i$. |
| 352 |
\\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. |
| 353 |
Cette nouvelle inconnue peut s'exprimer en fonction des autres inconnues : |
| 354 |
\begin{eqnarray} |
| 355 |
\label{eqnspline} |
| 356 |
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} |
| 357 |
\end{eqnarray} |
| 358 |
Nous allons écrire maintenant les différentes conditions de régularité de l'interpolation : |
| 359 |
\begin{itemize} |
| 360 |
\item Nous faisons une interpolation : $p_i(x)=f(x_i)=f_i$ pour $0\le i \le n$ |
| 361 |
\item Continuité de la dérivée seconde pour les $n-1$ points intérieurs |
| 362 |
\begin{eqnarray*} |
| 363 |
p''_{i+1}(x_{i+1})&=&p''_{i}(x_{i+1}) \quad 0\le i \le n-2\\ |
| 364 |
f''_{i+1}&=&f''_i+f'''_i(x_{i+1}-x_i)=f''_i+f'''_ih_i\\ |
| 365 |
f'''_i&=&\frac{f''_{i+1}-f''_i}{h_i} |
| 366 |
\end{eqnarray*} |
| 367 |
En ajoutant la relation précédente \eqref{eqnspline} il vient |
| 368 |
\begin{eqnarray*} |
| 369 |
f'''_i&=&\frac{f''_{i+1}-f''_i}{h_i} \quad 0\le i \le n-1 |
| 370 |
\end{eqnarray*} |
| 371 |
\item Continuité de la fonction pour les $n-1$ points intérieurs et le point final |
| 372 |
\begin{eqnarray*} |
| 373 |
p_{i+1}(x_{i+1})&=&f(x_{i+1})=f_{i+1} \quad 0\le i \le n-1\\ |
| 374 |
&=&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\\ |
| 375 |
&=&f_i+f'_ih_i+\frac{f''_i}{2}h_i^2+\frac{f'''_i}{6}h_i^3 \\ |
| 376 |
h_if'_i&=&f_{i+1}-f_i-\frac{f''_i}{2}h_i^2-\frac{f'''_i}{6}h_i^3 \\ |
| 377 |
f'_i&=&\frac{f_{i+1}-f_i}{h_i}-\frac{f''_i}{2}h_i-\frac{f'''_i}{6}h_i^2 \\ |
| 378 |
f'_i&=&f[x_i.x_{i+1}]-\frac{f''_i}{2}h_i-\frac{f'''_i}{6}h_i^2 \\ |
| 379 |
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 \\ |
| 380 |
f'_i&=&f[x_i.x_{i+1}]-\frac{f''_i}{3}h_i-\frac{f''_{i+1}}{6}h_i \\ |
| 381 |
\end{eqnarray*} |
| 382 |
\item Continuité de la dérivée première pour les $n-1$ points intérieurs |
| 383 |
\begin{eqnarray*} |
| 384 |
p'_i(x_{i+1})&=& p'_{i+1}(x_{i+1}) \quad 0\le i \le n-2\\ |
| 385 |
f'_i+(x_{i+1}-x_i)f''_i+(x_{i+1}-x_i)^2\frac{f'''_i}{2}&=&f'_{i+1}\\ |
| 386 |
f'_i+h_i f''_i+h_i^2\frac{f'''_i}{2}&=&f'_{i+1}\\ |
| 387 |
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}\\ |
| 388 |
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}\\ |
| 389 |
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}\\ |
| 390 |
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}]\\ |
| 391 |
\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}}\\ |
| 392 |
\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}]\\ |
| 393 |
\end{eqnarray*} |
| 394 |
\end{itemize} |
| 395 |
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$. |
| 396 |
\\Si $a=b=0$ on parle de spline cubique naturelle. |
| 397 |
\\ On aboutit alors au système suivant |
| 398 |
|
| 399 |
\begin{eqnarray*} |
| 400 |
\begin{pmatrix} |
| 401 |
1 & 0 & 0 & 0 & ... & 0\\ |
| 402 |
\frac{h_0}{h_0+h_1} & 2 & \frac{h_1}{h_0+h_1} & 0 & ... & 0\\ |
| 403 |
0 &\frac{h_1}{h_1+h_2} & 2 & \frac{h_2}{h_1+h_2} & ... & 0\\ |
| 404 |
& & & &\vdots & &\\ |
| 405 |
0 &0 & 0 & 0 & ... & \frac{h_{n-1}}{h_{n-2}+h_{n-1}}\\ |
| 406 |
0 & 0 & 0 & 0 & ... & 1\\ |
| 407 |
\end{pmatrix} |
| 408 |
\begin{pmatrix} |
| 409 |
f''_0\\ |
| 410 |
f''_1\\ |
| 411 |
f''_2\\ |
| 412 |
\vdots\\ |
| 413 |
f''_{n-1}\\ |
| 414 |
f''_n\\ |
| 415 |
\end{pmatrix} |
| 416 |
= |
| 417 |
\begin{pmatrix} |
| 418 |
a\\ |
| 419 |
6f[x_0,x_1,x_2]\\ |
| 420 |
6f[x_1,x_2,x_3]\\ |
| 421 |
\vdots\\ |
| 422 |
6f[x_{n-2},x_{n-1},x_n]\\ |
| 423 |
b\\ |
| 424 |
\end{pmatrix} |
| 425 |
\end{eqnarray*} |
| 426 |
|
| 427 |
Pour finir les $f''_i$ sont solutions de ce système tridiagonal avec pivot toujours différent de $0$ et les autres inconnues sont |
| 428 |
\begin{eqnarray*} |
| 429 |
f_i&=&f(x_i)=y_i\\ |
| 430 |
f'_i&=&f[x_i.x_{i+1}]-\frac{f''_i}{3}h_i-\frac{f''_{i+1}}{6}h_i\\ |
| 431 |
f'''_i&=&\frac{f''_{i+1}-f''_i}{h_i}\\ |
| 432 |
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\\ |
| 433 |
avec\quad 0 &\le& i \le n-1 |
| 434 |
\end{eqnarray*} |
| 435 |
\\ |
| 436 |
\\ |
| 437 |
Exemple : interpolation d'une spline cubique naturelle pour les points $(1,1),(2,9),(4,2),(5,11)$ |
| 438 |
\\ |
| 439 |
\\ |
| 440 |
On construit d'abord la table des différences divisées \\ \\ |
| 441 |
\begin{tabular}{|r|r|l|l|l|} |
| 442 |
\hline |
| 443 |
$x_i$ & $f(x_i)$ & $f[x_i,x_{i+1}]$ & $f[x_i,x_{i+1},x_{i+2}]$ & $h_i$ \\ |
| 444 |
\hline |
| 445 |
$1$ & $1$ & & & $1$ \\ |
| 446 |
& & $\frac{9-1}{2-1}=8 $ & & \\ |
| 447 |
$2$ & $9$ & & $\frac{\frac{-7}{2}-8}{4-1}=\frac{-23}{6}$ & $2$ \\ |
| 448 |
& & $\frac{2-9}{4-2}=\frac{-7}{2}$ & & \\ |
| 449 |
$4$ & $2$ & & $\frac{9-\frac{-7}{2}}{5-2}=\frac{25}{6}$ & $1$ \\ |
| 450 |
& & $\frac{11-2}{5-4}=9 $ & & \\ |
| 451 |
$5$ & $11$ & & & \\ |
| 452 |
|
| 453 |
\hline |
| 454 |
\end{tabular} |
| 455 |
\\ |
| 456 |
\\ |
| 457 |
On peut ensuite écrire le système : |
| 458 |
\\ |
| 459 |
\begin{eqnarray*} |
| 460 |
\begin{pmatrix} |
| 461 |
1 & 0 & 0 & 0 \\ |
| 462 |
\frac{1}{3} & 2 & \frac{2}{3} & 0 & \\ |
| 463 |
0 &\frac{2}{3} & 2 & \frac{1}{3} \\ |
| 464 |
0 & 0 & 0 & 1\\ |
| 465 |
\end{pmatrix} |
| 466 |
\begin{pmatrix} |
| 467 |
f''_0\\ |
| 468 |
f''_1\\ |
| 469 |
f''_2\\ |
| 470 |
f''_3\\ |
| 471 |
\end{pmatrix} |
| 472 |
= |
| 473 |
\begin{pmatrix} |
| 474 |
0\\ |
| 475 |
6\frac{-23}{6}\\ |
| 476 |
6\frac{25}{6}\\ |
| 477 |
0\\ |
| 478 |
\end{pmatrix} |
| 479 |
= |
| 480 |
\begin{pmatrix} |
| 481 |
0\\ |
| 482 |
-23\\ |
| 483 |
25\\ |
| 484 |
0\\ |
| 485 |
\end{pmatrix} |
| 486 |
\end{eqnarray*} |
| 487 |
La solution de ce système est |
| 488 |
\begin{eqnarray*} |
| 489 |
\begin{pmatrix} |
| 490 |
f''_0\\ |
| 491 |
f''_1\\ |
| 492 |
f''_2\\ |
| 493 |
f''_3\\ |
| 494 |
\end{pmatrix} |
| 495 |
= |
| 496 |
\begin{pmatrix} |
| 497 |
0\\ |
| 498 |
\frac{-141}{8}\\ |
| 499 |
\frac{147}{8}\\ |
| 500 |
0\\ |
| 501 |
\end{pmatrix} |
| 502 |
\end{eqnarray*} |
| 503 |
L'interpolation est donc |
| 504 |
\begin{itemize} |
| 505 |
\item pour $x \in [1,2]$ |
| 506 |
\begin{eqnarray*} |
| 507 |
f_0&=&1\\ |
| 508 |
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}\\ |
| 509 |
f''_0&=&0\\ |
| 510 |
f'''_0&=&\frac{f''_1-f''_0}{h_0}=\frac{\frac{-141}{8}-0}{1}=\frac{-141}{8}\\ |
| 511 |
p_0(x)&=&1+\frac{175}{16}(x-1)+\frac{0}{2}(x-1)^2+\frac{-141}{6*8}(x-1)^3 |
| 512 |
\end{eqnarray*} |
| 513 |
\item pour $x \in [2,4]$ |
| 514 |
\begin{eqnarray*} |
| 515 |
f_1&=&9\\ |
| 516 |
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}\\ |
| 517 |
f''_1&=&\frac{-141}{8}\\ |
| 518 |
f'''_1&=&\frac{f''_2-f''_1}{h_1}=\frac{\frac{147}{8}-\frac{-141}{8}}{2}=18\\ |
| 519 |
p_1(x)&=&9+\frac{17}{8}(x-2)+\frac{-141}{2*8}(x-2)^2+\frac{18}{6}(x-2)^3 |
| 520 |
\end{eqnarray*} |
| 521 |
\item pour $x \in [4,5]$ |
| 522 |
\begin{eqnarray*} |
| 523 |
f_2&=&2\\ |
| 524 |
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}\\ |
| 525 |
f''_2&=&\frac{147}{8}\\ |
| 526 |
f'''_2&=&\frac{f''_3-f''_2}{h_2}=\frac{0-\frac{147}{8}}{1}=\frac{-147}{8}\\ |
| 527 |
p_2(x)&=&2+\frac{23}{8}(x-4)+\frac{147}{2*8}(x-4)^2+\frac{-147}{8*6}(x-4)^3 |
| 528 |
\end{eqnarray*} |
| 529 |
|
| 530 |
\end{itemize} |
| 531 |
|
| 532 |
\subsection{Les splines paramétrées} |
| 533 |
\subsubsection{Construction} |
| 534 |
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. |
| 535 |
\\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$. |
| 536 |
\\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)]$ |
| 537 |
\\ 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)$. |
| 538 |
\\ Pour la série $t$, on a une infinité de choix. Les plus courant sont \begin{itemize} |
| 539 |
\item $t_i=i$. |
| 540 |
\item $t_0=0$ et $t_i=t_{i-1}+\| \overrightarrow{x_i}-\overrightarrow{x_{i-1}}\|_2$ |
| 541 |
\end{itemize} |
| 542 |
|
| 543 |
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)$. |
| 544 |
\\ |
| 545 |
\\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 |
| 546 |
\begin{center} |
| 547 |
\includegraphics[width=12cm,bb=0 0 499 347]{./splineex.jpg} |
| 548 |
% splineex.jpg: 665x463 pixel, 96dpi, 17.59x12.25 cm, bb=0 0 499 347 |
| 549 |
\end{center} |
| 550 |
|
| 551 |
Le résultat montre que le cercle n'est vraiment un cercle parfait. |
| 552 |
\subsubsection{Exemple de modification des splines cubiques pour les courbes fermées} |
| 553 |
Pour que la courbe précédente parraisse 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. |
| 554 |
Les conditions supplémentaires à imposer sont |
| 555 |
\begin{eqnarray*} |
| 556 |
\left \{ |
| 557 |
\begin{array}{l} |
| 558 |
P'_0(x_0)=P'_{n-1}(x_n)\\ |
| 559 |
P''_0(x_0)=P''_{n-1}(x_n)\\ |
| 560 |
\end{array} |
| 561 |
\right. |
| 562 |
\end{eqnarray*} |
| 563 |
\begin{eqnarray*} |
| 564 |
\left \{ |
| 565 |
\begin{array}{l} |
| 566 |
f'_0=f'_{n-1}+h_{n-1}f''_{n-1}+\frac{h^2_{n-1}}{2}f'''_{n-1}\\ |
| 567 |
f''_0=f''_{n-1}+h_{n-1}f'''_{n-1}\\ |
| 568 |
\end{array} |
| 569 |
\right. |
| 570 |
\end{eqnarray*} |
| 571 |
\begin{eqnarray*} |
| 572 |
\left \{ |
| 573 |
\begin{array}{l} |
| 574 |
f[x_0,x_1]-h_0\frac{f''_0}{3}-h_1\frac{f''_1}{6}=f[x_{n-1},x_n]-h_{n-1}\frac{f''_{n-1}}{3}-h_{n-1}\frac{f''_1}{6}+h_{n-1}f''_{n-1}+\frac{h^2_{n-1}}{2}\frac{f''_n-f''_{n-1}}{h_{n-1}}\\ |
| 575 |
f''_0=f''_{n-1}+h_{n-1}\frac{f''_n-f''_{n-1}}{h_{n-1}}\\ |
| 576 |
\end{array} |
| 577 |
\right. |
| 578 |
\end{eqnarray*} |
| 579 |
\begin{eqnarray*} |
| 580 |
\left \{ |
| 581 |
\begin{array}{l} |
| 582 |
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]\\ |
| 583 |
f''_0-f''_{n}=0\\ |
| 584 |
\end{array} |
| 585 |
\right. |
| 586 |
\end{eqnarray*} |
| 587 |
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éneral comme celui vu au chapitre précédent. |
| 588 |
Le résultat donne la courbe suivante : |
| 589 |
\begin{center} |
| 590 |
\begin{center} |
| 591 |
\includegraphics[width=12cm,bb=0 0 929 604]{./splineex2.jpg} |
| 592 |
% splineex2.jpg: 1238x805 pixel, 96dpi, 32.76x21.30 cm, bb=0 0 929 604 |
| 593 |
\end{center} |
| 594 |
\end{center} |
