Algorithme de Remez - Remez algorithm

L' algorithme de Remez ou algorithme d' échange de Remez , publié par Evgeny Yakovlevich Remez en 1934, est un algorithme itératif utilisé pour trouver des approximations simples de fonctions, en particulier des approximations par des fonctions dans un espace de Chebyshev qui sont les meilleures au sens de la norme uniforme L _∞ .

Un exemple typique d'un espace Chebyshev est le sous - espace de polynômes de Chebyshev d'ordre n dans la place de réelles fonctions continues sur un intervalle , C [ a , b ]. Le polynôme de meilleure approximation dans un sous-espace donné est défini comme celui qui minimise la différence absolue maximale 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 .

Procédure

L'algorithme de Remez commence par la fonction à approximer et un ensemble de points d'échantillonnage dans l'intervalle d'approximation, généralement les extrema du polynôme de Chebyshev mappés linéairement sur l'intervalle. Les étapes sont : ${\style d'affichage f}$${\style d'affichage X}$${\style d'affichage n+2}$${\style d'affichage x_{1},x_{2},...,x_{n+2}}$

• Résoudre le système linéaire d'équations

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i} )}$(où ),${\style d'affichage i=1,2,...n+2}$

pour les inconnues et E .${\displaystyle b_{0},b_{1}...b_{n}}$

• Utilisez les comme coefficients pour former un polynôme .${\style d'affichage b_{i}}$${\style d'affichage P_{n}}$
• Trouver l'ensemble des points d'erreur maximale locale .${\style d'affichage M}$${\style d'affichage |P_{n}(x)-f(x)|}$
• Si les erreurs à chaque fois sont de même amplitude et de signe alternatif, alors est le polynôme d'approximation minimax. Sinon, remplacez par et répétez les étapes ci-dessus.${\displaystyle m\in M}$${\style d'affichage P_{n}}$${\style d'affichage X}$${\style d'affichage M}$

Le résultat est appelé le polynôme de meilleure approximation ou l' algorithme d'approximation minimax .

Une revue des détails techniques dans la mise en œuvre de l'algorithme de Remez est donnée par W. Fraser.

Sur le choix de l'initialisation

Les nœuds de Chebyshev sont un choix courant 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 pour la fonction f par l'interpolant de Lagrange L _n ( f ), on peut montrer que cette première approximation est bornée par

${\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n }}\lVert fp\rVert }$

avec la norme ou constante de Lebesgue de l'opérateur d'interpolation de Lagrange L _n des nœuds ( t ₁ , ..., t _{n  + 1} ) étant

${\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{ n}(T;x),}$

T étant les zéros des polynômes de Chebyshev, et les fonctions de Lebesgue étant

${\displaystyle \lambda _{n}(T;x)=\sum _{j=1}^{n+1}\left|l_{j}(x)\right|,\quad l_{j}( x)=\prod _{\stackrel {i=1}{i\neq j}}^{n+1}{\frac {(x-t_{i})}{(t_{j}-t_{i })}}.}$

Theodore A. Kilgore, Carl de Boor et Allan Pinkus ont prouvé qu'il existe un t _i unique pour chaque L _n , bien qu'il ne soit pas connu explicitement pour les polynômes (ordinaires). De même, , et l'optimalité d'un choix de nœuds peuvent être exprimés comme${\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)}$${\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.}$

Pour les nœuds de Chebyshev, qui fournit un choix sous-optimal, mais analytiquement explicite, le comportement asymptotique est connu sous le nom

${\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\ gauche(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}}$

( γ étant la constante d'Euler–Mascheroni ) avec

${\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}}$ pour ${\style d'affichage n\geq 1,}$

et borne supérieure

${\displaystyle {\overline {\Lambda }}_{n}(T)\leq {\frac {2}{\pi }}\log(n+1)+1}$

Lev Brutman a obtenu la borne pour , et étant les zéros des polynômes étendus de Chebyshev : ${\style d'affichage n\geq 3}$${\displaystyle {\hat {T}}}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<{\overline {\Lambda }}_{3}-{\frac {1}{6}}\cot {\frac {\pi }{8}}+{\frac {\pi }{64}}{\frac {1 }{\sin ^{2}(3\pi /16)}}-{\frac {2}{\pi }}(\gamma -\log \pi )\approx 0.201.}$

Rüdiger Günttner a obtenu à partir d'une estimation plus précise de ${\style d'affichage n\geq 40}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}$

Discussion détaillée

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

Étape 1 : Étant donné , résolvez le système linéaire de n +2 équations ${\style d'affichage x_{0},x_{1},...x_{n+1}}$

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i} )}$(où ),${\style d'affichage i=0,1,...n+1}$

pour les inconnues et E .${\style d'affichage b_{0},b_{1},...b_{n}}$

Il devrait être clair que dans 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 a une solution unique. (Comme cela est bien connu, tous les systèmes linéaires n'ont pas de solution.) De plus, la solution peut être obtenue avec uniquement des opérations arithmétiques alors qu'un solveur standard de la bibliothèque prendrait des opérations. Voici la preuve simple : ${\style d'affichage (-1)^{i}E}$${\style d'affichage x_{0},...,x_{n+1}}$${\style d'affichage O(n^{2})}$${\style d'affichage O(n^{3})}$

Calculer l' interpolant standard du n -ième degré aux n +1 premiers nœuds et également l' interpolant standard du n -ième degré aux ordonnées${\style d'affichage p_{1}(x)}$${\style d'affichage f(x)}$${\style d'affichage p_{2}(x)}$${\style d'affichage (-1)^{i}}$

${\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,..., n.}$

Pour cela, utilisez à chaque fois la formule d'interpolation de Newton avec les différences divisées d'ordre et d' opérations arithmétiques. ${\style d'affichage 0,...,n}$${\style d'affichage O(n^{2})}$

Le polynôme a son i- ième zéro entre et , et donc aucun autre zéro entre et : et ont le même signe . ${\style d'affichage p_{2}(x)}$${\style d'affichage x_{i-1}}$${\style d'affichage x_{i},\ i=1,...,n}$${\style d'affichage x_{n}}$${\style d'affichage x_{n+1}}$${\style d'affichage p_{2}(x_{n})}$${\style d'affichage p_{2}(x_{n+1})}$${\style d'affichage (-1)^{n}}$

La combinaison linéaire est aussi un polynôme de degré n et ${\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}$

${\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})- (-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}$

C'est la même que l'équation ci-dessus pour et pour tout choix de E . La même équation pour i = n +1 est ${\style d'affichage i=0,...,n}$

${\displaystyle p(x_{n+1})\ =\ p_{1}(x_{n+1})-p_{2}(x_{n+1})\!\cdot \!E\ =\ f(x_{n+1})-(-1)^{n+1}E}$et nécessite un raisonnement particulier : résolu pour la variable E , c'est la définition de E :

${\displaystyle E\ :=\ {\frac {p_{1}(x_{n+1})-f(x_{n+1})}{p_{2}(x_{n+1})+( -1)^{n}}}.}$

Comme mentionné ci-dessus, les deux termes du dénominateur ont le même signe : E et sont donc toujours bien définis. ${\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}$

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

${\displaystyle p(x_{i})-f(x_{i})\ =\ -(-1)^{i}E,\ \ i=0,...,n\!+\!1. }$

Le théorème de La Vallée Poussin énonce que sous cette condition aucun polynôme de degré n n'existe avec une erreur inférieure à E . En effet, si un tel polynôme existait, appelez-le , alors la différence serait toujours 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, ce E est une borne inférieure de l'erreur minimale qui peut être atteinte avec des polynômes de degré n . ${\displaystyle {\tilde {p}}(x)}$${\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))}$${\style d'affichage x_{i}}$

L'étape 2 modifie la notation de à . ${\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}$${\style d'affichage p(x)}$

L'étape 3 améliore les nœuds d'entrée et leurs erreurs comme suit. ${\style d'affichage x_{0},...,x_{n+1}}$${\style d'affichage \pm E}$

Dans chaque région P, le nœud actuel est remplacé par le maximiseur local et dans chaque région N est remplacé par le minimiseur local. (Attendez-vous à A , près de , et à B .) Aucune précision élevée n'est requise ici, la recherche de ligne standard avec quelques ajustements quadratiques devrait suffire. (Voir ) ${\style d'affichage x_{i}}$${\displaystyle {\bar {x}}_{i}}$${\style d'affichage x_{i}}$${\displaystyle {\bar {x}}_{0}}$${\displaystyle {\bar {x}}_{i}}$${\style d'affichage x_{i}}$${\displaystyle {\bar {x}}_{n+1}}$

Laissez . 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 . ${\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})}$${\style d'affichage |z_{i}|}$${\style d'affichage z_{0},...,z_{n+1}}$${\displaystyle \min\{|z_{i}|\}\geq E}$

De plus, cela s'avère utile en tant que limite supérieure évidente pour la meilleure erreur possible. ${\style d'affichage \max\{|z_{i}|\}}$

Étape 4 : Avec et comme borne inférieure et supérieure pour la meilleure erreur d'approximation possible, on a un critère d'arrêt fiable : répéter les étapes jusqu'à ce qu'elle soit suffisamment petite ou ne diminue plus. Ces bornes indiquent la progression. ${\style d'affichage \min \,\{|z_{i}|\}}$${\style d'affichage \max \,\{|z_{i}|\}}$${\style d'affichage \max\{|z_{i}|\}-\min\{|z_{i}|\}}$

Variantes

Parfois, plusieurs points d'échantillonnage sont remplacés en même temps par les emplacements des différences absolues maximales proches.

Parfois, tous les points d'échantillonnage sont remplacés en une seule itération avec les emplacements de tous, signe alternatif, différences maximales.

Parfois, l' erreur relative est utilisée pour mesurer la différence entre l'approximation et la fonction, surtout si l'approximation sera utilisée pour calculer la fonction sur un ordinateur qui utilise l' arithmétique à virgule flottante .

Parfois, des contraintes de point zéro erreur sont incluses dans un algorithme d'échange Remez modifié.

Voir également

• Théorie de l'approximation

Les références

Liens externes

• Minimax Approximations and the Remez Algorithm , chapitre de fond dans la documentation Boost Math Tools, avec lien vers une implémentation en C++
• Introduction au DSP
• Aarts, Ronald M.; Bond, Charles ; Mendelsohn, Phil & Weisstein, Eric W. "Algorithme Remez" . MathWorld .