Vés al contingut

Construcció de les taules trigonomètriques

De la Viquipèdia, l'enciclopèdia lliure

En matemàtiques, les taules de valors de les funcions trigonomètriques són útils en diverses àrees. Abans de l'existència de les calculadores les taules trigonomètriques eren essencials per a la navegació, la ciència i l'enginyeria. Avui, els ordinadors moderns i les calculadores de butxaca, generen els valors de les funcions trigonomètriques fent servir llibreries especials de codi matemàtic. Sovint, aquestes llibreries fan servir internament taules precalculades, i llavors calculen els valors que es requereix fent servir els mètodes adequats d'interpolació.

La interpolació a partir de taules senzilles de funcions trigonomètriques es fa servir encara en informàtica gràfica, on els càlculs precisos ni calen ni es poden fer prou ràpid.

Una altra aplicació important de les taules trigonomètriques és en els algorismes de generació de la Transformada Ràpida de Fourier (FFT, en anglès: "Fast Fourier Tranforsm"), on els mateixos valors de funcions trigonomètriques (anomenats factors de gir) han de ser avaluats molts cops per a una transformada donada, especialment en al cas habitual on s'han de calcular moltes transformades de la mateixa mida. En aquest cas, l'estratègia de cridar cada cop una rutina d'una llibreria genèrica es fa inacceptablement lent. Una opció és la de cridar les rutines de la llibreria només un cop per a cada angle, i anar construint una taula amb els valors trigonomètrics que es necessitaran, això necessita una quantitat significativa de memòria per a emmagatzemar la taula. Un altre possibilitat, donat que el que es necessita és una successió de valors distribuïts uniformement, és fer servir una fórmula recurrent per a calcular el valors trigonomètrics "al vol". S'han dedicat significatius esforços de recerca per tal de trobar algorismes recurrents estables i precisos, per tal de preservar la precisió de la FFT (la qual és molt sensible als errors trigonomètrics).

Algorismes de càlcul

[modifica]

Els ordinadors moderns fan servir una gran varietat de tècniques.[1] Un mètode habitual, especialment en processadors amb unitats de coma flotant, és combinar una aproximació per un polinomi o una funció racional (com ara l'aproximació de Chebyshev, l'aproximació uniforme òptima, i l'aproximació de Padé, i per a precisions més altes o precisions variables, la sèrie de Taylor i la sèrie de Laurent) amb una reducció del recorregut i una cerca en taula — primer busquen en una petita taula l'angle més proper, i llavors utilitzen el polinomi per a calcular la correcció.[2] En dispositius més senzills als que els manquen unitats de maquinari per fer multiplicacions, hi ha un algorisme anomenat CORDIC (amb les seves tècniques relacionades) que és més eficient perquè només fa servir sumes i l'operació desplaçament. Tots aquests mètodes es poden implementar en circuits especialitzats per motius d'eficiència.

Per a càlculs de molt alta precisió, quan la convergència de les sèries esdevé massa lenta, les funcions trigonomètriques es poden aproximar amb la mitjana aritmètico-geomètrica, que ella mateixa aproxima la funció trigonomètrica per la integral el·líptica (complexa)[3]

Les funcions trigonomètriques d'angles que són múltiples racionals de 2π són nombres algebraics, relacionats amb les arrels de la unitat, i es poden calculat amb algorismes de resolució numèrica d'equacions d'un polinomi en el pla complex. Per exemple, el cosinus i el sinus de 2π⋅5/37 són respectivament, la part real i la part imaginària d'una arrel 37a de la unitat, corresponent a una arrel del polinomi de grau 37: . Els algorismes de resolució numèrica d'equacions com ara el mètode de Newton són molt més senzills que els algorismes per a calcular la mitjana artimètico-geomètrica i convergeixen a un ritme asimptòtic similar; aquests últims algorismes són necessaris per a calcular constants trigonomètriques transcendents.

Identitats de l'angle meitat i de la suma d'angles

[modifica]

Històricament, el mètode més antic amb el que es calculaven les taules trigonomètriques, i probablement el més comú finis a l'adveniment dels ordinadors, va ser l'aplicació repetida de les identitats de l'angle meitat i de la suma d'angles començant a partir d'un valor conegut (com ara sin(π/2)=1, cos(π/2)=0). Aquestes identitats (la primera demostració coneguda de les quals es deu a Ptolemeu) són:

Hi ha diverses variacions possibles d'aquestes identitats (per exemple, les taules trigonomètriques antigues no feien servir el sinus i el cosinus, sinó el sinus i el versinus).

Una aproximació ràpida però inexacte

[modifica]

Un algorisme ràpid, però inexacte, per a calcular una taula de N aproximacions sn del sin (2πn/N) i cn del cos (2πn/N) és:

s0 = 0
c0 = 1
sn+1 = sn + d × cn
cn+1 = cnd × sn

per n = 0,...,N-1, on d = 2π/N.

Aquest mètode se senzillament el mètode d'Euler per a resoldre l'equació diferencial ordinària:

Amb les condicions inicials s(0) = 0 i c(0) = 1, la solució analítica de la qual és s = sin(t) i c = cos(t).

Malauradament, no és un algorisme pràctic per a generar taules trigonomètriques perquè té un error significatiu, proporcional a 1/N.

Per exemple, per N = 256 l'error màxim en els valors del sinus és ~0.061 (s202 = −1.0368 instead of −0.9757). Per N = 1024, l'error màxim dels valors del sinus és ~0.015 (s803 = −0.99321 instead of −0.97832), al voltant de 4 cops més petit. Si s'haguessin de dibuixar els valors del sinus i del cosinus, aquest algorisme dibuixaria una espiral trigonomètrica en comptes d'una circumferència.

Mètode basat en la fórmula d'Euler

[modifica]

Un algorisme senzill per a generar taules trigonomètriques es basa en la fórmula d'Euler i la relació:

Això porta a la següent recurrència per a calcular els valors trigonomètrics sn i cn tal com abans:

c0 = 1
s0 = 0
cn+1 = wr cnwi sn
sn+1 = wi cn + wr sn

per n = 0, ..., N − 1, where wr = cos(2π/N) i wi = sin(2π/N). Aquests dos valors trigonomètrics inicials normalment es calculen emprant llibreres de funcions (però també es podrien trobar per exemple emprant el mètode de Newton al pla complex per tal de resoldre l'arrel de zN − 1).

Aquest mètode donaria una taula exacta en aritmètica exacta, però té errors en aritmètica de coma flotant que té una precisió finita. De fet l'error creix en proporció a O(ε N) (tant en el cas pitjor com en el cas mitjà), on ε é la precisió de coma flotant.

Una millora significativa, és fer servir la següent modificació de l'anterior algorisme (deguda a Singleton) que sovint es fa servir per a generar valors trigonomètrics per a implementar els algorismes FFT:

c0 = 1
s0 = 0
cn+1 = cn − (αcn + β sn)
sn+1 = sn + (β cn − α sn)

on α = 2 sin²(π/N) i β = sin(2π/N). L'error d'aquest mètode és molt més petit, O(ε √N) de mitjana i O(ε N) en el pitjor cas, però això encara és prou gran per degradar l'exactitud de la FFT de mides grans.

Vegeu també

[modifica]

Referències

[modifica]
  1. Kantabutra.
  2. Ara bé, fer això i mantenir la precisió no és trivial, i es poden fer servir mètodes com les taules de precisió de Gal, la reducció de Cody i Waite, i els algoritmes de reducció de Payne i Hanek.
  3. R. P. Brent, "Fast Multiple-Precision Evaluation of Elementary Functions", J. ACM 23, 242 (1976).

Bibliografia

[modifica]
  • Carl B. Boyer, A History of Mathematics, 2nd ed. (Wiley, New York, 1991).
  • Manfred Tasche and Hansmartin Zeuner, "Improved roundoff error analysis for precomputed twiddle factors," J. Computational Analysis and Applications 4 (1), 1-18 (2002).
  • James C. Schatzman, "Accuracy of the discrete Fourier transform and the fast Fourier transform," SIAM J. Sci. Comput. 17 (5), 1150-1166 (1996).