Численные методы. Мирошниченко Г.П - 24 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

24
4. Быстрое дискретное преобразование Фурье
Процедуру построения дискретного ряда Фурье для выбранной функции
можно оптимизировать, существенно сократив время вычислений [1], [6].
Эта возможность следует из следующего наблюдения. Допустим, нам
задана функция
(
)
f
t на
M
узлах сетки
()
:ft =♦ .
Функция задана в интервале
::ab=♦ =♦ .
Определим период
T
дискретного ряда Фурье
:Tba=−.
Зададим число
M
(выберем его четным, для удобства)
:
M
=
♦ ,
определяющее полное число
M
(внутренних) узлов равномерной сетки.
Определим шаг сетки
:
T
t
M
Δ= .
Заполним вектор
τ
размерности
M
положениями (внутренних) узлов
(генерация сетки), края интервала
[
]
,ab отстоят от нулевого и
1
M
−
- ого
узлов на половину шага сетки
2t
(4.1)
:0.. 1
:
2
k
kM
t
atk
τ
=−
Δ
=+ +Δ⋅
.
Заполним вектор F размерности
M
значениями функции на узлах
(4.2)
(
)
:
kk
Ff
τ
= .
Определим интервал частот
ω
Δ
2
:
T
π
ω
⋅
Δ= .
Введем равномерную сетку частот
ω
:
k
k
ω
ω
=Δ ⋅ .
Затем для нахождения каждого коэффициента
{
}
; 0,1... 1
m
Fm M
Ω
−=
дискретного Фурье (полное число коэффициентов Фурье равно
M
)
необходимо проделать
M
суммирований
()
1
0
1
exp
M
mnmn
n
FFi
M
ω
τ
−
=
Ω⋅⋅−⋅⋅
∑
= . (4.3)

Страницы