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]​

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]​

Véase también

• Teoría de la aproximación

Referencias

Enlaces externos

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