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.

Le but est de trouver le polynôme ${\displaystyle P_{n}(x)}$ de degré n qui approche au mieux une fonction continue f donnée sur un intervalle ${\displaystyle [a,b]}$, dans le sens où le maximum de la différence entre le polynôme et la fonction doit être minimal :

${\displaystyle 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 ${\displaystyle n+2}$ extremums, de même amplitude et qui alterneront.

Notons le polynôme cherché.

${\displaystyle 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 ${\displaystyle n+1}$ inconnues qui sont :

${\displaystyle 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é ${\displaystyle n+1}$ et de déterminer le polynôme ${\displaystyle 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 :

${\displaystyle z_{k}={\frac {a+b}{2}}+{\frac {b-a}{2}}\cdot \cos \left({\frac {(2k-1)\pi }{2n+2}}\right)}$ ,   pour ${\displaystyle k\in \{1,\ldots ,n+1\}.}$

Il faut donc résoudre :

${\displaystyle P_{n}(z_{k})=f(z_{k})}$   pour   ${\displaystyle k\in \{1,\ldots ,n+1\}.}$

Explicitement, si on cherche les coefficients du polynôme ${\displaystyle P_{n}(x)}$ cela donne :

${\displaystyle \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 :

${\displaystyle {\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é ${\displaystyle n+1}$, bornes comprises.

${\displaystyle 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 ${\displaystyle a}$ et ${\displaystyle b}$ font partie de ces extremums. Cela devrait donner ${\displaystyle n+2}$ points ${\displaystyle x_{1},x_{2},...,x_{n+2}}$.

En général, ${\displaystyle x_{1}=a}$ est le premier extremum, ensuite les autres extremums alternent entre "minima" et "maxima", jusqu'à ${\displaystyle x_{n+2}=b}$.

Troisième étape :

Déterminer le polynôme ${\displaystyle P_{n}(x)}$ de degré ${\displaystyle n}$ qui satisfait :

${\displaystyle P_{n}(x_{k})+(-1)^{k}\cdot e=f(x_{k}),\,\forall k\in \{1,\ldots ,n+2\}.}$

où e est la n+2^e 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 :

${\displaystyle {\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 ${\displaystyle |e|}$ donne une bonne estimation de la différence maximale entre le polynôme et la fonction sur l'intervalle ${\displaystyle [a,b]}$ donné.

Remarque

Une dernière légère amélioration serait d'écrire le polynôme sous la forme :

${\displaystyle 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ù ${\displaystyle T_{n}(x)}$ est le n-ème polynôme de Tchebychev.

Ensuite on évalue efficacement ce polynôme en ${\displaystyle x}$ par

${\displaystyle d_{n+1}=0;\quad d_{n}=c_{n};}$

${\displaystyle d_{j}=2\cdot x\cdot d_{j+1}-d_{j+2}+c_{j}}$

  pour   ${\displaystyle j=n-1,n-2,n-3,...,3,2,1}$

${\displaystyle P_{n}(x)=x\cdot d_{1}-d_{2}+c_{0}}$

Les coefficients ${\displaystyle c_{k}}$ décroîtront habituellement rapidement.

• Polynôme de Tchebychev

• J.-M. Muller, Elementary functions: Algorithms and Implementation. éd. Birkhäuser (1997, rééd. 2005), (ISBN 0-8176-4372-9), p. 41–47
• Numerical Recipes, The Art of Scientific Computing, Second Edition ou Third Edition, William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, éd. Cambridge university press, 1992 ou 2007. Chapitre 5, "Chebyshev Approximation" jusqu'à "Rational Chebyshev Approximation".

• (en) Eric W. Weisstein, « Remez Algorithm », sur MathWorld
• Approximation polynomiale de fonctions dans le langage SciLab, avec une implémentation de l'algorithme de Remez. C.f. la Série 4 et le corrigé qui suit.

• Portail de l'informatique théorique