Введение в численные методы. Дулов Е.Н. - 53 стр.

      9. Быстрое преобразование Фурье

      Рассмотрим сначала дискретное преобразование Фурье (ДПФ), происходящее
из непрерывного преобразования Фурье функции f (t ) на конечном отрезке t ∈ [0,1] :
                     1
       F (ω n ) = ∫ f (t )e iωnt dt , ω = 2πn , n = 0,.., ∞                                   (9.1)
                     0


      Этот           интеграл           представляет          собой   ортогональное   преобразование   в
бесконечномерном (гильбертовом) пространстве. От разложения вектора в
ортогональном базисе привычного 2- или 3-мерного евклидового пространства
преобразование Фурье отличается лишь числом измерений и комплексным
характером функций. Интеграл соответствует скалярному произведению в
гильбертовом пространстве и описывает проецирование вектора f на n -ю орту
en = e iωnt , т.е.

       F (ω n ) = ( f , en )                                                                  (9.2)
      Сами же орты удовлетворяют условию
                         1
       (em , en ) = ∫ e −iω t e iω t dt = δ mn
                             m   n
                                                                                              (9.3)
                         0


      δ mn - символ Кронекера.

      Здесь учитывается комплексный характер базисных функций, из-за которого
длина вектора определяется как скалярное произведение вектора на свое
комплексное сопряжение.
      Заметим, что преобразование Фурье может быть формально получено через
метод наименьших квадратов с линейно входящими параметрами (предыдущая
глава), причем матрица Грама будет диагональной.
      При численном нахождении (9.1) бесконечное множество точек t ∈ [0,1]
заменяется дискретным {t k } , k = 0,.., N − 1 , t k = k / N . Тогда вместо пространства
Гильберта получаем обычное N -мерное евклидовое пространство, а формулы (9.1),
(9.2) приобретают вид:
                 1 N −1              1 N −1
                                                         nk
                                                 2πi
       F (ω n ) = ∑ f (t k )e iωntk = ∑ f (t k )e N                                           (9.4)
                 N k =0              N k =0

      При этом свойство ортогональности базиса сохраняется (без доказательства):
                                                                 53