Algoritmo Remez

El algoritmo de Remez o algoritmo de intercambio de Remez, publicado por Evgeny Yakovlevich Remez en 1934, es un algoritmo iterativo utilizado para encontrar aproximaciones simples a funciones, específicamente, aproximaciones por funciones en un espacio Chebyshev que son las mejores en el sentido uniforme de la norma L _∞. ^[1]​

Algoritmo Remez Algoritmo de intercambio de Remez
Tipo	Algoritmo iterativo
Problema que resuelve	Encontrar aproximaciones simples a ciertas funciones.
Creador	Evgeny Yakovlevich Remez
Fecha	1934
[editar datos en Wikidata]

Un ejemplo típico de un espacio de Chebyshev es el subespacio de polinomios de Chebyshev de orden n en el espacio de funciones continuas reales en un intervalo, C[a,b ]. El polinomio de mejor aproximación dentro de un subespacio dado se define como el que minimiza la diferencia absoluta máxima entre el polinomio y la función. En este caso, la forma de la solución se precisa mediante el teorema de equioscilación .

Procedimiento

El algoritmo de Remez comienza con la función a ser aproximada ${\displaystyle f}$  y un conjunto ${\displaystyle X}$  de ${\displaystyle n+2}$  puntos de muestra ${\displaystyle x_{1},x_{2},...,x_{n+2}}$  en el intervalo de aproximación, generalmente los extremos del polinomio de Chebyshev se asignan linealmente al intervalo. Los pasos son:

• Resolver el sistema lineal de ecuaciones.

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$  (dónde ${\displaystyle i=1,2,...n+2}$  ),

para las incógnitas ${\displaystyle b_{0},b_{1}...b_{n}}$  y E.

• Utilizar los ${\displaystyle b_{i}}$  como coeficientes para formar un polinomio ${\displaystyle P_{n}}$  .
• Encontrar el set ${\displaystyle M}$  de puntos de error local máximo ${\displaystyle |P_{n}(x)-f(x)|}$  .
• Si los errores en cada ${\displaystyle m\in M}$  son de igual magnitud y se alternan en signo, entonces ${\displaystyle P_{n}}$  es el polinomio de aproximación minimax. Si no, reemplace ${\displaystyle X}$  con ${\displaystyle M}$  y repita los pasos anteriores.

El resultado se denomina polinomio de mejor aproximación o algoritmo de aproximación minimax .

W. Fraser ofrece una revisión de los tecnicismos en la implementación del algoritmo Remez.^[2]​

Sobre la elección de la inicialización

Los nodos de Chebyshev son una opción común para la aproximación inicial debido a su papel en la teoría de la interpolación polinómica. Para la inicialización del problema de optimización para la función f por el interpolante de Lagrange L_n(f), se puede demostrar que esta aproximación inicial está limitada por

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

con la norma o constante de Lebesgue del operador de interpolación de Lagrange L_n de los nodos (t₁, ..., t_n+1 ) sea:

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

T son los ceros de los polinomios de Chebyshev, y las funciones de Lebesgue son

${\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, ^[3]​ Carl de Boor y Allan Pinkus ^[4]​ demostraron que existe un t_i único para cada L_n, aunque no se conoce explícitamente para polinomios (ordinarios). De manerasimilar, ${\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)}$ , y la optimalidad de una elección de nodos se puede expresar como ${\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.}$ 

Para los nodos de Chebyshev que proporcionan una opción subóptima, pero analíticamente explícita, el comportamiento asintótico se conoce como ^[5]​

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

(γ es la constante de Euler-Mascheroni) con

${\displaystyle 0<\alpha _{n}<{\frac {\pi }{72n^{2}}}}$  para ${\displaystyle n\geq 1,}$ 

y límite superior ^[6]​

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

Lev Brutman ^[7]​ obtuvo el límite para ${\displaystyle n\geq 3}$  y ${\displaystyle {\hat {T}}}$  siendo los ceros de los polinomios de Chebyshev expandidos:

${\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 ^[8]​ obtuvo, de una estimación más precisa para ${\displaystyle n\geq 40}$ 

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

Discusión detallada

Esta sección proporciona más información sobre los pasos descritos anteriormente. En esta sección, el índice i se ejecuta de 0 a n +1.

Paso 1: dado ${\displaystyle x_{0},x_{1},...x_{n+1}}$ , resolver el sistema lineal de n+2 ecuaciones

${\displaystyle b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})}$  (dónde ${\displaystyle i=0,1,...n+1}$ ),

por las incógnitas ${\displaystyle b_{0},b_{1},...b_{n}}$  y E.

Debe quedar claro que ${\displaystyle (-1)^{i}E}$  en esta ecuación solo tiene sentido si los nodos ${\displaystyle x_{0},...,x_{n+1}}$  se ordenan, ya sea de manera estrictamente creciente o estrictamente decreciente. Entonces este sistema lineal tiene una solución única. (Como es bien sabido, no todos los sistemas lineales tienen una solución) Además, la solución se puede obtener solo con ${\displaystyle O(n^{2})}$  operaciones aritméticas mientras que un solucionador estándar tomaría ${\displaystyle O(n^{3})}$  operaciones. Una prueba simple:

Calcule el interpolador estándar de n-ésimo grado ${\displaystyle p_{1}(x)}$  a ${\displaystyle f(x)}$  en los primeros n+1 nodos y también el grado interpolador estándar n-ésimo ${\displaystyle p_{2}(x)}$  a las ordenadas ${\displaystyle (-1)^{i}}$ 

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

Para este fin, use cada vez la fórmula de interpolación de Newton con las diferencias divididas de orden ${\displaystyle 0,...,n}$  y ${\displaystyle O(n^{2})}$  operaciones aritméticas.

El polinomio ${\displaystyle p_{2}(x)}$  tiene su i-ésimo cero entre ${\displaystyle x_{i-1}}$  y ${\displaystyle x_{i},\ i=1,...,n}$  y, por lo tanto, no hay más ceros entre ${\displaystyle x_{n}}$  y ${\displaystyle x_{n+1}}$  : ${\displaystyle p_{2}(x_{n})}$  y ${\displaystyle p_{2}(x_{n+1})}$  teniendo el mismo signo ${\displaystyle (-1)^{n}}$  .

La combinación lineal ${\displaystyle p(x):=p_{1}(x)-p_{2}(x)\!\cdot \!E}$  también es un polinomio de grado ny

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

Esto es lo mismo que la ecuación anterior para ${\displaystyle i=0,...,n}$  y para cualquier elección de E. La misma ecuación para i = n +1 es

${\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}$  y necesita un razonamiento especial: resuelto para la variable E, es la definición de E :

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

Como se mencionó anteriormente, los dos términos en el denominador tienen el mismo signo: E y por lo tanto ${\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}$  siempre están bien definidos

El error en los nodos ordenados n +2 dados es positivo y negativo a su vez porque

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

El teorema de De La Vallée Poussin establece que bajo esta condición no existe un polinomio de grado n con un error menor que E. De hecho, si existiera tal polinomio, llámelo ${\displaystyle {\tilde {p}}(x)}$ , entonces la diferencia ${\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))}$  seguiría siendo positivo/negativo en los n+2 nodos ${\displaystyle x_{i}}$  y por lo tanto tienen al menos n+ ceros lo que es imposible para un polinomio de grado n . Por lo tanto, esta E es un límite inferior para el error mínimo que se puede lograr con polinomios de grado n .

El paso 2 cambia la notación de ${\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}$  a ${\displaystyle p(x)}$  .

El paso 3 mejora los nodos de entrada ${\displaystyle x_{0},...,x_{n+1}}$  y sus errores ${\displaystyle \pm E}$  como sigue.

En cada región P, el nodo actual ${\displaystyle x_{i}}$  se reemplaza con el ${\displaystyle {\bar {x}}_{i}}$  maximizador local y en cada N-región ${\displaystyle x_{i}}$  se reemplaza con el minimizador local. (Se espera ${\displaystyle {\bar {x}}_{0}}$  en A, ${\displaystyle {\bar {x}}_{i}}$  cerca ${\displaystyle x_{i}}$  y ${\displaystyle {\bar {x}}_{n+1}}$  en B). No se requiere alta precisión aquí, la búsqueda de línea estándar con un par de ajustes cuadráticos debería ser suficiente. (Ver ^[9]​ )

Sea ${\displaystyle z_{i}:=p({\bar {x}}_{i})-f({\bar {x}}_{i})}$  . Cada amplitud ${\displaystyle |z_{i}|}$  es mayor o igual que E. El teorema de de La Vallée Poussin y su prueba también se aplican a ${\displaystyle z_{0},...,z_{n+1}}$  con ${\displaystyle \min\{|z_{i}|\}\geq E}$  como el nuevo límite inferior para el mejor error posible con polinomios de grado n .

Además, ${\displaystyle \max\{|z_{i}|\}}$  es útil como un límite superior obvio para ese mejor error posible.

Paso 4: con ${\displaystyle \min \,\{|z_{i}|\}}$  y ${\displaystyle \max \,\{|z_{i}|\}}$  como límite inferior y superior para el mejor error de aproximación posible, uno tiene un criterio de detención confiable: repite los pasos hasta que ${\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}$  es suficientemente pequeño o ya no disminuye. Estos límites indican el progreso.

Variantes

A veces se reemplaza más de un punto de muestra es reemplazado al mismo tiempo con las ubicaciones de las diferencias absolutas máximas cercanas.

A veces todos los puntos de muestra se reemplazan en una sola iteración con las ubicaciones de todos las diferencias máximas, alternando los signos. ^[10]​

A veces, el error relativo se usa para medir la diferencia entre la aproximación y la función, especialmente si la aproximación se usará para calcular la función en una computadora que usa aritmética de coma flotante.

A veces, las restricciones de punto de error cero se incluyen en un Algoritmo de intercambio Remez modificado. ^[10]​

Ver también

• Teoría de la aproximación

Referencias

1. E. Ya. Remez, "Sur la détermination des polynômes d'approximation de degré donnée", Comm. Soc. Math. Kharkov 10, 41 (1934);
   "Sur un procédé convergent d'approximations successives pour déterminer les polynômes d'approximation, Compt. Rend. Acad. Sc. 198, 2063 (1934);
   "Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Acade. Sc. 199, 337 (1934).
2. Fraser, W. (1965). «A Survey of Methods of Computing Minimax and Near-Minimax Polynomial Approximations for Functions of a Single Independent Variable». J. ACM 12: 295. doi:10.1145/321281.321282. 
3. Kilgore, T. A. (1978). «A characterization of the Lagrange interpolating projection with minimal Tchebycheff norm». J. Approx. Theory 24: 273. doi:10.1016/0021-9045(78)90013-8. 
4. de Boor, C.; Pinkus, A. (1978). «Proof of the conjectures of Bernstein and Erdös concerning the optimal nodes for polynomial interpolation». Journal of Approximation Theory 24: 289. doi:10.1016/0021-9045(78)90014-X. 
5. Luttmann, F. W.; Rivlin, T. J. (1965). «Some numerical experiments in the theory of polynomial interpolation». IBM J. Res. Dev. 9: 187. doi:10.1147/rd.93.0187. 
6. T. Rivlin, "The Lebesgue constants for polynomial interpolation", in Proceedings of the Int. Conf. on Functional Analysis and Its Application, edited by H. G. Garnier et al. (Springer-Verlag, Berlin, 1974), p. 422; The Chebyshev polynomials (Wiley-Interscience, New York, 1974).
7. Brutman, L. (1978). «On the Lebesgue Function for Polynomial Interpolation». SIAM J. Numer. Anal. 15: 694. doi:10.1137/0715046. 
8. Günttner, R. (1980). «Evaluation of Lebesgue Constants». SIAM J. Numer. Anal. 17: 512. doi:10.1137/0717043. 
9. David G. Luenberger: Introduction to Linear and Nonlinear Programming, Addison-Wesley Publishing Company 1973.
10. 2/73 "The Optimization of Bandlimited Systems" – G. C. Temes, F. C. Marshall and V. Barcilon. Proceedings IEEE.

Enlaces externos

• El Método Remez , Documentación de Boost

•   Datos: Q2835816