تبدیل سریع فوریه (Fast Fourier Transform - FFT)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
تبدیل سریع فوریه (Fast Fourier Transform - FFT) :
الگوریتمی برای محاسبه کارآمد تبدیل فوریه گسسته (DFT)
توضیح ساده: تبدیل سریع فوریه (FFT) یک الگوریتم کارآمد برای محاسبه تبدیل فوریه گسسته (DFT) و معکوس آن است. DFT به خودی خود از مرتبه O(n²) است، اما FFT با استفاده از رویکرد تقسیم و غلبه، این محاسبه را به O(n log n) کاهش می دهد. این الگوریتم توسط کولی (Cooley) و توکی (Tukey) در سال ۱۹۶۵ معرفی شد، اگرچه ایده های مشابهی قبلا توسط گاوس نیز مطرح شده بود. FFT یکی از مهم ترین الگوریتم های قرن بیستم است و در همه زمینه های علوم و مهندسی که با سیگنال ها و داده های دوره ای سروکار دارند، انقلابی ایجاد کرده است.
شرح گام به گام: الگوریتم کولی-توکی برای FFT (برای n توانی از ۲):
۱. اگر n=1، برگردان x (حالت پایه).
۲. داده را به دو نیمه زوج و فرد تقسیم کنید: x_even = [x₀, x₂, ..., x_{n-2}]، x_odd = [x₁, x₃, ..., x_{n-1}].
۳. FFT هر دو زیردنباله را به صورت بازگشتی محاسبه کنید: X_even = FFT(x_even)، X_odd = FFT(x_odd).
۴. برای k = ۰ تا n/۲-۱:
- t = X_even[k]
- عامل چرخش (Twiddle factor):
\[ \omega = e^{-2\pi i k / n} \]- X[k] = t + ω * X_odd[k]
- X[k + n/2] = t - ω * X_odd[k]
۵. برگردان X.
این الگوریتم مرتبه O(n log n) است. پیاده سازی های بهینه سازی شده (مانند FFTW) برای nهای غیر توان دو نیز وجود دارند.
مثال عددی: ضرب دو عدد بزرگ با استفاده از FFT. اعداد را به چندجمله ای تبدیل کنید، FFT بگیرید، در حوزه فرکانس ضرب کنید، IFFT بگیرید. این روش برای ضرب اعداد با میلیون ها رقم بسیار سریع تر از روش مستقیم است.
مزایا: بسیار سریع (کاهش از O(n²) به O(n log n))، دقیق، پایدار، کاربردهای بی شمار.
معایب: پیاده سازی صحیح و کارآمد نیاز به دقت دارد. برای nهای اول، کارایی کاهش می یابد.
کاربردها: در پردازش سیگنال، در فشرده سازی داده ها (JPEG, MP3)، در حل معادلات دیفرانسیل، در مخابرات، در تصویربرداری پزشکی.
نکته: FFT یکی از ۱۰ الگوریتم برتر قرن بیستم انتخاب شده است.
