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

UptoLike

ВУЗ: 

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

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

Рубрика: 

25
Полное число операций для вычисления всех компонент
m
FΩ оказывается
порядка
2
M
. Это число операций можно сократить. Предположим, что
число
M
разбивается на два сомножителя
12
M
pp⋅= .
Перепишем формулу
(4.3) для коэффициентов дискретного Фурье
m
FΩ
()
1
0
1
exp exp 2
M
mn
n
mn
FimFi
MM
θπ
−
=
⋅
⎛⎞
Ω⋅−⋅⋅⋅⋅−⋅⋅⋅
⎜⎟
⎝⎠
∑
= , (4.4)
и введем новое правило суммирования. Здесь фаза
(
)
2at
θ
ω
Δ⋅ +Δ= .
Зададим целые числа
{
}
;0,1..1mm M
−
= и
}
;0,1..1nn M
−
= в виде
112
11 1 2 2 2
221
,0 , 1,0 , 1
mm pm
nm p nm p
nn pn
+⋅
⎧
≤≤−≤ ≤−
⎨
+⋅
⎩
=
=
. (4.5)
Здесь введены новые индексы суммирования
1
n и
2
n (вместо n ) и новые
индексы
1
m и
2
m (вместо m ), нумерующие коэффициенты Фурье. Тогда
сумма по n разобьется на две суммы
()
2
2
1
221
1
1
112
2
0
212
1
1
1
0
11
1
exp exp 2
1
exp 2
p
m
n
p
npn
n
mpm
Fim i n
ppp
m
Fin
pp
θπ
π
−
=
−
+⋅
=
⎧
⎛⎞
+⋅
Ω−⋅⋅⋅⋅−⋅⋅⋅ ⋅×
⎨
⎜⎟
⋅
⎝⎠
⎩
⎫
⎛⎞
×⋅ ⋅ −⋅⋅⋅⋅
⎬
⎜⎟
⎝⎠
⎭
∑
∑
=
. (4.6)
В формуле
(4.6) в первой сумме по значку
1
n
()
1
221
1
1
1
12 1
0
11
1
;exp2
p
npn
n
m
Fmn F i n
pp
π
−
+⋅
=
⎫
⎛⎞
⋅⋅−⋅⋅⋅⋅
⎬
⎜⎟
⎝⎠
⎭
∑
%
=
заполняется
M
- мерный (промежуточный) вектор
(
)
12
;Fmn
%
. Для его
заполнения требуется порядка
(
)
2
12
p
p
⋅
операций. Во второй сумме по
значку
2
n заполняется искомый вектор коэффициентов Фурье
m
FΩ . Для
этого требуется порядка
(
)
2
21
p
p
⋅
операций. Если числа
1
p
и
2
p
одного
порядка, то полное число операций для получения вектора
m
FΩ имеет
порядок
32
M
(вместо
2
M
). Налицо ускорение процесса. Для проведения
быстрого Фурье – преобразования выбирают число узлов
M
в виде
:2
r
M
=
,
где
r - целое число. Тогда требуемое число операций для получения
вектора
m
FΩ имеет порядок
(
)
2
log
M
M
⋅
. Имеем существенное ускорение
процесса. Для реализации этой возможности требуется новая организация
суммирования в формуле
(4.4). Для этой цели вместо индексов m и n ,

Страницы