Teoría de la aproximación

Error entre el polinomio óptimo y log(x) (rojo), y la aproximación de Chebyshev y log(x) (azul) en el intervalo [2, 4]. Las divisiones verticales son de 10⁻⁵. El error máximo para el polinomio óptimo es de 6.07 × 10⁻⁵

Error entre el polinomio óptimo y exp(x) (rojo), y la aproximación de Chebyshev y exp(x) (azul) durante el intervalo [−1, 1]. Las divisiones verticales son de 10⁻⁴. El error máximo para el polinomio óptimo es 5.47 × 10⁻⁴

En matemáticas, la teoría de la aproximación se refiere a cómo las funciones pueden ser aproximadas con otras funciones más simples, incluyendo la caracterización cuantitativa del error introducido. Debe tenerse en cuenta que lo que se entiende por mejor y más simple depende del uso que quiera darse a la aproximación, y de los recursos de cálculo necesarios.^[1]

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

Un problema de particular interés es el de aproximar una función en una biblioteca matemática de una computadora, utilizando operaciones que pueden realizarse fácilmente en el dispositivo (por ejemplo, la suma y la multiplicación), de modo que el resultado sea lo más cercano posible a la función buscada. Esto normalmente se hace con aproximaciones polinómicas o racionales (relación de polinomios).

El objetivo es hacer que la aproximación sea lo más cercana posible a la función real, generalmente con una precisión cercana a la de la aritmética en coma flotante de la computadora subyacente. Esto se logra mediante el uso de un polinomio de alto grado, y/o estrechando el dominio sobre el que el polinomio tiene que aproximar la función.

La reducción del dominio a menudo se puede hacer mediante el uso de varias fórmulas de adición o escalado para la función que se aproxima. Las bibliotecas matemáticas modernas a menudo reducen el dominio en muchos segmentos pequeños y usan un polinomio de bajo grado para cada segmento.

El problema de la aproximación surgió muy temprano en geometría, para las funciones trigonométricas: son funciones cuyas propiedades conocemos (paridad, diferenciabilidad, valores en puntos particulares) pero que no se expresan a partir de operaciones que se pueden realizar a mano (las cuatro operaciones). Esto llevó a la noción de desarrollo en serie. Así, se crearon las tablas trigonométricas, luego, con un enfoque similar, las tablas logarítmicas y, en general, tablas para funciones comúnmente utilizadas en ciencia, como la raíz cuadrada.

Un problema particularmente interesante es el de aproximar funciones por otras definidas únicamente a partir de operaciones informáticas básicas, como la suma y la multiplicación, para crear bibliotecas de funciones matemáticas cuya ejecución produzca valores lo más cercanos posible a los valores teóricos. Esto se llama aproximación polinómica o racional (es decir, uso de funciones racionales).

El objetivo es proporcionar una aproximación lo más precisa posible de una función real dada, para proporcionar los valores más exactos posibles, con la precisión de la aritmética de coma flotante de una computadora. Este objetivo se logra utilizando un polinomio de alto grado y/o reduciendo el dominio sobre el cual el polinomio debe aproximarse a la función. A menudo se puede realizar una reducción de dominio, aunque esto requiere una composición por otras funciones afines (lineales) de la función que se va a aproximar. Las bibliotecas matemáticas modernas a menudo reducen el dominio dividiéndolo en múltiples segmentos pequeños y emplean un polinomio de bajo grado en cada segmento.

Una vez elegidos el dominio y el grado del polinomio, se elige el polinomio en sí para minimizar el error en el peor de los casos. En otras palabras, si $f$ es la función real y $P$ el polinomio que debe tender a $f$ , debemos minimizar el límite superior de la función $|P-f|$ en el dominio. Para una función “adecuada”, un polinomio óptimo de grado $N$ se caracteriza por una curva de error cuyo valor oscila entre $+ ε$ y $- ε$ y que cambia de signo $N + 1$ veces, dando un error en los peores casos de $ε$ . Es posible construir funciones $f$ para las cuales esta propiedad no se cumple, pero en la práctica generalmente es cierta.

Polinomios óptimos

Una vez que se elige el dominio (típicamente un intervalo) y el grado del polinomio, el polinomio en sí se elige de tal manera que se minimice el error del peor de los casos. Es decir, el objetivo es minimizar el valor máximo de $\mid P(x)-f(x)\mid$ , donde P(x) es el polinomio de la aproximación, f(x) es la función real, y x varía en el intervalo elegido. Para funciones con buen comportamiento, existe un polinomio de grado N-ésimo que conducirá a una curva de error que oscila entre $+\varepsilon$ y $-\varepsilon$ un total de N+2 veces, lo que da una cota del peor resultado del error $\varepsilon$ . Se ve que existe un polinomio de grado N-ésimo que puede interpolar N+1 puntos en una curva. Tal polinomio es siempre óptimo. Es posible encontrar funciones artificiales f(x) para las cuales no existe tal polinomio, pero raramente se suelen dar en la práctica.^[3]

Por ejemplo, los gráficos situados a la derecha muestran el error al aproximar log(x) y exp(x) para N = 4. Las curvas rojas, para el polinomio óptimo, establecen un nivel de referencia, es decir, oscilan entre $+\varepsilon$ y $-\varepsilon$ exactamente. Debe tenerse en cuenta que, 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.

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

Para demostrar que esto es cierto en general, supóngase 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 alternos y magnitudes iguales. El gráfico rojo a la derecha muestra cómo podría ser esta función de error para N = 4. Supóngase 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 se sitúa un extremo de P-f, entonces

|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

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 se produce un mínimo de P-f en x_i , entonces

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}).

Entonces, como se puede ver en el gráfico, [P(x) - f(x)] - [ Q (x) - f(x)] debe alternar en el signo de 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 el signo al menos N+1 veces, por lo que, por el Teorema del valor intermedio, tiene N+1 ceros, lo que es imposible para un polinomio de grado N.^[4]

Aproximación de Chebyshev

Se pueden obtener polinomios muy cercanos al óptimo expandiendo la función dada en términos de los polinomios de Chebyshev y luego cortando la expansión en el grado deseado.^[5]

Este enfoque 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:

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

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

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 un término, el error total que surge del corte está cerca del 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 otros tipos de polinomios. Si una expansión de Chebyshev se corta después de $T_{N}$ , el error tomará una forma cercana a un múltiplo de $T_{N+1}$ . Los polinomios de Chebyshev tienen la propiedad de que están nivelados: oscilan entre +1 y −1 en el intervalo [−1, 1]. $T_{N+1}$ tiene N+2 niveles extremos. Esto significa que el error entre f(x) y su expansión de Chebyshev a $T_{N}$ está cerca de una función de nivel con N+2 extremos, por lo que está cerca del polinomio óptimo de N-ésimo grado.

En los gráficos anteriores, debe tenerse en cuenta que la función de error azul es a veces mejor (está más próxima) que la función roja, pero a veces es peor, lo que significa que no es el polinomio óptimo. Téngase en cuenta también que la discrepancia es menos grave para la función exp, que tiene una serie de potencias convergente extremadamente rápida, que para la función de registro.

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

Algoritmo de Remez

El algoritmo Remez (a veces escrito Remes) se usa 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 N+2 niveles extremos. Según el teorema anterior, este polinomio es óptimo.^[7]

El algoritmo de Remez utiliza el hecho de que se puede construir un polinomio de grado N-ésimo que conduce a niveles y valores de error alternos, dados los N+2 puntos de referencia.

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

{\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 de la derecha se alternan en señal, es decir

{\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 $x_{1}$ , ..., $x_{N+2}$ son datos dados, todqs sus potencias son conocidas, y $f(x_{1})$ , ..., $f(x_{N+2})$ también son conocidos. Eso significa que las ecuaciones anteriores son solo N+2 ecuaciones lineales en las N+2 variables $P_{0}$ , $P_{1}$ , ..., $P_{N}$ y $\varepsilon$ . Dados los puntos de referencia $x_{1}$ , ..., $x_{N+2}$ , se puede resolver este sistema para obtener el polinomio Py el número $\varepsilon$ .

El siguiente gráfico muestra un ejemplo de esta configuración, produciendo un polinomio de cuarto grado que se aproxima a $e^{x}$ sobre [−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 de $\varepsilon$ es 4.43 × 10⁻⁴

Téngase en cuenta que el gráfico de error toma los valores $\pm \varepsilon$ en los seis puntos de prueba, incluidos los puntos finales, pero que 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.

El segundo paso del algoritmo de Remez consiste en mover los puntos de prueba a las ubicaciones aproximadas donde la función de error tenía sus máximos o mínimos locales reales. Por ejemplo, al observar el gráfico se puede decir que el punto en −0.1 debería haber estado en aproximadamente −0.28. La forma de hacer esto en el algoritmo es usar un solo paso del método de Newton. Como se conoce la primera y la segunda derivada de P(x) − f(x), se puede calcular aproximadamente hasta qué punto se debe mover un punto de prueba para que la derivada sea cero.

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

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

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

Revistas principales

Journal of Approximation Theory
Constructive Approximation
East Journal on Approximations

Véase también

Referencias

↑ Approximation Theory, Volumen 36. American Mathematical Soc. 1986. p. X de 131. ISBN 9780821800980. Consultado el 12 de diciembre de 2019.
↑ Encyclopaedia of Mathematics (set). Springer Science & Business Media. 1994. pp. 155 de 5402. ISBN 9781556080104. Consultado el 12 de diciembre de 2019.
↑ Olavi Nevanlinna (2012). Convergence of Iterations for Linear Equations. Birkhäuser. p. 64. ISBN 97830348854 |isbn= incorrecto (ayuda). Consultado el 12 de diciembre de 2019.
↑ Nathaniel Max Rock (2007). Standards Driven Math: Calculus. Team Rock Press. pp. 23 de 120. ISBN 9781599800325. Consultado el 12 de diciembre de 2019.
↑ Fauziahanim Che Seman (2004). Chebyshev Approximation of Discrete Polynomials and Splines. Kolej Universiti Teknologi Tun Hussein Onn. p. 75. Consultado el 12 de diciembre de 2019.
↑ G. Nurnberger (1997). Multivariate Approximation and Splines. Springer Science & Business Media. pp. 153 de 324. ISBN 9783764356545. Consultado el 12 de diciembre de 2019.
↑ ^a ^b Jean-Michel Muller (2006). Elementary Functions: Algorithms and Implementation. Springer Science & Business Media. pp. 41 de 266. ISBN 9783034885478. Consultado el 12 de diciembre de 2019.

Bibliografía

N. I. Achiezer (Akhiezer), Theory of approximation, Translated by Charles J. Hyman Frederick Ungar Publishing Co., New York 1956 x+307 pp.
A. F. Timan, Theory of approximation of functions of a real variable, 1963 ISBN 0-486-67830-X
C. Hastings, Jr. Approximations for Digital Computers. Princeton University Press, 1955.
J. F. Hart, E. W. Cheney, C. L. Lawson, H. J. Maehly, C. K. Mesztenyi, J. R. Rice, H. C. Thacher Jr., C. Witzgall, Computer Approximations. Wiley, 1968, Lib. Cong. 67-23326.
L. Fox and I. B. Parker. "Chebyshev Polynomials in Numerical Analysis." Oxford University Press London, 1968.
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), «Section 5.8. Chebyshev Approximation», Numerical Recipes: The Art of Scientific Computing (3rd edición), New York: Cambridge University Press, ISBN 978-0-521-88068-8 .
W. J. Cody Jr., W. Waite, Software Manual for the Elementary Functions. Prentice-Hall, 1980, ISBN 0-13-822064-6.
E. Remes [Remez], "Sur le calcul effectif des polynomes d'approximation de Tschebyscheff". 1934 C. R. Acad. Sci., Paris, 199, 337-340.
K.-G. Steffens, "The History of Approximation Theory: From Euler to Bernstein," Birkhauser, Boston 2006 ISBN 0-8176-4353-2.
T. Erdélyi, "Extensions of the Bloch-Pólya theorem on the number of distinct real zeros of polynomials", Journal de théorie des nombres de Bordeaux 20(2008), 281–287.
T. Erdélyi, "The Remez inequality for linear combinations of shifted Gaussians", Math. Proc. Camb. Phil. Soc. 146(2009), 523–530.
L. N. Trefethen, "Approximation theory and approximation practice", SIAM 2013. [1]

Enlaces externos

Historia de la teoría de la aproximación (HAT) Archivado el 18 de septiembre de 2019 en Wayback Machine.
Surveys in Approximation Theory (SAT)

Datos: Q774123

[BOOR-1] Approximation Theory, Volumen 36. American Mathematical Soc. 1986. p. X de 131. ISBN 9780821800980. Consultado el 12 de diciembre de 2019.

[ENMAT-2] Encyclopaedia of Mathematics (set). Springer Science & Business Media. 1994. pp. 155 de 5402. ISBN 9781556080104. Consultado el 12 de diciembre de 2019.

[OLAVI-3] Olavi Nevanlinna (2012). Convergence of Iterations for Linear Equations. Birkhäuser. p. 64. ISBN 97830348854 |isbn= incorrecto (ayuda). Consultado el 12 de diciembre de 2019.

[MAX-4] Nathaniel Max Rock (2007). Standards Driven Math: Calculus. Team Rock Press. pp. 23 de 120. ISBN 9781599800325. Consultado el 12 de diciembre de 2019.

[5] Fauziahanim Che Seman (2004). Chebyshev Approximation of Discrete Polynomials and Splines. Kolej Universiti Teknologi Tun Hussein Onn. p. 75. Consultado el 12 de diciembre de 2019.

[NURMBERGER-6] G. Nurnberger (1997). Multivariate Approximation and Splines. Springer Science & Business Media. pp. 153 de 324. ISBN 9783764356545. Consultado el 12 de diciembre de 2019.

[MULLER-7] Jean-Michel Muller (2006). Elementary Functions: Algorithms and Implementation. Springer Science & Business Media. pp. 41 de 266. ISBN 9783034885478. Consultado el 12 de diciembre de 2019.

[1]

[2]

[3]

[4]

[5]

[6]

[7]