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

     1 N −1 −2πi N 2πi N
                   mk         nk

       ∑ e e = δ mn
     N k =0
                                                                                                                                        (9.5)

    Число базисных векторов, которые полностью описывает вектор f , будет равно
размерности пространства N .
    В итоге получаем формулы дискретного преобразования Фурье (ДПФ):
         1 N −1 2πi
                               nk
     Fn = ∑ f k e N , n = 0,.., N − 1                                                                                                   (9.6)
         N k =0

    Соответствующие формулы обратного ДПФ:
          1 N −1
                                   nk
                 − 2πi
     f n = ∑ Fk e N , n = 0,.., N − 1                                                                                                   (9.7)
          N k =0

    Здесь f k = f (xk ) , Fk = F (xk )
    Эти формулы могут быть представлены в матричном виде:
     F = Aˆ f

     f = Aˆ −1 F                                                                                                                        (9.8)
    Для получения ДПФ требуется O(N 2 ) операций, столько же, сколько для
операции умножения матрицы на вектор.


    Задание 9.1
    Реализовать ДПФ для функции                                                   f (t ) = e −0.1t sin (αt ) + 2 cos(9t ) , t ∈ [0,1] , где α пробегает
значения от 0 до 1000 с шагом 1. Число точек N = 1024 . Результаты представить в виде анимации
амплитудного спектра, т.е. ДПФ выполняется для α , выводится на экран график амплитудного
спектра (амплитуда – модуль комплексного вектора в каждой точке Фурье-образа), затем α
увеличивается на 0.0001 и процесс повторяется. По достижению α = 1000 параметр α
сбрасывается в 0. Измерить время одного цикла анимации, при котором α пробегает значения от
нуля до единицы.




    Идея быстрого преобразования Фурье состоит в том, что при N не являющимся
простым числом, размерность задачи может быть уменьшена. Предположим, что N
четное. Тогда сумму (9.6) можно разбить на две, содержащие четные и нечетные
узлы.
                N / 2−1                  n (2 k )         N / 2 −1                     n ( 2 k +1)
          1                        2πi                1                          2πi
     Fn =
          N
                 ∑
                 k =0
                          f 2k e            N
                                                    +
                                                      N
                                                           ∑
                                                           k =0
                                                                     f 2 k +1e              N
                                                                                                     , n = 0,.., N − 1                  (9.9)
                                                                                                        54