Быстрое преобразование Фурье. Логарифмический алгоритм БПФ для произвольного N

В "Википедии" нашелся алгоритм сложности O(Nlog_₂N)для произвольного N. Алгоритм основан на значительном увеличении числа элементов последовательности и дополнении ее нулями. Хотя такое расширение, естественно, будет компенсироваться высокой скоростью алгоритма.

Длина последовательности берется равной N', где N' - степень двойки ближайшая сверху к 2N. То есть, 4N > N' = 2^T ≥ 2N. Т.е. число элементов новой последовательности в худшем случае может превышать число элементов исходной последовательности почти в 4 раза. Например, если N = 9, то N' = 32.

kn = 2kn/2 = (−k² + k² + 2kn + n² − n²)/2 = (−k² + (k + n)² − n²)/2

Это используем для дальнейшего преобразования формулы (1):

И далее авторы алгоритма выполняют виртуозный "финт ушами". Пусть:

w_{_{z_{_k} − n}} = W ^{(z_{_{z_{_k} − n}})²/2} = W ^{(2N − 2 − (z_{_k} − n))²/2} = W ^{(2N − 2 − z_{_k} + n)²/2} = W ^{(2N − 2 − (2N − 2 − k) + n)²/2} = W ^{(2N − 2 − 2N + 2 + k + n)²/2} = W ^{(k + n)²/2}

Правая часть формулы (43) является дискретной сверткой. В общем случае формула свертки имеет вид:

где f и g - функции от целых переменных (т.е. дискретные функции). В данном случае роль таких функций играют x'_{_n} и w_{_n}, которые "зависят" от своих индексов как от целых переменных. Свертка обладает замечательным свойством:

где F(f) - это дискретная функция, которая получается из дискретной функции f с помощью быстрого преобразования Фурье.

Дальнейший порядок вычисления таков. Сначала надо вычислить F(x'), то есть взять набор x'_{_n} и вычислить БПФ для n = 0...N' − 1. Затем вычислить F(w), для чего взять набор w_{_n} и вычислить БПФ для n = 0...N' − 1. Потом по формуле (45) простым перемножением получаем F(x' * w) = F(x') F(w). Просто берем i-й элемент, полученный после БПФ набора x'_{_n}, и умножаем на i-й элемент, полученный после БПФ набора w_{_n}. В результате получим БПФ свертки x' * w. Теперь у нас есть БПФ свертки, из него надо получить саму свертку. Для этого применяем обратное преобразование Фурье. Теперь нам надо найти X'_{_k}. Для этого используем формулу (43). k-й элемент набора X_{_k} будет соответствовать z_{_k}-му элементу свертки. Наконец, останется перейти от X'_{_k} к X_{_k}.

В процессе вычислений мы применяли алгоритмы порядка сложности N, N' и N'log_₂N' (когда делали три БПФ). Поскольку N' не может превышать N более, чем в 4 раза, то весь алгоритм имеет сложность O(Nlog_₂N)

Обратное преобразование требует величины W без минуса в показателе и в конце алгоритма - деления всех полученных элементов на N. Три алгоритма БПФ остаются в этом случае теми же: два прямых перобразования и одно обратное.

На следующей страничке приведен листинг программы, выполняющей прямое и обратное преобразования по этому алгоритму. Оптимизация выполнена примерно теми же способами, что и в предыдущем случае с незначительными модификациями. Переменные x' в алгоритме обозначаются как x_, 2N как N2, N' как N_, z_{_k} как N22, π/N (или −π/N при обратном преобразовании) как piN.

Знаете ли Вы, что cогласно релятивистской мифологии "гравитационное линзирование - это физическое явление, связанное с отклонением лучей света в поле тяжести. Гравитационные линзы обясняют образование кратных изображений одного и того же астрономического объекта (квазаров, галактик), когда на луч зрения от источника к наблюдателю попадает другая галактика или скопление галактик (собственно линза). В некоторых изображениях происходит усиление яркости оригинального источника." (Релятивисты приводят примеры искажения изображений галактик в качестве подтверждения ОТО - воздействия гравитации на свет)
При этом они забывают, что поле действия эффекта ОТО - это малые углы вблизи поверхности звезд, где на самом деле этот эффект не наблюдается (затменные двойные). Разница в шкалах явлений реального искажения изображений галактик и мифического отклонения вблизи звезд - 10¹¹ раз. Приведу аналогию. Можно говорить о воздействии поверхностного натяжения на форму капель, но нельзя серьезно говорить о силе поверхностного натяжения, как о причине океанских приливов.
Эфирная физика находит ответ на наблюдаемое явление искажения изображений галактик. Это результат нагрева эфира вблизи галактик, изменения его плотности и, следовательно, изменения скорости света на галактических расстояниях вследствие преломления света в эфире различной плотности. Подтверждением термической природы искажения изображений галактик является прямая связь этого искажения с радиоизлучением пространства, то есть эфира в этом месте, смещение спектра CMB (космическое микроволновое излучение) в данном направлении в высокочастотную область. Подробнее читайте в FAQ по эфирной физике.