Составители:
Рубрика:
В дальнейшем там, где это удобно, мы будем пользоваться при-
менённой здесь нотацией – бесконечными представлениями (5.5),
(5.6) (не оговаривая этого специально).
Заметим, что произведением двух многочленов степени k − 1
P (x) =
k−1
X
i=0
a
i
x
i
Q(x) =
k−1
X
j=0
b
j
x
j
(5.9)
является многочлен степени 2k −2
P (x)Q(x) =
2k−2
X
i=0
{
i
X
j=0
a
j
b
i−j
}x
i
, (5.10)
так что коэффициентами произведения является свёртка (5.8) век-
торов, предоставляющих коэффициенты многочленов P (x) и Q(x)
(здесь мы пользуемся нотацией замечания 2).
6. Применение дискретного пребразования Фурье для
вычисления свёртки двух векторов
Пусть два многочлена степени k −1 представлены списками сво-
их коэффициентов. Для того,чтобы найти список коэффициентов
многочлена, представляющего их произведение, перейдём сначала
к спискам их значений в корнях некоторой степени из единицы (с
помощью дискретного преобразования Фурье), затем найдём спи-
сок значений их произведения в этих точках (перемножением со-
ответствующих значений в этих точках), а затем сделаем обратное
дискретное преобразование Фурье, найдя тем самым список коэф-
фициентов произведения многочленов. Точное описание этого при-
ёма содержится в теореме 4.
Определение 6. Покомпонентным произведением c = a·b двух
n-мерных векторов a и b,
a = (a
0
, . . . , a
n−1
), b = (b
0
, . . . , b
n−1
) (6.1)
называется n-мерный иектор c,
c = (c
0
, . . . , c
n−1
), (6.2)
где
c
j
= a
j
b
j
, j = 0, 1, . . . , n − 1. (6.3)
12
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
