Teoría de aproximación

Teoría para obtener cálculos matemáticos aceptablemente cercanos e inexactos

En matemáticas , la teoría de aproximación se ocupa de cómo se pueden aproximar mejor las funciones con funciones más simples y de caracterizar cuantitativamente los errores introducidos por ellas. Lo que se entiende por mejor y más simple dependerá de la aplicación.

Un tema estrechamente relacionado es la aproximación de funciones mediante series de Fourier generalizadas , es decir, aproximaciones basadas en la suma de una serie de términos basados ​​en polinomios ortogonales .

Un problema de particular interés es el de aproximar una función en una biblioteca matemática informática , utilizando operaciones que se pueden realizar en la computadora o calculadora (por ejemplo, suma y multiplicación), de modo que el resultado sea lo más cercano posible a la función real. Esto se hace típicamente con aproximaciones polinómicas o racionales (cociente de polinomios).

El objetivo es hacer que la aproximación sea lo más cercana posible a la función real, normalmente con una precisión cercana a la de la aritmética de punto flotante de la computadora subyacente . Esto se logra utilizando un polinomio de alto grado y/o acotando el dominio sobre el cual el polinomio tiene que aproximarse a la función. A menudo, el acotación del dominio se puede realizar mediante el uso de varias fórmulas de adición o escalamiento para la función que se está aproximando. Las bibliotecas matemáticas modernas a menudo reducen el dominio en muchos segmentos diminutos y utilizan un polinomio de bajo grado para cada segmento.

Polinomios óptimos

Una vez que se eligen el dominio (normalmente un intervalo) y el grado del polinomio, el propio polinomio se elige de tal forma que minimice el error en el peor de los casos. Es decir, el objetivo es minimizar el valor máximo de , donde P ( x ) es el polinomio de aproximación, f ( x ) es la función real y x varía en el intervalo elegido. Para funciones que se comportan bien, existe un polinomio de grado N que conducirá a una curva de error que oscila entre y un total de N +2 veces, dando un error en el peor de los casos de . Se ve que existe un polinomio de grado N que puede interpolar N +1 puntos en una curva. El teorema de equioscilación afirma que un polinomio de este tipo siempre es óptimo . Es posible crear funciones artificiales f ( x ) para las que no existe dicho polinomio, pero esto ocurre raramente en la práctica. ${\displaystyle \mid P(x)-f(x)\mid }$ ${\displaystyle +\varepsilon }$ ${\displaystyle -\varepsilon }$ ${\displaystyle \varepsilon }$

Por ejemplo, los gráficos que se muestran a la derecha muestran el error en la aproximación de log(x) y exp(x) para N  = 4. Las curvas rojas, para el polinomio óptimo, están niveladas , es decir, oscilan entre y exactamente. En cada caso, el número de extremos es N +2, es decir, 6. Dos de los extremos están en los puntos finales del intervalo, en los bordes izquierdo y derecho de los gráficos. ${\displaystyle +\varepsilon }$ ${\displaystyle -\varepsilon }$

Error P ( x ) −  f ( x ) para el polinomio de nivel (rojo) y para el supuesto polinomio mejor (azul)

Para demostrar que esto es cierto en general, supongamos que P es un polinomio de grado N que tiene la propiedad descrita, es decir, da lugar a una función de error que tiene N  + 2 extremos, de signos alternados y magnitudes iguales. El gráfico rojo a la derecha muestra cómo se vería esta función de error para N  = 4. Supongamos que Q ( x ) (cuya función de error se muestra en azul a la derecha) es otro polinomio de grado N que es una mejor aproximación a f que P . En particular, Q está más cerca de f que P para cada valor x _i donde ocurre un extremo de P − f , por lo que

${\displaystyle |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|.}$

Cuando se produce un máximo de P − f en x _i , entonces

${\displaystyle Q(x_{i})-f(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=P(x_{i})-f(x_{i}),}$

Y cuando ocurre un mínimo de P − f en x _i , entonces

${\displaystyle f(x_{i})-Q(x_{i})\leq |Q(x_{i})-f(x_{i})|<|P(x_{i})-f(x_{i})|=f(x_{i})-P(x_{i}).}$

Así, como se puede ver en el gráfico, [ P ( x ) −  f ( x )] − [ Q ( x ) −  f ( x )] debe alternar en signo para los N  + 2 valores de x _i . Pero [ P ( x ) −  f ( x )] − [ Q ( x ) −  f ( x )] se reduce a P ( x ) −  Q ( x ) que es un polinomio de grado N . Esta función cambia de signo al menos N +1 veces por lo que, por el teorema del valor intermedio , tiene N +1 ceros, lo cual es imposible para un polinomio de grado N .

Aproximación de Chebyshev

Se pueden obtener polinomios muy cercanos al óptimo desarrollando la función dada en términos de polinomios de Chebyshev y luego cortando la expansión en el grado deseado. Esto es similar al análisis de Fourier de la función, utilizando los polinomios de Chebyshev en lugar de las funciones trigonométricas habituales.

Si se calculan los coeficientes en la expansión de Chebyshev para una función:

${\displaystyle f(x)\sim \sum _{i=0}^{\infty }c_{i}T_{i}(x)}$

y luego se corta la serie después del término, se obtiene un polinomio de grado N que se aproxima a f ( x ) . ${\displaystyle T_{N}}$

La razón por la que este polinomio es casi óptimo es que, para funciones con series de potencias que convergen rápidamente, si la serie se corta después de algún término, el error total que surge del corte es cercano al primer término después del corte. Es decir, el primer término después del corte domina todos los términos posteriores. Lo mismo es cierto si la expansión es en términos de polinomios de contrapunto. Si una expansión de Chebyshev se corta después de , el error tomará una forma cercana a un múltiplo de . Los polinomios de Chebyshev tienen la propiedad de que son niveles: oscilan entre +1 y −1 en el intervalo [−1, 1]. tiene N +2 extremos de nivel. Esto significa que el error entre f ( x ) y su expansión de Chebyshev hasta es cercano a una función de nivel con N +2 extremos, por lo que es cercano al polinomio de grado N óptimo . ${\displaystyle T_{N}}$ ${\displaystyle T_{N+1}}$ ${\displaystyle T_{N+1}}$ ${\displaystyle T_{N}}$

En los gráficos anteriores, la función de error azul a veces es mejor que (dentro de) la función roja, pero a veces es peor, lo que significa que no es exactamente el polinomio óptimo. La discrepancia es menos grave para la función exp, que tiene una serie de potencias que converge extremadamente rápido, que para la función logaritmo.

La aproximación de Chebyshev es la base de la cuadratura de Clenshaw-Curtis , una técnica de integración numérica .

Algoritmo de Remez

El algoritmo Remez (a veces escrito Remes) se utiliza para producir un polinomio óptimo P ( x ) que se aproxima a una función dada f ( x ) en un intervalo dado. Es un algoritmo iterativo que converge a un polinomio que tiene una función de error con extremos de nivel N +2. Según el teorema anterior, ese polinomio es óptimo.

El algoritmo de Remez utiliza el hecho de que se puede construir un polinomio de grado N que conduce a valores de error nivelados y alternos, dados N +2 puntos de prueba.

Dados N +2 puntos de prueba , , ... (donde y son presumiblemente los puntos finales del intervalo de aproximación), estas ecuaciones deben resolverse: ${\displaystyle x_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle x_{N+2}}$ ${\displaystyle x_{1}}$ ${\displaystyle x_{N+2}}$

${\displaystyle {\begin{aligned}P(x_{1})-f(x_{1})&=+\varepsilon \\P(x_{2})-f(x_{2})&=-\varepsilon \\P(x_{3})-f(x_{3})&=+\varepsilon \\&\ \ \vdots \\P(x_{N+2})-f(x_{N+2})&=\pm \varepsilon .\end{aligned}}}$

Los lados derechos se alternan en signo.

Eso es,

${\displaystyle {\begin{aligned}P_{0}+P_{1}x_{1}+P_{2}x_{1}^{2}+P_{3}x_{1}^{3}+\dots +P_{N}x_{1}^{N}-f(x_{1})&=+\varepsilon \\P_{0}+P_{1}x_{2}+P_{2}x_{2}^{2}+P_{3}x_{2}^{3}+\dots +P_{N}x_{2}^{N}-f(x_{2})&=-\varepsilon \\&\ \ \vdots \end{aligned}}}$

Dado que se dieron , ..., se conocen todas sus potencias, y , ..., también se conocen. Esto significa que las ecuaciones anteriores son simplemente N +2 ecuaciones lineales en las N +2 variables , , ..., , y . Dados los puntos de prueba , ..., , se puede resolver este sistema para obtener el polinomio P y el número . ${\displaystyle x_{1}}$ ${\displaystyle x_{N+2}}$ ${\displaystyle f(x_{1})}$ ${\displaystyle f(x_{N+2})}$ ${\displaystyle P_{0}}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{N}}$ ${\displaystyle \varepsilon }$ ${\displaystyle x_{1}}$ ${\displaystyle x_{N+2}}$ ${\displaystyle \varepsilon }$

El gráfico siguiente muestra un ejemplo de esto, que produce un polinomio de cuarto grado que se aproxima a [−1, 1]. Los puntos de prueba se establecieron en −1, −0,7, −0,1, +0,4, +0,9 y 1. Esos valores se muestran en verde. El valor resultante es 4,43 × 10 ⁻⁴ ${\displaystyle e^{x}}$ ${\displaystyle \varepsilon }$

Error del polinomio producido por el primer paso del algoritmo de Remez, aproximando e ^x en el intervalo [−1, 1]. Las divisiones verticales son 10 ⁻⁴ .

El gráfico de error efectivamente toma los valores en los seis puntos de prueba, incluidos los puntos finales, pero esos puntos no son extremos. Si los cuatro puntos de prueba interiores hubieran sido extremos (es decir, la función P ( x ) f ( x ) tuviera máximos o mínimos allí), el polinomio sería óptimo. ${\displaystyle \pm \varepsilon }$

El segundo paso del algoritmo de Remez consiste en mover los puntos de prueba a las posiciones aproximadas donde la función de error tuvo sus máximos o mínimos locales reales. Por ejemplo, al observar el gráfico se puede saber que el punto en −0,1 debería haber estado aproximadamente en −0,28. La forma de hacer esto en el algoritmo es usar una sola ronda del método de Newton . Como se conocen las derivadas primera y segunda de P ( x ) − f ( x ) , se puede calcular aproximadamente cuánto se debe mover un punto de prueba para que la derivada sea cero.

Calcular las derivadas de un polinomio es sencillo. También es necesario saber calcular la primera y la segunda derivada de f ( x ). El algoritmo de Remez requiere la capacidad de calcular , y con una precisión extremadamente alta. Todo el algoritmo debe ejecutarse con una precisión mayor que la precisión deseada del resultado. ${\displaystyle f(x)\,}$ ${\displaystyle f'(x)\,}$ ${\displaystyle f''(x)\,}$

Después de mover los puntos de prueba, se repite la parte de la ecuación lineal, obteniendo un nuevo polinomio, y se vuelve a utilizar el método de Newton para mover los puntos de prueba nuevamente. Esta secuencia continúa hasta que el resultado converge con la precisión deseada. El algoritmo converge muy rápidamente. La convergencia es cuadrática para las funciones que se comportan bien: si los puntos de prueba están dentro del resultado correcto, estarán aproximadamente dentro del resultado correcto después de la siguiente ronda. ${\displaystyle 10^{-15}}$ ${\displaystyle 10^{-30}}$

El algoritmo de Remez generalmente comienza eligiendo los extremos del polinomio de Chebyshev como puntos iniciales, ya que la función de error final será similar a ese polinomio. ${\displaystyle T_{N+1}}$

Revistas principales

• Revista de teoría de aproximación
• Aproximación constructiva
• Revista del Este sobre aproximaciones

Véase también

• Teoría de la estimación
• Serie de Fourier
• Aproximación de funciones
• Base ortonormal
• Padé aproximado
• Base de Schauder
• Filtro Kalman

Referencias

• NI Achiezer (Akhiezer) , Teoría de aproximación, Traducido por Charles J. Hyman Frederick Ungar Publishing Co., Nueva York 1956 x+307 pp.
• AF Timan, Teoría de aproximación de funciones de una variable real , 1963 ISBN  0-486-67830-X
• C. Hastings, Jr. Aproximaciones para computadoras digitales . Princeton University Press, 1955.
• JF Hart, EW Cheney , CL Lawson, HJ Maehly, CK Mesztenyi, JR Rice , HC Thacher Jr., C. Witzgall, Aproximaciones por computadora . Wiley, 1968, Lib. Cong. 67–23326.
• L. Fox e IB Parker. "Polinomios de Chebyshev en análisis numérico". Oxford University Press, Londres, 1968.
• Press, WH ; Teukolsky, SA ; Vetterling, WT; Flannery, BP (2007), "Sección 5.8. Aproximación de Chebyshev", Recetas numéricas: el arte de la computación científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8, archivado del original el 10 de abril de 2020 , consultado el 9 de agosto de 2011
• WJ Cody Jr., W. Waite, Manual de software para las funciones elementales . Prentice-Hall, 1980, ISBN 0-13-822064-6 . 
• E. Remes [Remez] , "Sur le calcul effectif des polynomes d'approximation de Tschebyscheff". 1934 CR Acad. Ciencia. , París, 199 , 337–340.
• K.-G. Steffens, "La historia de la teoría de la aproximación: de Euler a Bernstein", Birkhauser, Boston 2006 ISBN 0-8176-4353-2 . 
• T. Erdélyi , "Extensiones del teorema de Bloch-Pólya sobre el número de ceros reales distintos de polinomios", Journal de théorie des nombres de Bordeaux 20 (2008), 281–287.
• T. Erdélyi, "La desigualdad de Remez para combinaciones lineales de gaussianas desplazadas", Math. Proc. Camb. Phil. Soc. 146 (2009), 523–530.
• LN Trefethen , "Teoría de aproximación y práctica de aproximación", SIAM 2013. [1]

Enlaces externos

• Historia de la teoría de aproximación (TAA)
• Encuestas en teoría de aproximación (SAT)