Algorithme de Remez

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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'équioscillation de Tchebychev (cf. Théorie de l'approximation). Voir aussi les polynômes de Tchebychev.

Algorithme[modifier | modifier le code]

Le but est de trouver le polynôme P_n(x) de degré n qui approxime au mieux une fonction continue f donnée sur un intervalle [a, b]. "Au mieux" signifie que le maximum de la différence entre le polynôme et la fonction doit être minimal.

 \sup_{a \le x \le b} |P_n(x) - f(x)| = minimum

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 :

a_0 + a_1 \cdot z_1  + a_2 \cdot z_1^2  + a_3 \cdot z_1^3 + ... + a_n \cdot z_1^n = f(z_1)

a_0 + a_1 \cdot z_2  + a_2 \cdot z_2^2  + a_3 \cdot z_2^3 + ... + a_n \cdot z_2^n = f(z_2)

...

a_0 + a_1 \cdot z_{n+1}  + a_2 \cdot z_{n+1}^2  + a_3 \cdot z_{n+1}^3 + ... + a_n \cdot z_{n+1}^n = f(z_{n+1})

Sous forme de Matrice, cela donne :

M=\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}

coef=\begin{pmatrix}
a_0\\
a_1\\
... \\
a_n\\
\end{pmatrix}   func=\begin{pmatrix}
f(z_1)\\
f(z_2)\\
... \\
f(z_{n+1})\\
\end{pmatrix}

M \cdot coef = func

Première étape, meilleure départ :

Un meilleur départ est de choisir les extremums du Polynôme de Tchebychev de degré n+1, bornes a et b comprises.

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

Passer ensuite directement à la troisième étape.

Ce départ est tellement bon, qu'il est souvent inutile de revenir à la deuxième étape. Référez-vous au lien externe "Approximation polynomiale" donné ci-dessous, qui donne un exemple pratique de l'algorithme de Remez dans le langage Scilab.

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+1} = 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)   pour    k\in\{1,\ldots,n+2\}.

e est la n+2 ème 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. Référez-vous au lien externe "Approximation polynomiale" donné ci-dessous, qui donne un exemple pratique de l'algorithme de Remez dans le langage Scilab.

Sous forme de Matrice, l'équation à résoudre est :

M \cdot coef = func     où

M=\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}

coef=\begin{pmatrix}
a_0\\
a_1\\
... \\
a_n\\
e\\
\end{pmatrix}     func=\begin{pmatrix}
f(x_1)\\
f(x_2)\\
... \\
f(x_{n+1})\\
f(x_{n+2})\\
\end{pmatrix}

|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(x) = x \cdot d_1 - d_2 + c_0

Les coefficients c_k décroîtront habituellement rapidement.

Article connexe[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • 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".

Liens externes[modifier | modifier le code]