Algoritme Remez

El algoritme de Remez o algoritme de intercanvi de Remez, publicat per Evgeny Yakovlevich Remez en 1934, és un algoritme iterativo utilisat per a trobar aproximacions simples a funcions, específicament, aproximacions per funcions en un espai Chebyshev que són les millors en el sentit uniforme de la norma L _∞.

Un eixemple típic d'un espai de Chebyshev és el subespacio de polinomis de Chebyshev d'orde n en l'espai de funcions contínues reals en un interval, C[a,b ]. El polinomi de millor aproximació dins d'un subespacio donat es definix com el que minimisa la diferència absoluta màxima entre el polinomi i la funció. En este cas, la forma de la solució es precisa per mig del teorema de equioscilación .

Procediment

L'algoritme de Remez comença en la funció a ser aproximada $f$ i un conjunt $X$ de $n+2$ punts de mostra $x_1,x_2,\mathrm{...},x_{n+2}$ en l'interval d'aproximació, generalment els extrems del polinomi de Chebyshev s'assignen linealment a l'interval. Els passos són:

• Resoldre el sistema llineal d'equacions.

$b_0+b_1{x}_i+\mathrm{...}+b_n{x}_i^n+(-1{)}^{i}E=f(x_i)$ (on $i=1,2,\mathrm{...}n+2$ ),

per a les incògnites $b_0,b_1\mathrm{...}{b}_n$ i E.

• Utilisar els $b_i$ com a coeficients per a formar un polinomi $P_n$ .
• Trobar el set $M$ de punts d'error local màxim $|P_n(x)-f(x)|$ .
• Si els errors en cada $m\in M$ són d'igual magnitut i s'alternen en signe, llavors $P_n$ és el polinomi d'aproximació minimax. Si no, reemplace $X$ en $M$ i repetixca els passos anteriors.

El resultat es denomina polinomi de millor aproximació o algoritme d'aproximació minimax .

W. Fraser oferix una revisió dels tecnicismos en l'implementació de l'algoritme Remez.

Sobre l'elecció de la inicialización

Els nodos de Chebyshev són una opció comuna per a l'aproximació inicial pel seu paper en la teoria de l'interpolació polinòmica. Per a la inicialización del problema d'optimisació per a la funció f pel interpolante de Lagrange L_n(f), es pot demostrar que esta aproximació inicial està llimitada per

$\Vert f-L_n(f){\Vert }_{\mathrm{\infty }}\le (1+\Vert L_n{\Vert }_{\mathrm{\infty }})\underset{p\in P_n}{\inf }\Vert f-p\Vert$

en la norma o constant de Lebesgue de l'operador d'interpolació de Lagrange L_n dels nodos (t₁, ..., t_n+1 ) siga:

$\Vert L_n{\Vert }_{\mathrm{\infty }}={\bar{\Lambda }}_n(T)=\underset{-1\le x\le 1}{\max }{\lambda }_n(T;x),$

T són els zeros dels polinomis de Chebyshev, i les funcions de Lebesgue són

${\lambda }_n(T;x)=\sum _{j=1}^{n+1}|l_j(x)|,l_j(x)=\prod _{\stackrel{i=1}{i\ne j}}^{n+1}\frac{(x-t_i)}{(t_j-t_i)}.$

Theodore A. Kilgore, Carl de Boor i Allan Pinkus varen demostrar que existix un t_i únic per a cada L_n, encara que no es coneix explícitament per a polinomis (ordinaris). De manerasimilar, ${\underset{\_}{\Lambda }}_n(T)=\underset{-1\le x\le 1}{\min }{\lambda }_n(T;x)$, i la optimalidad d'una elecció de nodos es pot expressar com ${\bar{\Lambda }}_n-{\underset{\_}{\Lambda }}_n\ge 0.$

Per als nodos de Chebyshev que proporcionen una opció subóptima, pero analíticamente explícita, el comportament asintòtic es coneix com

${\bar{\Lambda }}_n(T)=\frac{2}{\pi }\log (n+1)+\frac{2}{\pi }(\gamma +\log \frac{8}{\pi })+{\alpha }_{n+1}$

(γ és la constant de Euler-Mascheroni) en

$0<{\alpha }_n<\frac{\pi }{72n^2}$ per a $n\ge 1,$

i llímit superior

${\bar{\Lambda }}_n(T)\le \frac{2}{\pi }\log (n+1)+1$

Lev Brutman va obtindre el llímit per a $n\ge 3$ i $\hat{T}$ sent els zeros dels polinomis de Chebyshev expandits:

${\bar{\Lambda }}_n(\hat{T})-{\underset{\_}{\Lambda }}_n(\hat{T})<{\bar{\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 \mathrm{0.201.}$

Rüdiger Günttner va obtindre, d'una estimació més precisa per a $n\ge 40$

${\bar{\Lambda }}_n(\hat{T})-{\underset{\_}{\Lambda }}_n(\hat{T})<\mathrm{0.0196.}$

Discussió detallada

Esta secció proporciona més informació sobre els passos descrits anteriorment. En esta secció, l'índex i es eixecuta de 0 a n +1.

Pas 1: dau $x_0,x_1,\mathrm{...}{x}_{n+1}$, resoldre el sistema llineal de n+2 equacions

$b_0+b_1{x}_i+\mathrm{...}+b_n{x}_i^n+(-1{)}^{i}E=f(x_i)$ (on $i=0,1,\mathrm{...}n+1$),

per les incògnites $b_0,b_1,\mathrm{...}{b}_n$ i E.

Deu quedar clar que $(-1{)}^{i}E$ en esta equació solament té sentit si els nodos $x_0,\mathrm{...},x_{n+1}$ es ordenen, ya siga de manera estrictament creixent o estrictament decreixent. Llavors este sistema llineal té una solució única (com és ben sabut, no tots els sistemes llineals tenen una solució). Ademés, la solució es pot obtindre solament en $O(n^2)$ operacions aritmètiques mentres que un solucionador estàndar prendria $O(n^3)$ operacions. Una prova simple:

Calcule el interpolador estàndar de n-ésimo grau $p_1(x)$ a $f(x)$ en els primers n+1 nodos i també el grau interpolador estàndar n-ésimo $p_2(x)$ a les ordenades $(-1{)}^i$

$p_1(x_i)=f(x_i),p_2(x_i)=(-1{)}^i,i=0,\mathrm{...},n.$

Per a este fi, use cada volta la fòrmula d'interpolació de Newton en les diferències dividides d'orde $0,\mathrm{...},n$ i $O(n^2)$ operacions aritmètiques.

El polinomi $p_2(x)$ té la seua i-ésimo zero entre $x_{i-1}$ i $x_i,i=1,\mathrm{...},n$ i, per lo tant, no hi ha més zeros entre $x_n$ i $x_{n+1}$ : $p_2(x_n)$ i $p_2(x_{n+1})$ tenint el mateix signe $(-1{)}^n$ .

La combinació llineal $p(x):=p_1(x)-p_2(x)\cdot E$ també és un polinomi de grau ny

$p(x_i)=p_1(x_i)-p_2(x_i)\cdot E=f(x_i)-(-1{)}^{i}E,i=0,\dots ,n.$

Açò és lo mateix que l'equació anterior per a $i=0,\mathrm{...},n$ i per a qualsevol elecció de E. La mateixa equació per a i = n +1 és

$p(x_{n+1})=p_1(x_{n+1})-p_2(x_{n+1})\cdot E=f(x_{n+1})-(-1{)}^{n+1}E$ i necessita un raonament especial: resolt per a la variable I, és la definició de I :

$E:=\frac{p_1(x_{n+1})-f(x_{n+1})}{p_2(x_{n+1})+(-1{)}^n}.$

Com es va mencionar anteriorment, els dos térmens en el denominador tenen el mateix signe: I i per lo tant $p(x)\equiv b_0+b_{1}x+\dots +b_n{x}^n$ sempre estan ben definits

L'error en els nodos ordenats n +2 daus és positiu i negatiu a la seua volta perque

$p(x_i)-f(x_i)=-(-1{)}^{i}E,i=0,\mathrm{...},n+1.$

La teorema de De la Vallée Poussin establix que baixe esta condició no existix un polinomi de grau n en un error menor que E. De fet, si existira tal polinomi, cride-ho $\tilde{p}(x)$, llavors la diferència $p(x)-\tilde{p}(x)=(p(x)-f(x))-(\tilde{p}(x)-f(x))$ seguiria sent positiu/negatiu en els n+2 nodos $x_i$ i per lo tant tenen a lo manco n+ zeros lo que és impossible per a un polinomi de grau n . Per lo tant, esta I és un llímit inferior per a l'error mínim que es pot conseguir en polinomis de grau n .

El pas 2 canvia la notació de $b_0+b_{1}x+\mathrm{...}+b_n{x}^n$ a $p(x)$ .

El pas 3 millora els nodos d'entrada $x_0,\mathrm{...},x_{n+1}$ i els seus errors $\pm E$ com seguix.

En cada regió P, el nodo actual $x_i$ es reemplaça en el ${\overline{x}}_i$ maximisador local i en cada N-regió $x_i$ es reemplaça en el minimisador local. (S'espera ${\overline{x}}_0$ en A, ${\overline{x}}_i$ prop $x_i$ i ${\overline{x}}_{n+1}$ en B). No es requerix alta precisió ací, la busca de llínea estàndar en un parell de ajusts quadràtics deuria ser suficient. (Vore )

Siga $z_i:=p({\overline{x}}_i)-f({\overline{x}}_i)$ . Cada amplitut $|z_i|$ és major o igual que E. La teorema de de la Vallée Poussin i la seua prova també s'apliquen a $z_0,\mathrm{...},z_{n+1}$ en $\min \{|z_i|\}\ge E$ com el nou llímit inferior per al millor error possible en polinomis de grau n .

Ademés, $\max \{|z_i|\}$ és útil com un llímit superior obvi per a eixe millor error possible.

Pas 4: en $\min \{|z_i|\}$ i $\max \{|z_i|\}$ com a llímit inferior i superior per al millor error d'aproximació possible, un té un criteri de detenció confiable: repetix els passos fins que $\max \{|z_i|\}-\min \{|z_i|\}$ és suficientment chicotet o ya no disminuïx. Estos llímits indiquen el progrés.

Vore també

• Teoria de l'aproximació