Главная Промышленная автоматика.

Можно было бы определить преобразование, которое вычисляло бы значения полинома на множестве точек, отличных от корней из единицы. Например, можно было бы использовать целые числа 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. Детали оставляем в качестве упражнения. □





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 [92] 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0043