Быстрое преобразование Фурье. Логарифмический алгоритм БПФ для произвольного 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.

Знаете ли Вы, что такое "Большой Взрыв"?
Согласно рупору релятивистской идеологии Википедии "Большой взрыв (англ. Big Bang) - это космологическая модель, описывающая раннее развитие Вселенной, а именно - начало расширения Вселенной, перед которым Вселенная находилась в сингулярном состоянии. Обычно сейчас автоматически сочетают теорию Большого взрыва и модель горячей Вселенной, но эти концепции независимы и исторически существовало также представление о холодной начальной Вселенной вблизи Большого взрыва. Именно сочетание теории Большого взрыва с теорией горячей Вселенной, подкрепляемое существованием реликтового излучения..."
В этой тираде количество нонсенсов (бессмыслиц) больше, чем количество предложений, иначе просто трудно запутать сознание обывателя до такой степени, чтобы он поверил в эту ахинею.
На самом деле взорваться что-либо может только в уже имеющемся пространстве.
Без этого никакого взрыва в принципе быть не может, так как "взрыв" - понятие, применимое только внутри уже имеющегося пространства. А раз так, то есть, если пространство вселенной уже было до БВ, то БВ не может быть началом Вселенной в принципе. Это во-первых.
Во-вторых, Вселенная - это не обычный конечный объект с границами, это сама бесконечность во времени и пространстве. У нее нет начала и конца, а также пространственных границ уже по ее определению: она есть всё (потому и называется Вселенной).
В третьих, фраза "представление о холодной начальной Вселенной вблизи Большого взрыва" тоже есть сплошной нонсенс.
Что могло быть "вблизи Большого взрыва", если самой Вселенной там еще не было? Подробнее читайте в FAQ по эфирной физике.