Можно было бы определить преобразование, которое вычисляло бы значения полинома на множестве точек, отличных от корней из единицы. Например, можно было бы использовать целые числа 1, 2, . . ., п. Однако мы увидим, что, выбирая степени корня со, мы делаем вычисление значений и интерполяцию особенно простыми. В гл. 8 преобразование Фурье применяется для вычисления значений и интерполяции полиномов в произвольных точках.

Одно из основных приложений преобразования Фурье- вычисление свертки двух векторов. Пусть

- два вектора-столбца. Их сверткой а©Ь называется такой вектор

с= [со, Си . . ., Can-i), ЧТО Ct=ajbt-j. (Полагаем а=Ь=0, если

/г<0 или kn.) Таким образом,

Са = а„Ьа, c = abi-\-aiba, С2 = аоЬ2+аА-ЬаЛ. и т. д.

Заметим, что C2„-i=0; эта компонента включена только для симметрии.

Чтобы мотивировать рассмотрение свертки, снова обратимся к представлению полинома его коэффициентами. Произведение двух полиномов степени п-1

л-1 л-1

p{x)=a,x, q{x)=bjxf

i=0 i=0

является полиномом степени 2n-2

2л-2

p{x)q{x) 2

£ = 0

SaA-y

Заметим, что коэффициенты произведения - это в точности компоненты свертки векторов [Яо, . • •, a„ i] и [Ьо, &i, . . ., b-iV, составленных из коэффициентов исходных полиномов (коэффициентом Cjn-i, равным О, мы пренебрегаем).

Если два полинома степени п-1 представлены своими коэффициентами, то, чтобы вычислить коэффициенты их произведения, можно устроить свертку векторов их коэффициентов. С другой стороны, если р{х) и (д;) представлены своими значениями в корнях п-й степени из единицы, то, чтобы вычислить аналогичное представление для их произведения, можно просто перемножить пары значений р(х) и (7(д;) в соответствующих корнях. Отсюда следует, что свертка двух векторов а и b равна обратному преобразованию, примененному к покомпонентному произведению их образов. Формально это записывается так: a©b=F- (F(a) •F(b)). Иными словами, свертку векторов можно вычислить, взяв их преобразования Фурье, вычислив покомпонентное произведение и затем сделав обратное преобра-

зование. Единственная трудность состоит в том, что произведение двух полиномов степени п-1, вообще говоря, является полиномом степени 2п-2 и для его представления требуются его значения в 2«-2 различных точках. В теореме 7.1 показывается, как преодолеть эту трудность. Можно рассматривать р{х) и q (х) как полиномы степени 2п-1, у которых равны нулю коэффициенты при п старших степенях х (т. е. полиномы степени п-1 считать полиномами степени 2«-1).

Теорема 7.1. (Теорема о свертке.) Пусть

а = [ао, Ci, а„ 1, 0.....0]"

Ь = [&.. Ь,.....Ь„-г, 0.....0Y

- векторы-столбцы размерности 2п, а

F(a) = [a;, а[.....аы-iV

F(b)=[6„, 6;.....b;„ if

- их преобразования Фурье. Тогда a©b=F-* (F(a) •F(b)).

Доказательство. Так как at=bi=0 для n<i<2n, то при 0</<2п

/=о *=о

Следовательно,

л-1п-1

а,Ь, = 22 аЛо)(7.2)

/=0 * = 0

Пусть а©Ь=[Со, Си . . ., сп-А и F(a©b)=[c;, с[, . . ., Can-J.

2n-I

2n-l 2л-1

Так как Ср= 2 «ур-/. то

с;= 2 2аЛ-/«"- (7.3)

р=0 /=0

Меняя порядок суммирования в (7.3) и подставляя k вместо p-j, получаем

2Я-12П-1-/

с<= 2 2 аЛ«**- (7.4)

/=о *=-/

Так как 6=0 для k<(), можно повысить нижний предел суммирования во внутренней сумме до k=0. Аналогично, поскольку а]=0 для можно понизить верхний предел во внешней сумме до п-1. Верхний предел внутреннего суммирования не меньше п

независимо от значения /. Таким образом, можно заменить верхний предел на п-1, так как &=0 при Л>п. После этих изменений (7.4) превратится в (7.2); отсюда следует, что cj=aj Ь]. Итак, F(a©b)= =F (а) -F(b), откуда a©b=F-i (F(a) -F (b)). □

Свертка двух л-мерных векторов является 2п-мерным вектором. Это требует, чтобы в теореме о свертке вектора а и b были "разбавлены" п нулями. Чтобы избежать этого "разбавления", введем понятие обернутой свертки.

Определение. Пусть a=[Qo, Ci, . . ., a„ i] и b= [6о, &i, . . . .. два n-мерных вектора. Положительно обернутой сверт-

кой векторов а и b называется такой вектор с=[Со, Сх,..., c„-i], что

t п-1

1=0 /=«+1

Отрицательно обернутой сверткой векторов а и b называется такой вектор d=[do, du . . ., d„-i], что

i n-l

В разд. 7.5 мы воспользуемся обернутой сверткой в алгоритме Шёнхаге - Штрассена - алгоритме быстрого умножения целых чисел. А пока отметим следующее. Вычислив значения двух полиномов степени п-1 в корнях п-й степени из единицы и перемножив пары значений в соответствующих точках, мы получим п значений, по которым сможем однозначно интерполировать полином степени п-1. Вектор коэффициентов этого единственного полинома как раз и будет положительно обернутой сверткой векторов коэффициентов исходных полиномов.

Теорема 7.2. Пусть а=[ао, Ci, . . ., On-iV и b=[&o, bu . . . ,bn-i\- два n-мерных вектора, а а> - примитивный корень п-й степени из единицы. Пусть 1з*=©. Предположим, что элемент п имеет обратный. Тогда

1) положительно обернутая свертка векторов а ы b равна F-4F(a).F(b)),

2) если d=[do, di, . . ., dn-V- отрицательно обернутая свертка векторов а ы Ь, а=[ао, "аи .., i])"~a„ i], b=[&o, •. . . ., V-b„.iV, d=[do, tdi, . . ., JJ-, mo d= =F-4F(a).F(b)).

Доказательство. Теорема доказывается аналогично теореме 7.1 с учетом равенства1з»=-1. Детали оставляем в качестве упражнения. □