Algoritmo Remez

El algoritmo Remez (también el algoritmo de reemplazo de Remez) es un algoritmo iterativo para la aproximación uniforme de funciones f ∊ C[ a , b ], basado en el teorema de alternancia de P. L. Chebyshev . Propuesto por E. Ya. Remez en 1934 [1] .

El algoritmo Remez se utiliza en el diseño de filtros FIR [2] .

Fundamentos matemáticos

Teorema de Chebyshev

La base teórica del algoritmo Remez es el siguiente teorema [3] .

Para que algún polinomio de grado a lo sumo sea un polinomio que se desvíe lo mínimo de , es necesario y suficiente que se encuentre al menos un sistema de puntos en el que la diferencia : $P^{*}(x)$ $norte$ ${\ estilo de visualización f \ en C [a, b]}$ $[a,b]$ ${\ estilo de visualización n+2}$ ${\ estilo de visualización \ {x_ {i} \},}$ $a\leq x_{0}<x_{1}<\dots <x_{n+1}\leq b,$ $f(x)-P^{*}(x)$

toma alternativamente los valores de diferentes signos,
alcanza el valor máximo por módulo . $[a,\b]$

Tal sistema de puntos se llama alternancia de Chebyshev .

P. L. Chebyshev , 1854

El teorema de de la Vallée-Poussin

Sea E n el valor de la mejor aproximación de la función f ( x ) por polinomios de grado n . E n se estima a partir de abajo mediante el siguiente teorema [4] :

Si para una función f ∊ C[ a , b ] algún polinomio P ( x ) de grado n tiene la propiedad de que la diferencia f ( x ) - P ( x ) sobre algún sistema de n + 2 puntos ordenados x i toma valores con signos alternos, entonces

E_{n}(f)\geq \min |f(x_{i})-P(x_{i})|.

Sh.-Zh. Vallée Poussin, 1919

Algoritmo

Considere un sistema de funciones , una secuencia de puntos y busque un polinomio de aproximación $n+1$ ${\displaystyle \mathbf {\varPhi } =\{\varphi _{0},\dots ,\varphi _{n}\))$ ${\ estilo de visualización n+2}$ $X=\{x_{i}\},$ $a\leq x_{0}<x_{1}<\dots <x_{n+1}\leq b,$

{\displaystyle P_{X}=\sum_{0}^{n}a_{j}\varphi_{j))

Resolvemos un sistema de ecuaciones lineales para y : $a_{j}$ $d$
$\sum _{j=0}^{n}a_{j}\varphi _{j}(x_{i})+(-1)^{i}d=f(x_{i}), \quad i=0,1,\ldots,n.$
Encontramos un punto tal que . $\xi$ $D=f(\xi )-P(\xi )=\max$
Reemplazamos uno de los puntos en X por ξ de tal forma que el signo f - P se alterna en los puntos de la nueva sucesión. En la práctica, solo se aseguran de que los puntos x i estén ordenados en cada iteración [5] .
Repita todos los pasos desde el principio hasta que no haya | re | = re .

En el segundo paso, podemos buscar no solo un punto ξ , sino un conjunto Ξ de puntos donde los máximos locales | f - P |. Si todos los errores en los puntos del conjunto Ξ tienen el mismo valor absoluto y alternan el signo, entonces P es un polinomio minimax. De lo contrario, reemplazamos puntos de X con puntos de Ξ y repetimos el procedimiento nuevamente.

Selección de puntos de partida

Como secuencia inicial X , puede elegir puntos uniformemente distribuidos en [ a , b ]. También es recomendable tomar puntos [6] :

x_{i}={\frac {a+b}{2}}+{\frac {ba}{2}}\cos \left({\frac {\pi i}{n+1}} \right),\quad i=0,\ldots,n+1.

Modificación

Si la función de aproximación se busca en forma de polinomio, entonces en lugar de resolver el sistema en el primer paso del algoritmo, se puede utilizar el siguiente método [7] :

Encuentre un polinomio q ( x ) de grado n+1 tal que q ( x i ) = f ( x i ) ( problema de interpolación ).
También encontramos un polinomio q * ( x ) de grado n+1 tal que q * ( x i ) = (-1) i .
Eligiendo d para que el polinomio P ( x ) ≡ q ( x ) - d q * ( x ) tenga grado n , obtenemos P ( x i ) + (-1) i d = f ( x i ).

Luego se repiten los pasos según el esquema principal.

Condición de parada

Dado que por el teorema de de la Vallée-Poussin | re | ≤ E n ( f ) ≤ D , entonces la condición de parada del algoritmo puede ser D — | re | ≤ ε para algunos ε preasignados .

Convergencia

El algoritmo de Remez converge a razón de una progresión geométrica en el siguiente sentido [8] :

Para cualquier función f ∊ C[ a , b ] existen números A > 0 y 0 < q < 1 tales que las máximas desviaciones de la función f ( x ) de los polinomios construidos por este algoritmo satisfarán las desigualdades $P_{n}^{(k)}(x)$

\max |f(x)-P_{n}^{(k)}(x)|-E_{n}(f)\leq Aq^{k},\quad k=1,2,\ puntos,

donde E n ( f ) es el valor de la mejor aproximación en [ a , b ] de la función f ( x ) usando polinomios P n ( x ).

E. Ya. Remez , 1957

Ejemplo

F ( X ) = mi X , norte = 1, PAGS ( X ) = un X + segundo .

Paso 1.

x1_ _	−1	0	una
f ( x yo )	0.368	1.000	2.718

{\begin{casos}({-}1)a+b+d=0,368\\(0)a+bd=1,000\\(1)a+b+d=2,718\end{casos))

La solución del sistema da P = 1,175 x + 1,272, d = 0,272.
re = máx|e ξ - PAGS ( ξ )| = 0,286 en ξ = 0,16.

Paso 2

x2_ _	−1	0.16	una
f ( x yo )	0.368	1.174	2.718

{\begin{casos}({-}1)a+b+d=0,368\\(0,16)a+bd=1,174\\(1)a+b+d=2,718\end{casos))

La solución del sistema da P = 1,175 x + 1,265, d = 0,279.
re = máx|e ξ - PAGS ( ξ )| = 0,279 en ξ = 0,16.

Dado que se obtuvo el mismo punto dentro de la precisión dada, el polinomio encontrado debe considerarse como la mejor aproximación del primer grado de la función e x .

Véase también

Teorema de aproximación de Weierstrass

Notas

↑ E. Ya. Remes (1934). Sur le calful effectif des polynômes d'approximation de Tschebyscheff. CP París 199, 337-340; cap. 3:78
↑ Rabiner, 1978 , pág. 157.
↑ Dzyadyk, 1977 , pág. 12
↑ Dzyadyk, 1977 , pág. 33.
↑ Laurent, 1975 , pág. 117.
↑ Dzyadyk, 1977 , pág. 74.
↑ Laurent, 1975 , pág. 112.
↑ Dzyadyk, 1977 , pág. 76-77.

Literatura

DeVore RA, Lorentz GG Aproximación constructiva. — 1993.
Bronstein I. N., Semendyaev K. A. Manual de matemáticas para ingenieros y estudiantes de universidades técnicas. — 1980.
Dzyadyk VK Introducción a la teoría de la aproximación uniforme de funciones por polinomios. — 1977.
Laurent P.-J. Aproximación y optimización. — 1975.
Rabiner L., Gould B. Teoría y aplicación del procesamiento de señales digitales. — 1978.
Remez E. Ya. Fundamentos de los métodos numéricos de la aproximación de Chebyshev. — 1969.
Nadaniela Egidi, Lorella Fatone, Luciano Misici . A New Remez-Type Algorithm for Best Polynomial Aproximation // Numerical Computations: Theory and Algorithms: Third International Conference, NUMTA 2019, Crotone, Italy, 15 al 21 de junio de 2019, artículos seleccionados revisados, parte I , junio de 2019, páginas 56– 69 doi // Programa NUMTA 2019 , 19 de junio, miércoles por la mañana (9.00): Sala 1 // Libro de resúmenes, página 50 // libros google, páginas 56-57, 60-64, 67-69