Составители:
Рубрика:
Примеры. Пусть n = 3 и
a = a
0
, a
1
, a
2
, b = b
0
, b
1
, b
2
.
Нетрудно проверить, что положительно обёрнутая свёртка =
0
,
1
,
2
имеет компоненты
c
0
= a
0
b
0
+ a
1
b
2
+ a
2
b
1
,
c
1
= a
0
b
1
+ a
1
b
0
+ a
2
b
2
,
c
2
= a
0
b
2
+ a
1
b
1
+ a
2
b
0
,
а отрицательно обёрнутая свёртка d = d
0
, d
1
, d
2
имеет компоненты
d
0
= a
0
b
0
− a
1
b
2
− a
2
b
1
,
d
1
= a
0
b
1
+ a
1
b
0
− a
2
b
2
,
d
2
= a
0
b
2
+ a
1
b
1
+ a
2
b
0
.
Теорема 6.
4
Для векторов a и b справедлива формула
a
(+)
∗
b = F
−1
(ba
b
b). (6.22)
Теорема 7.
5
Пусть ψ
2
= ω и пусть
˜
Ψ – операция, переводящая
вектор a = (a
0
, a
1
, . . . , a
n−1
)
T
в вектор
˜
Ψa = (a
0
, ψa
1
, . . . , ψ
n−1
a
n−1
)
T
. (6.23)
Тогда
˜
Ψ(a
(−)
∗
b) = F
−1
(
c
˜
ψa ·
c
˜
ψb). (6.24)
7. Об алгоритме быстрого преобразования Фурье (ос-
новная идея)
Дискретное преобразование Фурье (и обратное к нему) опреде-
ляется как умножение специальной полностью заполненной квад-
ратной матрицы порядка n на n-мерный вектор (см. п. 3). Ясно,
что при этом достаточно n
2
умножений и n(n −1) сложений. Счи-
тая, что арифметические операции на ЭВМ выполняются за один
4
Доказательство теоремы 6 провести самостоятельно
5
Доказательство теоремы 7 провести самостоятельно
15
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
