Teoria de l'aproximació

Archiu:Logerror.png

Error entre el polinomi òptim i log(x) (roig), i l'aproximació de Chebyshev i log(x) (blava) en l'interval [2, 4]. Les divisions verticals són de 10⁻⁵. L'error màxim per al polinomi òptim és de 6.07 × 10⁻⁵

Archiu:Experror.png

Error entre el polinomi òptim i exp(x) (roig), i l'aproximació de Chebyshev i exp(x) (blava) durant l'interval [−1, 1]. Les divisions verticals són de 10⁻⁴. L'error màxim per al polinomi òptim és 5.47 × 10⁻⁴

En matemàtiques, la teoria de l'aproximació es referix a cóm les funcions poden ser aproximades en atres funcions més simples, incloent la caracterisació quantitativa del error introduït. Deu tindre's en conte que lo que s'entén per millor i més simple depén de l'us que vullga donar-se a l'aproximació, i dels recursos de càlcul necessaris.^[1]

Un tema estretament relacionat és l'aproximació de funcions per mig de séries de Fourier generalisades, és dir, aproximacions fonamentades en la suma d'una série de térmens basats en polinomis ortogonals.^[2]

Un problema de particular interés és el d'aproximar una funció en una biblioteca matemàtica d'una computadora, utilisant operacions que poden realisar-se fàcilment en el dispositiu (per eixemple, la suma i la multiplicació), de modo que el resultat siga lo més propenc possible a la funció buscada. Açò normalment es fa en aproximacions polinòmiques o racionals (relació de polinomis).

L'objectiu és fer que l'aproximació siga lo més propenca possible a la funció real, generalment en una precisió propenca a la de l'aritmètica en menge flotant de la computadora subjacent. Açò es conseguix per mig de l'us d'un polinomi d'alt grau, i/o estretint el domini sobre el que el polinomi té que aproximar la funció.

La reducció del domini a sovint es pot fer per mig de l'us de vàries fòrmules d'adició o escalat per a la funció que s'aproxima. Les biblioteques matemàtiques modernes a sovint reduïxen el domini en molts segments menuts i usen un polinomi de baix grau per a cada segment.

El problema de l'aproximació va sorgir molt primerenc en geometria, per a les funcions trigonométricas: són funcions les propietats de les quals coneixem (paritat, diferenciabilidad, valors en punts particulars) pero que no s'expressen a partir d'operacions que es poden realisar a mà (les quatre operacions). Açò va dur a la noció de desenroll en série. Aixina, es varen crear les taules trigonométricas, després, en un enfocament similar, les taules logarítmiques i, en general, taules per a funcions comunament utilisades en ciència, com la raïl quadrada.

Un problema particularment interessant és el d'aproximar funcions per atres definides únicament a partir d'operacions informàtiques bàsiques, com la suma i la multiplicació, per a crear biblioteques de funcions matemàtiques l'eixecució de les quals produïxca valors lo més propencs possible als valors teòrics. Açò es diu aproximació polinòmica o racional (és dir, us de funcions racionals).

L'objectiu és proporcionar una aproximació lo més precisa possible d'una funció real donada, per a proporcionar els valors més exactes possibles, en la precisió de l'aritmètica de menge flotant d'una computadora. Este objectiu es conseguix utilisant un polinomi d'alt grau i/o reduint el domini sobre el qual el polinomi deu aproximar-se a la funció. A sovint es pot realisar una reducció de domini, encara que açò requerix una composició per atres funcions afins (llineals) de la funció que es va a aproximar. Les biblioteques matemàtiques modernes a sovint reduïxen el domini dividint-ho en múltiples segments menuts i ampren un polinomi de baix grau en cada segment.

Una volta elegits el domini i el grau del polinomi, s'elegix el polinomi en sí per a minimisar l'error en el pijor dels casos. En atres paraules, si $f$ és la funció real i $P$ el polinomi que deu tendir a $f$ , devem minimisar el llímit superior de la funció $| P - f |$ en el domini. Per a una funció “adequada”, un polinomi òptim de grau $N$ es caracterisa per una curva d'error el valor del qual oscila entre $+ ε$ i $- ε$ i que canvia de signe $N + 1$ voltes, donant un error en els pijors casos de $ε$ . És possible construir funcions $f$ per a les quals esta propietat no es complix, pero en la pràctica generalment és certa.

Polinomis òptims

Una volta que s'elegix el domini (típicament un interval) i el grau del polinomi, el polinomi en sí s'elegix de tal manera que es minimise l'error del pijor dels casos. És dir, l'objectiu és minimisar el valor màxim de $∣ P (x) - f (x) ∣$ , a on P(x) és el polinomi de l'aproximació, f(x) és la funció real, i x varia en l'interval elegit. Per a funcions en bon comportament, existix un polinomi de grau N-ésimo que conduirà a una curva d'error que oscila entre $+ ε$ i $- ε$ un total de N+2 voltes, lo que dona una cota del pijor resultat de l'error $ε$ . Es veu que existix un polinomi de grau N-ésimo que pot interpolar N+1 punts en una curva. Tal polinomi és sempre òptim. És possible trobar funcions artificials f(x) para les quals no existix tal polinomi, pero rarament se solen donar en la pràctica.^[3]

Per eixemple, els gràfics situats a la dreta mostren l'error en aproximar log(x) i exp(x) per a N = 4. Les curves roges, per al polinomi òptim, establixen un nivell de referència, és dir, oscilen entre $+ ε$ i $- ε$ exactament. Deu tindre's en conte que, en cada cas, el número d'extrems és N+2, és dir, 6. Dos dels extrems estan en els punts finals de l'interval, en les vores esquerre i dret dels gràfics.

Archiu:Impossibleerror.png

Error P(x) − f(x) per al polinomi de nivell (roig), i per al supòsit millor polinomi (blau).

Per a demostrar que açò és cert en general, suponga's que P és un polinomi de grau N que té la propietat descrita, és dir, dona lloc a una funció d'error que té N + 2 extrems, de signes alterns i magnituts iguals. El gràfic roig a la dreta mostra cóm podria ser esta funció d'error per a N = 4. Suponga's que Q(x) (la funció de la qual d'error es mostra en blau a la dreta) és un atre polinomi de grau N que és una millor aproximació a f que P. En particular, Q està més prop de f que P per a cada valor x_i a on se situa un extrem de P-f, llavors

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

Quan es produïx un màxim de P-f en x_i, llavors

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

I quan es produïx un mínim de P-f en x_i , llavors

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

Llavors, com es pot vore en el gràfic, [P(x) - f(x)] - [ Q (x) - f(x)] deu alternar en el signe de N + 2 valors de x_i. Pero [P(x) - f(x)] - [ Q (x) - f(x)] es reduïx a P(x) - Q(x) que és un polinomi de grau N. Esta funció canvia el signe a lo manco N+1 voltes, per lo que, pel Teorema del valor intermig, té N+1 zeros, lo que és impossible per a un polinomi de grau N.^[4]

Aproximació de Chebyshev

Es poden obtindre polinomis molt propencs a l'òptim expandint la funció donada en térmens dels polinomis de Chebyshev i després tallant l'expansió en el grau desijat.^[5]

Este enfocament és similar al anàlisis de Fourier de la funció, utilisant els polinomis de Chebyshev en lloc de les funcions trigonométricas habituals.

Si es calculen els coeficients en l'expansió de Chebyshev per a una funció:

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

i després es talla la série despuix del terme $T_{N}$ , s'obté un polinomi de grau N-ésimo que s'aproxima a f(x).

La raó per la que este polinomi és casi òptim és que, per a funcions en series de potències que convergixen ràpidament, si la série es talla despuix d'un terme, l'error total que sorgix del tall està prop del primer terme despuix del tall. És dir, el primer terme despuix del tall domina tots els térmens posteriors. Lo mateix és cert si l'expansió és en térmens d'atres tipos de polinomis. Si una expansió de Chebyshev es talla despuix de $T_{N}$ , l'error prendrà una forma propenca a un múltiple de $T_{N + 1}$ . Els polinomis de Chebyshev tenen la propietat de que estan nivellats: oscilen entre +1 i −1 en l'interval [−1, 1]. $T_{N + 1}$ té N+2 nivells extrems. Açò significa que l'error entre f(x) i la seua expansió de Chebyshev a $T_{N}$ està prop d'una funció de nivell en N+2 extrems, per lo que està prop del polinomi òptim de N-ésimo grau.

En els gràfics anteriors, deu tindre's en conte que la funció d'error blau és a voltes millor (està més pròxima) que la funció roja, pero a voltes és pijor, lo que significa que no és el polinomi òptim. Tinga's en conte també que la discrepància és menys greu per a la funció exp, que té una série de potències convergent extremadament ràpida, que per a la funció de registre.

L'aproximació de Chebyshev és la base de la quadratura de Clenshaw-Curtis, una tècnica d'integració numèrica.^[6]

Algoritme de Remez

Archiu:Remesdemo.png

Error del polinomi produït pel primer pas de l'algoritme de Remez, aproximant i^x en l'interval [−1, 1]. Les divisions verticals són de 10⁻⁴

l'algoritme Remez (a voltes escrit Remes) s'usa per a produir un polinomi òptim P(x) que s'aproxima a una funció donada f(x) en un interval donat. És un algoritme iterativo que convergix a un polinomi que té una funció d'error en N+2 nivells extrems. Segons la teorema anterior, este polinomi és òptim.^[7]

L'algoritme de Remez utilisa el fet de que es pot construir un polinomi de grau N-ésimo que conduïx a nivells i valors d'error alterns, donats els N+2 punts de referència.

Donats N+2 punts de referència $x_{1}$ , $x_{2}$ , ... $x_{N + 2}$ (a on $x_{1}$ i $x_{N + 2}$ són presumiblement els punts finals de l'interval d'aproximació), estes equacions deuen resoldre's:

\begin{matrix} P (x_{1}) - f (x_{1}) & = + ε \\ P (x_{2}) - f (x_{2}) & = - ε \\ P (x_{3}) - f (x_{3}) & = + ε \\ ⋮ \\ P (x_{N + 2}) - f (x_{N + 2}) & = \pm ε . \end{matrix}

Els costats de la dreta s'alternen en senyal, és dir

\begin{matrix} 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}) & = + ε \\ 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}) & = - ε \\ ⋮ \end{matrix}

Ya que $x_{1}$ , ..., $x_{N + 2}$ són senyes donades, todqs les seues potències són conegudes, i $f (x_{1})$ , ..., $f (x_{N + 2})$ també són coneguts. Això significa que les equacions anteriors són solament N+2 equacions llineals en les N+2 variables $P_{0}$ , $P_{1}$ , ..., $P_{N}$ i $ε$ . Donats els punts de referència $x_{1}$ , ..., $x_{N + 2}$ , es pot resoldre este sistema per a obtindre el polinomi Pi el número $ε$ .

El següent gràfic mostra un eixemple d'esta configuració, produint un polinomi de quart grau que s'aproxima a $e^{x}$ sobre [−1, 1]. Els punts de prova es varen establir en −1, −0.7, −0.1, +0.4, +0.9, i 1. Eixos valors es mostren en vert. El valor resultant de $ε$ és 4.43 × 10⁻⁴

Tinga's en conte que el gràfic d'error pren els valors $\pm ε$ en els sis punts de prova, inclosos els punts finals, pero que eixos punts no són extrems. Si els quatre punts de prova interiors hagueren segut extrems (és dir, la funció P(x) f(x) tinguera màxims o mínims allí), el polinomi seria òptim.

El segon pas de l'algoritme de Remez consistix en moure els punts de prova a les ubicacions aproximades a on la funció d'error tenia els seus màxims o mínims locals reals. Per eixemple, en observar el gràfic es pot dir que el punt en −0.1 deuria haver estat en aproximadament −0.28. La forma de fer açò en l'algoritme és usar un sol pas del método de Newton. Com es coneix la primera i la segona derivada de P(x) − f(x), es pot calcular aproximadament fins a quin punt es deu moure un punt de prova per a que la derivada siga zero.

Calcular les derivades d'un polinomi és senzill. També es deu poder calcular la primera i la segona derivada de f(x). L'algoritme de Remez requerix la capacitat de calcular $f (x)$ , $f^{'} (x)$ i $f^{″} (x)$ en una precisió extremadament alta. Tot l'algoritme deu portar-se a terme en major precisió que la precisió desijada del resultat.

Despuix de moure els punts de prova, es repetix la part de l'equació llineal, obtenint un nou polinomi, i el método de Newton s'usa una atra volta per a moure els punts de referència novament. Esta seqüència continua fins que el resultat convergix a la precisió desijada. L'algoritme convergix molt ràpidament. La convergència és quadràtica per a funcions en bon comportament: si els punts de prova estan dins de $1 0^{- 15}$ del resultat correcte, estaran aproximadament dins de $1 0^{- 30}$ del resultat correcte despuix de la següent iteración.

L'algoritme de Remez generalment s'inicia elegint els extrems del polinomi de Chebyshev $T_{N + 1}$ com els punts inicials, ya que la funció d'error final serà similar a eixe polinomi.^[7]

Revistes principals

Journal of Approximation Theory
Constructive Approximation
East Journal on Approximations

Vore també

Referències

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

Bibliografia

N. I. Achiezer (Akhiezer), Theory of approximation, Translated by Charres J. Hyman Frederick Ungar Publishing Co., New York 1956 x+307 pp.

A. F. Claven, 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, I. W. Cheney, C. L. Lawson, H. J. Maehly, C. K. Mesztenyi, J. R. Rulle, 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.
(2007).«Numerical Recipes: The Art of Scientific Computing».Cambridge University Press.
W. J. Cody Jr., W. Waite, Software Manual for the Elementary Functions. Prentice-Hall, 1980, ISBN 0-13-822064-6.
I. Remes [Remez], "Sur li calcul effectif dones 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 dones noms 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]

Enllaços externs

Referències

Este artícul conté una traducció derivada de «Teoría de la aproximación» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[BOOR-1] (1986) Approximation Theory, Volum 36, American Mathematical Soc., p. X de 131. ISBN 9780821800980.

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

[OLAVI-3] Olavi Nevanlinna (2012). Convergence of Iterations for Linear Equations, Birkhäuser, p. 64. ISBN 9780817628659.

[MAX-4] Nathaniel Max Roc (2007). Standards Driven Math: Calculus, Team Roc Press, pp. 23 de 120. ISBN 9781599800325.

[5] Fauziahanim Che Seman (2004). Chebyshev Approximation of Discrete Polynomials and Splines, Kolej Universiti Teknologi Tun Hussein Onn, pp. 75.

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

[MULLER-7] 7,0 ^7,1 Jean-Michel Muller (2006). Elementary Functions: Algorithms and Implementation, Springer Science & Business Media, pp. 41 de 266. ISBN 9783034885478.

[1]

[2]

[3]

[4]

[5]

[6]

[7]