Algorithme de Remez

L' algorithme de Remez, _ou algorithme d'échange de Remez , publié par Evgueni Yakovlevitch Remez en 1934, est un algorithme itératif utilisé pour trouver des approximations simples de fonctions, et plus précisément, des approximations par des fonctions d'un espace de Tchebychev qui sont optimales au sens de la norme uniforme L∞ . Il est parfois appelé algorithme de Remes ou algorithme de Reme .

Un exemple typique d'espace de Tchebychev est le sous-espace des polynômes de Tchebychev d'ordre n dans l' espace des fonctions réelles continues sur un intervalle , C [ a , b ]. Le polynôme d'approximation optimale dans un sous-espace donné est celui qui minimise la plus grande différence absolue entre le polynôme et la fonction. Dans ce cas, la forme de la solution est précisée par le théorème d'équioscillation .

Résoudre le système d'équations linéaires (où ), pour les inconnues et E . Utilisez les comme coefficients pour former un polynôme . Trouver l'ensemble des points d'erreur maximale locale . Si les erreurs en chaque point sont de même amplitude et de signes alternés, alors est le polynôme d'approximation minimax. Sinon, remplacez par et répétez les étapes ci-dessus. Le résultat est appelé polynôme de meilleure approximation ou algorithme d'approximation minimax . W. Fraser donne un aperçu des aspects techniques de la mise en œuvre de l'algorithme de Remez. Choix de l'initialisation Les nœuds de Tchebychev sont souvent choisis pour l'approximation initiale en raison de leur rôle dans la théorie de l'interpolation polynomiale . Pour l'initialisation du problème d'optimisation de la fonction f par l'interpolant de Lagrange L <sub>n</sub> (f), on peut montrer que cette approximation initiale est bornée par la norme ou constante de Lebesgue de l'opérateur d'interpolation de Lagrange L <sub>n</sub> des nœuds (t <sub>1</sub>, ..., t<sub> n + 1 </sub>) étant T étant les zéros des polynômes de Tchebychev, et les fonctions de Lebesgue étant Theodore A. Kilgore , Carl de Boor et Allan Pinkus ont démontré qu'il existe un unique t<sub> i</sub> pour chaque L <sub>n</sub>, bien que cela ne soit pas explicitement connu pour les polynômes (ordinaires). De même, l'optimalité du choix des nœuds peut être exprimée comme Pour les nœuds de Chebyshev, qui offrent un choix sous-optimal mais analytiquement explicite, le comportement asymptotique est connu sous le nom de (constante d'Euler-Mascheroni ) avec pour et limite supérieure Lev Brutman a obtenu la borne pour , et étant les zéros des polynômes de Chebyshev développés : Rüdiger Günttner a obtenu à partir d'une estimation plus précise de

Discussion détaillée

Cette section fournit des informations complémentaires sur les étapes décrites ci-dessus. Dans cette section, l'indice i varie de 0 à n + 1.

Étape 1 : Étant donné , résoudre le système linéaire de n + 2 équations

(où ),

pour les inconnues et E .

Il est clair que cette équation n'a de sens que si les nœuds sont ordonnés , soit strictement croissants, soit strictement décroissants. Alors, ce système linéaire admet une solution unique. (Comme on le sait, tout système linéaire n'admet pas de solution.) De plus, la solution peut être obtenue en n'utilisant que des opérations arithmétiques, alors qu'un solveur standard de la bibliothèque nécessiterait un grand nombre d'opérations. Voici une démonstration simplifiée :

Calculer l' interpolant standard de degré n aux n + 1 premiers nœuds, ainsi que l' interpolant standard de degré n aux ordonnées.

À cette fin, utilisez à chaque fois la formule d'interpolation de Newton avec les différences divisées d'ordre et les opérations arithmétiques.

Le polynôme a son i -ème zéro entre et , et donc pas d'autres zéros entre et : et ont le même signe .

La combinaison linéaire est également un polynôme de degré n et

Ceci est identique à l'équation ci-dessus pour et pour toute valeur de E. La même équation pour i = n + 1 est

et nécessite un raisonnement particulier : résolue pour la variable E, c'est la définition de E :

Comme mentionné ci-dessus, les deux termes du dénominateur ont le même signe : E et sont donc toujours bien définis.

L'erreur aux n + 2 nœuds ordonnés donnés est tour à tour positive et négative car

Le théorème d'équioscillation stipule que, sous cette condition, aucun polynôme de degré n n'a une erreur inférieure à E. En effet, si un tel polynôme existait, notons-le , la différence serait encore positive/négative aux n + 2 nœuds et aurait donc au moins n + 1 zéros, ce qui est impossible pour un polynôme de degré n . Ainsi, cette valeur E constitue une borne inférieure pour l'erreur minimale pouvant être atteinte avec des polynômes de degré n .

L'étape 2 modifie la notation de à .

L'étape 3 améliore les nœuds d'entrée et leurs erreurs comme suit.

Dans chaque région P, le nœud courant est remplacé par le maximiseur local , et dans chaque région N, par le minimiseur local. (Sauf en A , près de et en B. ) Une grande précision n'est pas requise ; une recherche linéaire standard avec quelques ajustements quadratiques devrait suffire. (Voir )

Soit . Chaque amplitude est supérieure ou égale à E . Le théorème de La Vallée Poussin et sa démonstration s'appliquent également à avec comme nouvelle borne inférieure pour la meilleure erreur possible avec des polynômes de degré n .

De plus, cela s'avère utile comme limite supérieure évidente pour cette erreur optimale.

Étape 4 : Avec et comme bornes inférieure et supérieure de la meilleure erreur d’approximation possible , on dispose d’un critère d’arrêt fiable : répéter les étapes jusqu’à ce que soit suffisamment petit ou que ne diminue plus. Ces bornes indiquent la progression.

Variantes

Certaines modifications de l'algorithme sont présentes dans la littérature. Celles-ci comprennent :

Remplacer plusieurs points d'échantillonnage par les emplacements des différences absolues maximales voisines.à virgule flottante ;
Y compris les contraintes de point d'erreur nul.
La variante Fraser-Hart, utilisée pour déterminer la meilleure approximation rationnelle de Chebyshev.