Algoritmo de Remez

Algoritmo para aproximar funciones

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 de Chebyshev que sean las mejores en el sentido de la norma uniforme L _∞ . ^[1] A veces se lo conoce como algoritmo de Remes o algoritmo de Reme . ^{[ cita requerida ]}

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 aquel que minimiza la diferencia absoluta máxima entre el polinomio y la función. En este caso, la forma de la solución está precisada por el teorema de equioscilación .

Procedimiento

El algoritmo de Remez comienza con la función que se va a aproximar y un conjunto de puntos de muestra en el intervalo de aproximación, generalmente los extremos del polinomio de Chebyshev mapeados linealmente al intervalo. Los pasos son: ${\displaystyle f}$ ${\displaystyle X}$ ${\displaystyle n+2}$ ${\displaystyle x_{1},x_{2},...,x_{n+2}}$

• Resolver el sistema de ecuaciones lineales

${\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 y E . ${\displaystyle b_{0},b_{1}...b_{n}}$

• Utilice los coeficientes as para formar un polinomio . ${\displaystyle b_{i}}$ ${\displaystyle P_{n}}$
• Encuentra el conjunto de puntos de error máximo local . ${\displaystyle M}$ ${\displaystyle |P_{n}(x)-f(x)|}$
• Si los errores en cada caso tienen la misma magnitud y signos alternados, entonces es el polinomio de aproximación minimax. Si no es así, reemplácelo con y repita los pasos anteriores. ${\displaystyle m\in M}$ ${\displaystyle P_{n}}$ ${\displaystyle X}$ ${\displaystyle M}$

El resultado se llama polinomio de mejor aproximación o algoritmo de aproximación minimax .

W. Fraser ofrece una revisión de los aspectos técnicos de la implementación del algoritmo Remez. ^[2]

Elección de 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 interpolación polinómica. Para la inicialización del problema de optimización para la función f mediante 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} ) siendo

${\displaystyle \lVert L_{n}\rVert _{\infty }={\overline {\Lambda }}_{n}(T)=\max _{-1\leq x\leq 1}\lambda _{n}(T;x),}$

Siendo T los ceros de los polinomios de Chebyshev y las funciones de Lebesgue

${\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 manera similar, , y la optimalidad de una elección de nodos se puede expresar como ${\displaystyle {\underline {\Lambda }}_{n}(T)=\min _{-1\leq x\leq 1}\lambda _{n}(T;x)}$ ${\displaystyle {\overline {\Lambda }}_{n}-{\underline {\Lambda }}_{n}\geq 0.}$

Para los nodos de Chebyshev, que proporcionan una elecció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}}$

( siendo γ 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 , y siendo los ceros de los polinomios de Chebyshev expandidos: ${\displaystyle n\geq 3}$ ${\displaystyle {\hat {T}}}$

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

En esta sección se proporciona más información sobre los pasos descritos anteriormente. En esta sección, el índice i va de 0 a n +1.

Paso 1: Dado , resuelva el sistema lineal de n + 2 ecuaciones ${\displaystyle x_{0},x_{1},...x_{n+1}}$

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

para las incógnitas y E . ${\displaystyle b_{0},b_{1},...b_{n}}$

Debe quedar claro que en esta ecuación solo tiene sentido si los nodos están ordenados , ya sea 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 operaciones aritméticas mientras que un solucionador estándar de la biblioteca realizaría operaciones. Aquí está la prueba simple: ${\displaystyle (-1)^{i}E}$ ${\displaystyle x_{0},...,x_{n+1}}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{3})}$

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

${\displaystyle p_{1}(x_{i})=f(x_{i}),p_{2}(x_{i})=(-1)^{i},i=0,...,n.}$

Para ello se utiliza cada vez la fórmula de interpolación de Newton con las diferencias divididas de orden y operaciones aritméticas. ${\displaystyle 0,...,n}$ ${\displaystyle O(n^{2})}$

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

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

${\displaystyle p(x_{i})=p_{1}(x_{i})-p_{2}(x_{i})\!\cdot \!E\ =\ f(x_{i})-(-1)^{i}E,\ \ \ \ i=0,\ldots ,n.}$

Esta es la misma que la ecuación anterior para y para cualquier elección de E . La misma ecuación para i = n +1 es ${\displaystyle i=0,...,n}$

${\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, siempre están bien definidos. ${\displaystyle p(x)\equiv b_{0}+b_{1}x+\ldots +b_{n}x^{n}}$

El error en los n +2 nodos ordenados 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 ningún polinomio de grado n con error menor que E . De hecho, si existiera tal polinomio, llamémoslo , entonces la diferencia seguiría siendo positiva/negativa en los n + 2 nodos y por lo tanto tendría al menos n + 1 ceros, lo cual es imposible para un polinomio de grado n . Por lo tanto, este E es un límite inferior para el error mínimo que se puede lograr con polinomios de grado n . ${\displaystyle {\tilde {p}}(x)}$ ${\displaystyle p(x)-{\tilde {p}}(x)=(p(x)-f(x))-({\tilde {p}}(x)-f(x))}$ ${\displaystyle x_{i}}$

El paso 2 cambia la notación de a . ${\displaystyle b_{0}+b_{1}x+...+b_{n}x^{n}}$ ${\displaystyle p(x)}$

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

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

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

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

Paso 4: Con y como límite inferior y superior para el mejor error de aproximación posible, se dispone de un criterio de parada fiable: repetir los pasos hasta que sea suficientemente pequeño o deje de disminuir. Estos límites indican el progreso. ${\displaystyle \min \,\{|z_{i}|\}}$ ${\displaystyle \max \,\{|z_{i}|\}}$ ${\displaystyle \max\{|z_{i}|\}-\min\{|z_{i}|\}}$

Variantes

Existen algunas modificaciones del algoritmo en la literatura. ^[10] Estas incluyen:

• Reemplazar más de un punto de muestra con las ubicaciones de las diferencias absolutas máximas cercanas. ^{[ cita requerida ]}
• Reemplazar todos los puntos de muestra en una sola iteración con las ubicaciones de todas las diferencias máximas de signo alternado. ^[11]
• Utilizando el error relativo para medir la diferencia entre la aproximación y la función, especialmente si la aproximación se utilizará para calcular la función en una computadora que utiliza aritmética de punto flotante ;
• Incluyendo restricciones de puntos de error cero. ^[11]
• La variante Fraser-Hart, utilizada para determinar la mejor aproximación racional de Chebyshev. ^[12]

Véase también

• Portal de matemáticas

• Lema de Hadamard
• Serie de Laurent  – ​​Serie de potencias con potencias negativas
• Aproximación de Padé  : 'Mejor' aproximación de una función mediante una función racional de orden dado
• Serie de Newton  : Análogo discreto de una derivadaPages displaying short descriptions of redirect targets
• Teoría de aproximación  : teoría para obtener cálculos matemáticos inexactos aceptablemente cercanos
• Aproximación de funciones  : aproximación de una función arbitraria con una función que se comporta bien

Referencias

1. E.Ya. Remez, "Sur la determinación de polinômes d'approximation de degré donnée", Comm. Soc. Matemáticas. Jarkov 10 , 41 (1934);
   "Sur un procédé convergent d'approximations sucesivas para determinar los polinômes d'approximation, Compt. Rend. Acad. Sc. 198 , 2063 (1934);
   "Sur le calcul effectiv des polynômes d'approximation des Tschebyscheff", Compt. Rend. Academia Sc. 199 , 337 (1934).
2. Fraser, W. (1965). "Un estudio de métodos de cálculo de aproximaciones polinómicas minimax y casi minimax para funciones de una sola variable independiente". J. ACM . 12 (3): 295–314. doi : 10.1145/321281.321282 . S2CID  2736060.
3. Kilgore, TA (1978). "Una caracterización de la proyección de interpolación de Lagrange con norma mínima de Tchebycheff". J. Approach. Theory . 24 (4): 273–288. doi :10.1016/0021-9045(78)90013-8.
4. de Boor, C.; Pinkus, A. (1978). "Prueba de las conjeturas de Bernstein y Erdös relativas a los nodos óptimos para la interpolación polinómica". Journal of Approximation Theory . 24 (4): 289–303. doi : 10.1016/0021-9045(78)90014-X .
5. Luttmann, FW; Rivlin, TJ (1965). "Algunos experimentos numéricos en la teoría de la interpolación polinómica". IBM J. Res. Dev . 9 (3): 187–191. doi :10.1147/rd.93.0187.
6. T. Rivlin, "Las constantes de Lebesgue para la interpolación polinómica", en Actas de la Conferencia Internacional sobre Análisis Funcional y su Aplicación , editado por HG Garnier et al. (Springer-Verlag, Berlín, 1974), pág. 422; Los polinomios de Chebyshev (Wiley-Interscience, Nueva York, 1974).
7. Brutman, L. (1978). "Sobre la función de Lebesgue para interpolación polinómica". SIAM J. Numer. Anal . 15 (4): 694–704. Bibcode :1978SJNA...15..694B. doi :10.1137/0715046.
8. Günttner, R. (1980). "Evaluación de las constantes de Lebesgue". SIAM J. Numer. Anal . 17 (4): 512–520. Bibcode :1980SJNA...17..512G. doi :10.1137/0717043.
9. David G. Luenberger: Introducción a la programación lineal y no lineal , Addison-Wesley Publishing Company 1973.
10. Egidi, Nadaniela; Fatone, Lorella; Misici, Luciano (2020), Sergeyev, Yaroslav D.; Kvasov, Dmitri E. (eds.), "Un nuevo algoritmo de tipo Remez para la mejor aproximación polinomial", Numerical Computations: Theory and Algorithms , vol. 11973, Cham: Springer International Publishing, págs. 56–69, doi :10.1007/978-3-030-39081-5_7, ISBN 978-3-030-39080-8, S2CID  211159177 , consultado el 19 de marzo de 2022
11. Temes, GC; Barcilon, V.; Marshall, FC (1973). "La optimización de sistemas de banda limitada". Actas del IEEE . 61 (2): 196–234. doi :10.1109/PROC.1973.9004. ISSN  0018-9219.
12. Dunham, Charles B. (1975). "Convergencia del algoritmo Fraser-Hart para la aproximación racional de Chebyshev". Matemáticas de la computación . 29 (132): 1078–1082. doi : 10.1090/S0025-5718-1975-0388732-9 . ISSN  0025-5718.

Enlaces externos

• Aproximaciones Minimax y el algoritmo Remez, capítulo de referencia en la documentación de Boost Math Tools, con enlace a una implementación en C++
• Introducción al procesamiento digital de señales (DSP)
• Aarts, Ronald M .; Vínculo, Carlos; Mendelsohn, Phil y Weisstein, Eric W. "Algoritmo Remez". MundoMatemático .