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

БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ

Преобразование Фурье естественно возникает во многих задачах теоретического и прикладного характера, и потому имеет смысл изучить эффективный алгоритм его вычисления. Вездесущность преобразования Фурье будет в дальнейшем продемонстрирована его применимостью к построению эффективных алгоритмов. Во многих приложениях бывает удобно преобразовать данную задачу в другую, более легкую. Примером служит вычисление произведения двух полиномов. С вычислительной точки зрения целесообразно сначала применить линейное преобразование к векторам коэффициентов полиномов, затем над образами коэффициентов выполнить операцию, более простую, чем свертка, и, наконец, к результату применить обратное преобразование, чтобы получить искомое произведение. В данном случае подходящим линейным преобразованием будет дискретное преобразование Фурье.

В этой главе мы изучим преобразование Фурье и обратное к нему и обсудим его роль в вычислении сверток и произведений различных типов. Будет изложен эффективный алгоритм, называемый быстрым преобразованием Фурье (БПФ). Он основан на технике вычисления полиномов с помощью деления, и в нем учитывается, что ПОЛИНОМЫ вычисляются для аргументов, равных корням из единицы.

Затем докажем теорему о свертке. Свертку будем интерпретировать как вычисление полиномов в корнях из единицы, умножение этих значений и последующую интерполяцию полиномов. С помощью быстрого преобразования Фурье разработаем эффективный алгоритм для свертки и применим его к формальному (символьному) умножению полиномов и умножению целых чисел. Получающийся алгоритм умножения целых чисел, называемый алгоритмом Шёнхаге - Штрассена, является асимптотически самым быстрым из известных способов умножения двух целых чисел.

7.1. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ОБРАТНОЕ К НЕМУ

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



тативным кольцом {R, +, ; О, 1) Элемент со из R, обладающий свойствами

1) «#1,

2) (й»=1,

3) ФР=0 для l<p<n,

называется примитивным корнем п-й степени из единицы. Элементы ш», ffli, . . ., ш""! называются корнями п-й степени из единицы.

Например, е"", где i=y -I, является примитивным корнем п-й степени из единицы в кольце комплексных чисел.

Пусть а=[ао, fli, • • ., a„ i]будет n-мерным вектором (-столбцом) с элементами из R. Мы предполагаем, что элемент п обладает в этом кольце обратным относительно умножения ") и что ш - примитивный корень п-й степени из единицы в этом кольце. Пусть А - такая (пХп)-матрица, что А И, }]=а) дляО<1, /<п. Дискретным преобразованием Фурье вектора а называется вектор Л а, обозначаемый

также F (а); его i-я компонента bi, 0<i<n, равна аш*. Матрица

А невырожденна, и, значит, существует обратная к ней матрица А~; ее простой вид описывается в лемме 7.1.

Легта 7.1. Пусть R - коммутативное кольцо, а - примитивный корень п-й степени из единицы и п как элемент кольца R имеет обратный. Пусть А-такая (пХп)-матрица, что ли,/]=сйЛ Oi, }<.п. Тогда существует матрица А- и (/,/)-м элемент ее равен (1/п)(й-Л

Доказательство. Пусть 8и=1, если i=], и 8=0 в противном случае. Достаточно показать, что если матрица Л-* определена, как выше, то Л •Л-=/„, т. е. (t, /)-й элемент матрицы Л-Л -1 удовлетворяет равенству

] (й*(о-*/ = б,.у для 0<1, /<п. (7.1)

Если /=/, то левая часть равенства (7.1) превращается в

*) Напомним, что коммутативным называется кольцо, в котором умножение (как и сложение) коммутативно.

) Под элементом п кольца подразумевается 1--1-Ь".+ 1 (п раз). В этом смысле целые числа появляются в любом кольце, даже конечном. Заметим также, что примитивный корень ш обладает обратным, так как u).u)-i= 1 (и, следовательно, (0-1= (О"-»), поэтому можно говорить об отрицательных степенях ш.



Пусть 1Ф1 И q=i-j. Тогда левая часть в (7.1) равна

* = о

Если >0, то

поскольку (о - примитивный корень п-й степени из единицы. Если 9<0, то, умножив левую часть на cu-«"»-i>, изменив порядок слагаемых и подставив -q вместо q, получим

4 21 О < (? < п.

А = о

Эта сумма тоже равна О, поскольку © - примитивный корень п-й степени из единицы. Отсюда сразу вытекает (7.1). □

Обратным дискретным преобразованием Фурье вектора а называется вектор f-(a)=i4-*a, <-я компонента которого, 0</<п, равна

п- 1

Очевидно, что в результате применения обратного преобразования к преобразованию вектора а получается сам вектор а, т. е. F-F(a)= »=а.

Преобразование Фурье тесно связано с вычислением полиномов и их интерполяцией. Пусть

П- 1

р (X) = 2 aix

1 = 0

- полином (п-1)-й степени. Его можно однозначно представить двумя способами: списком его коэффициентов Со, Ci, . . ., a„-i и СПИСКОМ его значений в п различных точках дго, Xi, . . ., a:„ i. Процесс нахождения коэффициентов полинома по его значениям в точках Хо, Xi, . . ., Xn-t называется интерполяцией.

Вычисление преобразования Фурье вектора [со, а,, . . ., a„-iF

эквивалентно превращению представления полинома UtX списком его коэффициентов в представление его списком значений в точках ш", 0)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.0042