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 .

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:

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

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

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

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

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 _{-1leq xleq 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]​

(γ es la constante de Euler-Mascheroni) con

y límite superior ^[6]​

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

Rüdiger Günttner ^[8]​ obtuvo, de una estimación más precisa para ${displaystyle ngeq 40}$

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

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

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

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

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

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 { ilde {p}}(x)}$, entonces la diferencia ${displaystyle p(x)-{ ilde {p}}(x)=(p(x)-f(x))-({ ilde {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 {ar {x}}_{i}}$ maximizador local y en cada N-región ${displaystyle x_{i}}$ se reemplaza con el minimizador local. (Se espera ${displaystyle {ar {x}}_{0}}$ en A, ${displaystyle {ar {x}}_{i}}$ cerca ${displaystyle x_{i}}$ y ${displaystyle {ar {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({ar {x}}_{i})-f({ar {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.

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