Algoritmo de Remez

El algoritmo de Remez o algoritmo de intercambio de Remez , publicado por Evgeny Yakovlevich Remez en 1934, es un algoritmo iterativo que se utiliza para encontrar aproximaciones simples de funciones, específicamente, aproximaciones de funciones en un espacio de Chebyshev que son las mejores en el sentido de la norma uniforme L _∞ . ^{[ 1 ]} A veces se le denomina algoritmo de Remes o algoritmo de Reme . ^{[ 2 ]}

Un ejemplo típico de 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 máxima diferencia absoluta 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 que se va a aproximar y un conjunto de puntos de muestra en el intervalo de aproximación, generalmente los extremos de un polinomio de Chebyshev mapeado linealmente al intervalo. Los pasos son: ${\displaystyle f}$${\displaystyle X}$${\displaystyle n+2}$${\displaystyle x_{1},x_{2},...,x_{n+2}}$

• Resuelve 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 como coeficientes 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 punto tienen la misma magnitud y alternan su signo, entonces es el polinomio de aproximación minimax. De lo contrario, reemplácelo por y repita los pasos anteriores.${\displaystyle m\in M}$${\displaystyle P_{n}}$${\displaystyle X}$${\displaystyle M}$

El resultado se denomina 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 de Remez. ^{[ 3 ]}

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 mediante el interpolante de Lagrange L _n ( f ), se puede demostrar que esta aproximación inicial está acotada por

${\displaystyle \lVert f-L_{n}(f)\rVert _{\infty }\leq (1+\lVert L_{n}\rVert _{\infty })\inf _{p\in P_{n}}\lVert fp\rVert }$

siendo la norma o constante de Lebesgue del operador de interpolación de Lagrange L _n de los nodos ( t ₁ , ..., t _{n  + 1} )

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

${\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, ^{[ 4 ]} Carl de Boor y Allan Pinkus ^{[ 5 ]} demostraron que existe un único t _i 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 ^{[ 6 ].}

${\displaystyle {\overline {\Lambda }}_{n}(T)={\frac {2}{\pi }}\log(n+1)+{\frac {2}{\pi }}\left(\gamma +\log {\frac {8}{\pi }}\right)+\alpha _{n+1}}$

(donde γ es la constante de Euler-Mascheroni ) con

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

y límite superior ^{[ 7 ]}

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

Lev Brutman ^{[ 8 ]} obtuvo la cota para , 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 ^{[ 9 ]} obtuvo a partir de una estimación más precisa para${\displaystyle n\geq 40}$

${\displaystyle {\overline {\Lambda }}_{n}({\hat {T}})-{\underline {\Lambda }}_{n}({\hat {T}})<0.0196.}$

Esta sección 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 , resuelve 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 esta ecuación solo tiene sentido si los nodos están ordenados , ya sea de forma estrictamente creciente o estrictamente decreciente. En ese caso, este sistema lineal tiene una solución única. (Como es bien sabido, no todos los sistemas lineales tienen solución). Además, la solución se puede obtener con solo operaciones aritméticas, mientras que un solucionador estándar de la biblioteca requeriría operaciones. He aquí la demostración simple: ${\displaystyle (-1)^{i}E}$${\displaystyle x_{0},...,x_{n+1}}$${\displaystyle O(n^{2})}$${\displaystyle O(n^{3})}$

Calcular 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, utilice en cada caso la fórmula de interpolación de Newton con las diferencias divididas de orden y las operaciones aritméticas. ${\displaystyle 0,...,n}$${\displaystyle O(n^{2})}$

El polinomio tiene su i -ésimo cero entre y , y por lo tanto no tiene 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 es también 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 ecuación que la 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 requiere 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 alternativamente porque

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

El teorema de equioscilación establece que, bajo esta condición, no existe ningún polinomio de grado n con un error menor que E. De hecho, si existiera tal polinomio, llamémoslo , la diferencia seguiría siendo positiva/negativa en los nodos n + 2 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 una cota 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 por el maximizador local y en cada región N se reemplaza por el minimizador local. (Espere en A , cerca de y en B ). No se requiere alta precisión aquí; la búsqueda lineal estándar con un par de ajustes cuadráticos debería ser suficiente. (Véase ^{[ 10 ]} ) ${\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 la nueva cota 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ímites inferior y superior para el mejor error de aproximación posible , se tiene 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}|\}}$

En la literatura se encuentran algunas modificaciones del algoritmo. ^{[ 11 ]} Estas incluyen:

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

• Lema de Hadamard  – TeoremaPages displaying short descriptions with no spaces
• Serie Laurent  – ​​Serie de poder con poderes negativos
• Aproximante de Padé  : la mejor aproximación de una función mediante una función racional de orden dado.
• Serie de Newton  : análogo discreto de una derivada.Pages displaying short descriptions of redirect targets
• Teoría de la aproximación  : teoría para obtener cálculos matemáticos inexactos con una aproximación aceptable.
• Aproximación de funciones  : aproximar una función arbitraria con una función bien comportada.

• Aproximaciones minimax y el algoritmo de Remez , capítulo introductorio en la documentación de Boost Math Tools, con enlace a una implementación en C++.
• Introducción al DSP Archivado el 23/04/2014 en Wayback Machine
• Aarts, Ronald M .; Vínculo, Carlos; Mendelsohn, Phil y Weisstein, Eric W. "Algoritmo Remez" . MundoMatemático .