Преобразование Фурье

Прямое преобразование Фурье (обозначается также $F_+$) сопоставляет кусочно-гладкой абсолютно интегрируемой функции $f(x)$ новую функцию

$\widehat f(y) = \frac{1}{\sqrt{2 \pi}} \int_{- \infty}^{+ \infty}{f(x)e^{-ixy} dy}$

Обратное преобразование Фурье ($F_−$) сопоставляет кусочно-гладкой абсолютно интегрируемой функции $f(x)$ новую функцию

$\breve f(y) = \frac{1}{\sqrt{2 \pi}} \int_{- \infty}^{+ \infty}{f(x)e^{ixy} dy}$

Дискретное преобразование Фурье

Прямое дискретное преобразование Фурье (ДПФ):

$X_k = \sum_{n=0}^{N-1}x_n \cdot e^{-i 2 \pi k n / N}$, где $k = 0, …, N-1$

Обратное дискретное преобразование Фурье (ОДПФ):

$x_n = \frac{1}{N} \sum_{k=0}^{N-1}X_k e^{i 2 \pi k n / N}$, где $k = 0, …, N-1$

Модификация, позволяющая получить результат за время, меньшее чем $O(N^{2})$.

Пример того, как выглядит график преобразования Фурье для функции $\sin(x)+\sin(3x)+\sin(4x)$:

Исходный сигнал представляет собой синусоиду $f(x) = A_0 \sin(w_0 x + \varphi _0 )$.

Подготовить данные (набор координат $x$, $y$). Построить график исходного сигнала.
Осуществить прямое преобразование Фурье (не используя библиотеки). Построить график.
Осуществить обратное преобразование Фурье. Построить график, который должен совпадать с исходным.
Реализовать то же с помощью библиотек и сравнить результаты.