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 ∞.
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.
El algoritmo de Remez comienza con la función a ser aproximada
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 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
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.
, resolver el sistema lineal de n+2 ecuaciones Debe quedar claro que
Entonces este sistema lineal tiene una solución única (como es bien sabido, no todos los sistemas lineales tienen una solución).
operaciones aritméticas mientras que un solucionador estándar tomaría
Una prueba simple: Calcule el interpolador estándar de n-ésimo grado
en los primeros n+1 nodos y también el grado interpolador estándar n-ésimo
y, por lo tanto, no hay más ceros entre
también es un polinomio de grado ny Esto es lo mismo que la ecuación anterior para
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
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
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 .
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.
como el nuevo límite inferior para el mejor error posible con polinomios de grado n .
es útil como un límite superior obvio para ese mejor error posible.
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
es suficientemente pequeño o ya no disminuye.
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.