روش هم گشت (Convolution Methods)، در ریاضیات (Mathematics)
انواع روش های عددی (Numerical Methods) را در آموزش زیر شرح دادیم :
روش هم گشت (Convolution Methods) :
\[ (f * g)(t) = \int_{-\infty}^{\infty} f(\tau) g(t - \tau) d\tau \]توضیح ساده: روش های هم گشت به تکنیک های عددی برای محاسبه انتگرال هم گشت (Convolution Integral) بین دو تابع گفته می شود. هم گشت یک عملیات ریاضی مهم است که در پردازش سیگنال، پردازش تصویر، فیزیک، و آمار کاربرد فراوان دارد. این عملگر نشان می دهد که چگونه شکل یک تابع توسط تابع دیگر تغییر می کند. برای مثال، در پردازش تصویر، اعمال یک فیلتر (مثل Gaussian blur) بر روی یک تصویر، یک هم گشت است. روش های عددی برای هم گشت شامل روش مستقیم (با هزینه O(n²)) و روش مبتنی بر FFT (با هزینه O(n log n)) هستند.
شرح گام به گام: برای دو تابع گسسته f[i] و g[i] با طول n، هم گشت گسسته به صورت زیر تعریف می شود:
\[ (f * g)[k] = \sum_{i=-\infty}^{\infty} f[i] g[k-i] \]در عمل، توابع طول محدود دارند.
روش مستقیم:
۱. برای هر k از ۰ تا ۲n-1، حلقه بزنید.
۲. مجموع حاصل ضرب های f[i] و g[k-i] را برای iهایی که در محدوده تعریف شده هستند محاسبه کنید.
۳. این روش از مرتبه O(n²) است و برای nهای بزرگ کند است.
روش مبتنی بر FFT (تبدیل سریع فوریه):
۱. FFT هر دو تابع را محاسبه کنید: F = FFT(f), G = FFT(g) (با padding مناسب برای جلوگیری از پیچش دورانی).
۲. حاصل ضرب نقطه به نقطه H = F * G را محاسبه کنید.
۳. IFFT (تبدیل فوریه معکوس) را روی H اعمال کنید: h = IFFT(H).
۴. h همان هم گشت خطی f و g است.
این روش از مرتبه O(n log n) است و برای nهای بزرگ بسیار سریع تر است.
مثال عددی: در پردازش تصویر، برای اعمال یک فیلتر میانگین گیر (blur) به اندازه ۵×۵ روی یک تصویر ۱۰۰۰×۱۰۰۰، هم گشت دوبعدی باید محاسبه شود. روش مستقیم بسیار کند است، اما با استفاده از FFT دوبعدی، این عمل در کسری از ثانیه انجام می شود.
مزایا: FFT روش را بسیار سریع می کند. هم گشت یک عملیات اساسی در بسیاری از علوم است.
معایب: روش مستقیم برای داده های بزرگ غیرعملی است. نیاز به درک تبدیل فوریه و پیچیدگی های آن دارد.
کاربردها: در پردازش سیگنال، در پردازش تصویر، در معادلات دیفرانسیل، در آمار (توزیع مجموع متغیرهای تصادفی).
نکته: قضیه هم گشت (Convolution Theorem) می گوید که هم گشت در حوزه مکان معادل ضرب در حوزه فرکانس است.
