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 . El algoritmo de Remez comienza con la función a ser aproximada f {\displaystyle f} y un conjunto X {\displaystyle X} de n + 2 {\displaystyle n+2} puntos de muestra x 1 , x 2 , . . . , x n + 2 {\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. 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 Ln(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 Ln de los nodos (t1, ..., tn+1 ) sea: T son los ceros de los polinomios de Chebyshev, y las funciones de Lebesgue son Theodore A. Kilgore, Carl de Boor y Allan Pinkus demostraron que existe un ti único para cada Ln, aunque no se conoce explícitamente para polinomios (ordinarios). De manerasimilar, Λ _ n ( T ) = min − 1 ≤ x ≤ 1 λ n ( T ; x ) {\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 Λ ¯ n − Λ _ n ≥ 0. {\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 (γ es la constante de Euler-Mascheroni) con y límite superior Lev Brutman obtuvo el límite para n ≥ 3 {\displaystyle n\geq 3} y T ^ {\displaystyle {\hat {T}}} siendo los ceros de los polinomios de Chebyshev expandidos: