Una consideración importante en la implementación de cualquier algoritmo numérico práctico es la precisión numérica: ¿qué tan rápido se acumulan los errores de redondeo en punto flotante en el transcurso del cálculo? Afortunadamente, los algoritmos FFT en su mayor parte tienen características de precisión notablemente buenas. En particular, para una DFT de longitud\(n\) calculada por un algoritmo Cooley-Tukey con aritmética de coma flotante de precisión finita, el crecimiento de error en el peor de los casos esO(registron)O(registron)“role="presentation” style="position:relative;” tabindex="0"> \(O(\log n)\)y el crecimiento medio del error para entradas aleatorias es solamente\(O(\sqrt{\log n})\). Esto es tan bueno que, en aplicaciones prácticas, una FFT correctamente implementada rara vez será un contribuyente significativo al error numérico.
Los asombrosamente pequeños errores de redondeo de los algoritmos FFT a veces se explican incorrectamente como simplemente una consecuencia del reducido número de operaciones: ya que hay menos operaciones en comparación con una ingenuaO(n2)O(n2)“role="presentation” style="position:relative;” tabindex="0">\(O(n^2)\) algoritmo, va el argumento, hay menos acumulación de error de redondeo. La verdadera razón, sin embargo, es más sutil que eso, y tiene que ver con el orden de las operaciones más que con su número. Por ejemplo, considere el cálculo de solo la salida\(Y[0]\) en el algoritmo radix-2 de Pre ignorando todas las demás salidas de la FFT. \(Y[0]\)es la suma de todas las entradas, requiriendo\(n-1\) adiciones. El FFT no cambia este requisito, simplemente cambia el orden de las adiciones para reutilizar algunas de ellas para otras salidas. En particular, esta FFT DIT de radix-2 calcula de la\(Y[0]\) siguiente manera: primero suma las entradas indexadas pares, luego suma las entradas indexadas impares, luego suma las dos sumas; las entradas indexadas pares e impares se suman recursivamente por el mismo procedimiento. Este proceso a veces se llama suma en cascada, y aunque todavía requiere adiciones\(n-1\) totales para calcular\(Y[0]\) por sí mismo, su error de redondeo crece mucho más lentamente que simplemente agregar\(X[0],X[1],X[2]\) y así sucesivamente en secuencia. Específicamente, el error de redondeo al sumar números de\(n\) coma flotante en secuencia crece a medida queO(n2)O(n2)“role="presentation” style="position:relative;” tabindex="0">\(O(n)\) en el peor de los casos, o como\(O(\sqrt{n})\)O(n)O(n)“role="presentation” style="position:relative;” tabindex="0"> en promedio para entradas aleatorias (donde los errores crecen según una caminata aleatoria), pero simplemente reordenar estas adiciones n-1 en una suma en cascada produceO(registron)O(registron)“role="presentation” style="position:relative;” tabindex="0"> en el\(O(\log n)\) peor de los casos y\(O(\sqrt{\log n})\)O(registron)O(registron)“role="presentación” style="position:relative;” tabindex="0">O(registron)O(registron)“role="presentation” style="position:relative;” tabindex="0"> crecimiento promedio del error de caso.
Sin embargo, estas tasas alentadoras de crecimiento de errores solo se aplican si los factores trigonométricos de “twiddle” en el algoritmo FFT se calculan con mucha precisión. Muchas implementaciones FFT, incluyendo FFTW y bibliotecas comunes optimizadas por el fabricante, por lo tanto, utilizan tablas precalculadas de factores de twiddle calculados por medio de funciones de biblioteca estándar (que calculan constantes trigonométricas para obtener aproximadamente la precisión de la máquina). El otro método común para calcular los factores de twiddle es usar una fórmula de recurrencia trigonométrica, esto ahorra memoria (y caché), pero casi todas las recurrencias tienen errores que crecen a medida que\(O(\sqrt{n})\),O(n2)O(n2)“role="presentation” style="position:relative;” tabindex="0">\(O(n)\) o inclusoO(n2)O(n2)“role="presentation” style="position:relative;” tabindex="0">\(O(n^2)\) que conducen a errores correspondientes en la FFT. Por ejemplo, una recurrencia simple esei(k+1)θ=eikθeiθei(k+1)θ=eikθeiθ“role="presentation” style="position:relative;” tabindex="0">\(e^{i(k+1)\theta }=e^{ik\theta }e^{i\theta }\), multiplicando repetidamente poreiθeiθ“role="presentation” style="position:relative;” tabindex="0">\(e^{i\theta }\) para obtener una secuencia de ángulos igualmente espaciados, pero los errores al usar este proceso crecen comoO(n2)O(n2)“role="presentación” style="position:relative;” tabindex="0">\(O(n)\). Una recurrencia mejorada común esei(k+1)θ=eikθ+eikθ(eiθ-1)ei(k+1)θ=eikθ+eikθ(eiθ-1)“role="presentation” style="position:relative;” tabindex="0">\(e^{i(k+1)\theta }=e^{ik\theta }+e^{ik\theta }(e^{i\theta }-1)\) donde\(e^{i\theta }-1=\cos (\theta )-1+i\sin (\theta )\) se calcula la pequeña cantidad 12 usandocos(θ)-1=-2pecado2(θ/2)cos(θ)-1=-2pecado2(θ/2)“role="presentation” style="position:relative;” tabindex="0"> \(\cos (\theta )-1=-2\sin ^2(\theta/2 )\), desafortunadamente, el error al usar este método sigue creciendo\(O(\sqrt{n})\) mucho peor que logarítmico.
O(n)O(n)“role="presentation” style="position:relative;” tabindex="0"> De hecho, existen recurrencias trigonométricas con el mismo crecimiento logarítmico de error que la FFT, pero estas parecen más difíciles de implementar de manera eficiente; requieren que se almacene una tabla de\(\Theta (\log n)\) valores y actualizado a medida que avanza la recurrencia. En cambio, para obtener al menos algunos de los beneficios de una recurrencia trigonométrica (presión de memoria reducida a expensas de más aritmética), FFTW incluye varias formas de calcular una tabla de twiddle mucho más pequeña, a partir de la cual las entradas deseadas se pueden calcular con precisión sobre la marcha usando un número acotado ( por lo general<3<3“role="presentation” style="position:relative;” tabindex="0"> <3) de multiplicaciones complejas. Por ejemplo, en lugar de una tabla de twiddle con\(n\) entradas\(\omega _{n}^{k}\), FFTW puede usar dos tablas con\(\Theta (\sqrt{n})\) entradas cada una, de modo queωnkωnk“role="presentation” style="position:relative;” tabindex="0">\(\omega _{n}^{k}\) se calcula multiplicando una entrada en una tabla (indexada con los bits de orden bajo dekk“role="presentation” style="position:relative;” tabindex="0">\(k\)) por una entrada en la otra tabla (indexada con los bits de orden superior dekk“role="presentación” style="position:relative;” tabindex="0">kk“role="presentation” style="position:relative;” tabindex="0"> \(k\)).
Hay algunos algoritmos que no son Cooley-Tukey que se sabe que tienen peores características de error, como el algoritmo de “factor real” pero estos rara vez se usan en la práctica (y no se usan en absoluto en FFTW). Por otro lado, algunos algoritmos de uso común para las transformaciones discretas de coseno tipo I y tipo IV tienen errores que observamos para crecer comonn“role="presentation” style="position:relative;” tabindex="0"> \(\sqrt{n}\)incluso para constantes trigonométricas precisas (aunque no conocemos ningún análisis teórico de errores de estos algoritmos), y así nos vimos obligados a usar algoritmos alternativos.
Nota al pie
12 En una FFT, los factores de twiddle son potencias deωnωn“role="presentation” style="position:relative;” tabindex="0">\(\omega _n\), entoncesθθ“role="presentation” style="position:relative;” tabindex="0">\(\theta\) es un ángulo pequeño proporcional a1/n1/n“role="presentation” style="position:relative;” tabindex="0"> \(1/n\)y\(e^{i\theta }\) está cerca de 1.
