Algoritmo Remez
# 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 $_∞.$

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 $f$ y un conjunto $X$ de $n+2$ puntos de muestra $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.

    $b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})$ (dónde $i=1,2,...n+2$ ),
    para las incógnitas $b_{0},b_{1}...b_{n}$ y E.
* Utilizar los $b_{i}$ como coeficientes para formar un polinomio $P_{n}$ .
* Encontrar el set $M$ de puntos de error local máximo $|P_{n}(x)-f(x)|$ .
* Si los errores en cada $m\in M$ son de igual magnitud y se alternan en signo, entonces $P_{n}$ es el polinomio de aproximación minimax. Si no, reemplace $X$ con $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.

### 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

    $\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_1,$ ..., $t_{n+1}$ ) sea:

    $\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

    $\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 y Allan Pinkus demostraron que existe un $t_i$ único para cada $L_n,$ aunque no se conoce explícitamente para polinomios (ordinarios). De manerasimilar, ${\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 ${\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

    ${\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

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

y límite superior

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

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

    ${\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 obtuvo, de una estimación más precisa para $n\geq 40$

    ${\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 $x_{0},x_{1},...x_{n+1}$, resolver el sistema lineal de n+2 ecuaciones

    $b_{0}+b_{1}x_{i}+...+b_{n}x_{i}^{n}+(-1)^{i}E=f(x_{i})$ (dónde $i=0,1,...n+1$),
    por las incógnitas $b_{0},b_{1},...b_{n}$ y E.

Debe quedar claro que $(-1)^{i}E$ en esta ecuación solo tiene sentido si los nodos $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 $O(n^{2})$ operaciones aritméticas mientras que un solucionador estándar tomaría $O(n^{3})$ operaciones. Una prueba simple:

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

    $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 $0,...,n$ y $O(n^{2})$ operaciones aritméticas.

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

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

    $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 $i=0,...,n$ y para cualquier elección de E. La misma ecuación para i = n +1 es

    $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 :
    $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 $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

    $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 ${\tilde {p}}(x)$, entonces la diferencia $p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))$ seguiría siendo positivo/negativo en los n+2 nodos $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 $b_{0}+b_{1}x+...+b_{n}x^{n}$ a $p(x)$ .

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

En cada región P, el nodo actual $x_{i}$ se reemplaza con el ${\bar {x}}_{i}$ maximizador local y en cada N-región $x_{i}$ se reemplaza con el minimizador local. (Se espera ${\bar {x}}_{0}$ en A, ${\bar {x}}_{i}$ cerca $x_{i}$ y ${\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 )

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

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

Paso 4: con $\min \,\{|z_{i}|\}$ y $\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 $\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.

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.

