title: Algorithme de Remez
text: # Algorithme de Remez
  
  En mathématiques, l’algorithme de Remez, du nom de son inventeur Eugène Yakovlevitch Remez, vise à construire la meilleure approximation polynomiale d'une fonction continue sur un intervalle borné, étant donné le degré maximal du polynôme.
  
  Cet algorithme est le calcul pratique lié au théorème d'équi-oscillation de Tchebychev (cf. Théorie de l'approximation). Voir aussi les polynômes de Tchebychev.
  
  ## Algorithme
  
  Le but est de trouver le polynôme $P_{n}(x)$ de degré n qui approche au mieux une fonction continue f donnée sur un intervalle $[a,b]$, dans le sens où le maximum de la différence entre le polynôme et la fonction doit être minimal :
  
      $P_{n}={\textrm {arg}}\min \left(\sup _{a\leq x\leq b}|P_{n}(x)-f(x)|\right)$
  
  Cela implique que la différence entre le polynôme et la fonction atteindra $n+2$ extremums, de même amplitude et qui alterneront.
  
  Notons le polynôme cherché.
  
      $P_{n}(x)=a_{0}+a_{1}\cdot x+a_{2}\cdot x^{2}+a_{3}\cdot x^{3}+...+a_{n}\cdot x^{n}$
  
  Il y a donc $n+1$ inconnues qui sont :
  
      $a_{0};a_{1};a_{2};a_{3};...;a_{n}$
  
  Première étape :
  
  Un départ possible est de choisir les zéros du polynôme de Tchebychev de degré $n+1$ et de déterminer le polynôme $P_{n}(x)$ qui coïncide avec la fonction en ces points. Il faut faire une homothétie des zéros pour tenir compte des bornes de l'intervalle. Les valeurs à prendre en compte sont :
  
      $z_{k}={\frac {a+b}{2}}+{\frac {b-a}{2}}\cdot \cos \left({\frac {(2k-1)\pi }{2n+2}}\right)$ , pour $k\in \{1,\ldots ,n+1\}.$
  
  Il faut donc résoudre :
  
      $P_{n}(z_{k})=f(z_{k})$ pour $k\in \{1,\ldots ,n+1\}.$
  
  Explicitement, si on cherche les coefficients du polynôme $P_{n}(x)$ cela donne :
  
      $\forall k\in [\![1;n+1]\!],\,a_{0}+a_{1}\cdot z_{k}+a_{2}\cdot z_{k}^{2}+a_{3}\cdot z_{k}^{3}+...+a_{n}\cdot z_{k}^{n}=f(z_{k})$
  
  Sous forme de matrice, cela donne :
  
      ${\begin{pmatrix}1&z_{1}&z_{1}^{2}&...&z_{1}^{n}\\1&z_{2}&z_{2}^{2}&...&z_{2}^{n}\\...&...&...&...&...\\1&z_{n+1}&z_{n+1}^{2}&...&z_{n+1}^{n}\\\end{pmatrix}}{\begin{pmatrix}a_{0}\\a_{1}\\...\\a_{n}\end{pmatrix}}={\begin{pmatrix}f(z_{1})\\f(z_{2})\\...\\f(z_{n+1})\\\end{pmatrix}}$
  
  Première étape, meilleur départ :
  
  Un meilleur départ est de choisir les extremums du polynôme de Tchebychev de degré $n+1$, bornes comprises.
  
      $x_{k}={\frac {a+b}{2}}+{\frac {b-a}{2}}\cdot \cos \left({\frac {(k-1)\pi }{n+1}}\right),\,\forall k\in \{1,\ldots ,n+2\}.$
  
  Deuxième étape :
  
  Une fois un premier polynôme approximant la fonction trouvé, chercher les n+2 extremums de la différence entre le polynôme et la fonction. En général, les deux bornes $a$ et $b$ font partie de ces extremums. Cela devrait donner $n+2$ points $x_{1},x_{2},...,x_{n+2}$.
  
  En général, $x_{1}=a$ est le premier extremum, ensuite les autres extremums alternent entre "minima" et "maxima", jusqu'à $x_{n+2}=b$.
  
  Troisième étape :
  
  Déterminer le polynôme $P_{n}(x)$ de degré $n$ qui satisfait :
  
      $P_{n}(x_{k})+(-1)^{k}\cdot e=f(x_{k}),\,\forall k\in \{1,\ldots ,n+2\}.$
  
  où e est la n+2e inconnue.
  
  Si l'approximation trouvée n'est pas suffisamment bonne, retourner à l'étape 2. En général une itération suffit, la convergence est très rapide.
  
  Sous forme de matrice, l'équation à résoudre est :
  
  ${\begin{pmatrix}1&x_{1}&x_{1}^{2}&...&x_{1}^{n}&-1\\1&x_{2}&x_{2}^{2}&...&x_{2}^{n}&(-1)^{2}\\...&...&...&...&...\\1&x_{n+1}&x_{n+1}^{2}&...&x_{n+1}^{n}&(-1)^{n+1}\\1&x_{n+2}&x_{n+2}^{2}&...&x_{n+2}^{n}&(-1)^{n+2}\end{pmatrix}}{\begin{pmatrix}a_{0}\\a_{1}\\...\\a_{n}\\e\end{pmatrix}}={\begin{pmatrix}f(x_{1})\\f(x_{2})\\...\\f(x_{n+1})\\f(x_{n+2})\end{pmatrix}}$
  
  La valeur absolue $|e|$ donne une bonne estimation de la différence maximale entre le polynôme et la fonction sur l'intervalle $[a,b]$ donné.
  
  Remarque
  
  Une dernière légère amélioration serait d'écrire le polynôme sous la forme :
  
      $P_{n}(x)=c_{0}+c_{1}\cdot T_{1}(x)+c_{2}\cdot T_{2}(x)+c_{3}\cdot T_{3}(x)+...+c_{n}\cdot T_{n}(x)$
  
  où $T_{n}(x)$ est le n-ème polynôme de Tchebychev.
  
  Ensuite on évalue efficacement ce polynôme en $x$ par
  
      $d_{n+1}=0;\quad d_{n}=c_{n};$
      $d_{j}=2\cdot x\cdot d_{j+1}-d_{j+2}+c_{j}$
  
  pour  $j=n-1,n-2,n-3,...,3,2,1$
  
      $P_{n}(x)=x\cdot d_{1}-d_{2}+c_{0}$
  
  Les coefficients $c_{k}$ décroîtront habituellement rapidement.
  
  ## Article connexe
  
  * Polynôme de Tchebychev
  