Приближенное вычисление интегралов с помощью быстрого преобразования Фурье

ПРИБЛИЖЕННОЕ ВЫЧИСЛЕНИЕ ИНТЕГРАЛОВ С ПОМОЩЬЮ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ.

ЦЕЛЬ РАБОТЫ.

1. Быстрое преобразование Фурье. Любая непрерывная дифференцируемая периодическая функция ( с периодом Т ) может быть разложена в ряд Фурье:

[pic 1]        (2.1)

Коэффициенты ak определяются по формуле:

[pic 2]        (2.2)

Формулы (2.1) и (2.2) называются прямым и обратным преобразованием Фурье.

Если периодическая (с периодом Т=1) функция задана на дискретном множестве точек: xl=l/N, l=0,1,...,N-1; отрезка [0,1], то при ее интерполяции используется дискретное преобразование Фурье:

[pic 3]        (2.3)

Коэффициенты ak определяются по формуле

[pic 4]        (2.4)

Формулы (2.3;2.4) называют прямым и обратным дискретным преобразованием Фурье.

С учетом того, что xl=l/N и вводя обозначения [pic 5]i2π/N формулы (2.3;2.4) запишем в более компактном виде:

[pic 6]        (2.5)

где [pic 7]

При проведение вычислений по формулам (2.5) на каждое преобразование требуется примерно N2 операций типа умножения двух комплексных чисел с последующим сложением, при этом считается, что величина θkl уже вычислена заранее.

Пусть N=2n. Заменим каждый из индексов k и l (2.5) соответствующим двойным индексом и перейдем от суммирования по одному индексу k или l к суммированию по двум соответствующим индексам:

[pic 8],        (2.6)

при этом [pic 9], т.к. [pic 10]

Рассмотрим множитель [pic 11]:

[pic 12]        (2.7)

так как [pic 13]

Обозначим a(k)=ak. Тогда прямое преобразование Фурье запишется в виде:

[pic 14]        (2.8)

где

[pic 15]        (2.9)

Число коэффициентов [pic 16]равно 2n. Для их вычисления требуется две операции типа, указанного выше. Поэтому для вычисления всех коэффициентов [pic 17] требуется 2*2n операций.

Заменим индексы [pic 18] и l двойными индексами

[pic 19]

Найдем соотношение, которое определяет индекс [pic 20] через индекс [pic 21]. В соответствии с (2) имеем:

[pic 22]

Так как [pic 23], то из последнего равенства следует: [pic 24]. Отсюда получаем:

[pic 25]

или после сокращения:

[pic 26]        (2.11)

Таким образом соотношения (2.8, 2.9) можем записать следующим образом:

[pic 27]        (2.12)

где

[pic 28]        (2.13)

Число коэффициентов [pic 29] равно 2n, поэтому для вычисления всех этих коэффициентов требуется 2*2n операций.

Далее индексы [pic 30] и l заменим на индексы [pic 31] и запишем (2.12, 2.13) с новыми индексами. Повторяя этот процесс после i шага будем иметь:

[pic 32]        (2.14)

где

[pic 33]        (2.15)

Число коэффициентов [pic 34] равно 2n и для их вычисления требуется 2*2n операций.

После n шага имеем:

[pic 35]        (2.16)

Число коэффициентов [pic 36] равно 2n и для их вычисления необходимо 2*2n операций. Для вычисления всех значений fl=a(n)(l) по формулам (2.16) требуется 2*2n операций. Таким образом, чтобы выполнить все вычисления по формулам (2.6, 2.13) необходимо всего 2*n*2n операций вместо 22n операций для непосредственного вычисления тех же значений по первой формуле (2.5). Алгоритм (2.6-2.16) называется быстрым преобразованием Фурье. Следовательно, мы сократили количество операций в 2n-1/n раз.