Algorithme de Remez
# 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
