1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 56
Текст из файла (страница 56)
Во многих приложениях бывает удобно преобразовать данную задачу в другую, более легкую. Примером служит вычисление произведения двух полиномов. С вычислительной точки зрения целесообразно сначала применить линейное преобразование к векторам коэффициентов полиномов, затем над образами коэффициентов выполнить операцию, более простую, чем свертка, и, наконец, к результату применить обратное преобразование, чтобы получить искомое произведение. В данном случае подходящим линейным преобразованием будет дискретное преобразование Фурье. В этой главе мы изучим преобразование Фурье н обратное к нему и обсудим его роль в вычислении сверток и произведений различных типов. Будет изложен эффективный алгоритм, называемый быстрым преобразованием Фурье (БПФ).
Он основан на технике вычисления полиномов с помощью деления, и в нем учитывается, что полиномы вычисляются для аргументов, равных корням из единицы. Затем докажем теорему о свертке. Свертку будем интерпретировать как вычисление полиномов в корнях из единицы, умножение этих значений и последующую интерполяцию полиномов. С помощью быстрого преобразования Фурье разработаем эффективный алгоритм для свертки и применим его к формальному (символьному) умножению полиномов и умножению целых чисел. Получающийся алгоритм умножения целых чисел, называемый алгоритмом Шенхаге — Штрассена, является аснмптотически самым быстрым из известных способов умножения двух целых чисел.
7.1. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ И ОБРАТНОЕ К НЕМУ Обычно преобразование Фурье определяется над кольцом комплексных чисел. По причинам, которые станут ясными позже, мы будем определять преобразование Фурье над произвольным комму- тл. дискоктнон пквовнлзонлнии окяьк тативным кольцом (17, +, °, О, 1) '). Элемент в из Я, обладаюший свойствами !) вФ1, 2) вл=1, л — 1 3) ч~~~ вгэ=О для 1(р(п, с=а называется примитивным корнем и-й степени из единицы. Эле- менты ве, в',..., в'-1 называются корнями и-й степени из еди- ницы. Например, ети»л, где 1=у' — 1, является примитивным корнем и-й степени из единицы в кольце комплексных чисел. Пусть а=[а„а„..., а„,)г будет и-мерным вектором (-столбцом) с элементами из (т1.
Мы предполагаем, что элемент и обладает в этом кольце обратным относительно умножения ') и что в — примитив- ный корень и-й степени нз единицы в этом кольце. Пусть А — такая (пхп)-матрица, что А (1, 1)=в» для 0 =1, 1(п. Дискретным преоб- разованием Фурье вектора а называется вектор Аа, обозначаемый л-1 также Р(а); его!-я компонента Ьы 0(1(п, равна Х а„вга. Матрица ~о " А невырожденна, и, значит, существует обратная к ней матрица А ', ее простой вид описывается в лемме 7.1.
Лемма 7А. Пусть И вЂ” ксммутативнсе кольцо, в — прими- тивный коре ь и-й ппепени из единицы и и как элемент кольца 1с имеет обратный. Пусть А — такая (п х п)-матрица, что А(1', 1)=в!у, Оа.(, 1(п, Тогда существует матрица А-' и (1, 1)-й элемент ее равен (11п)в" ». Д оказательство. Пусть 611=1, если 1=1, и б11=0 в противном случае.
Достаточно показать, что если матрица А-1 определена, как выше, то А А-'=1„, т. е. (!', 1)-й элемент матрицы А *А-' удовлетворяет равенству л-1 — 2' ВВВ ку — б ДЛЯ 0(1, )<П. 1 (7.1) н а о Если 1=1, то левая часть равенства (7.1) превращается в л-1 — в'=1. 1 а=о 1) Напомним, что коммутатиаиым нааыаается кольцо, а котором умножение (как и сложение) коммутатиэио. а) Под элементом л кольца подразумевается 1+1+...+1 (л раз). В этом смысле целые числа появляются и любом кольце, даже конечном. заметим также, что примитивный корень в обладает обратным, так как в ыл-'=1 (и, следоаательяо, в-1=ел-'), поэтому можно говорить об отрицательных степенях ьь таз Гл. е БыстРОе пРеОБРА3ОВАние ФуРье Пусть !Ф1 и д=!' — 1.
Тогда левая часть в (7.1) равна л-! — ыоь, — и < а < и, ать О. 1 "А О Если д ьО, то — о!оь = О, 1 " А-О поскольку о! — примитивный корень и-й степени из единицы. Если у<0, то, умножив левую часть на !о-оФ«-!!, изменив порядок слагаемых и подставив — в вместо д, получим «-! — '~аль, 0<у<а. "А О Эта сумма тоже равна О, поскольку о! — примитивный корень и-й степени из единицы. Отсюда сразу вытекает (7А). П Обратным дискретным преобразованием Фурье вектора а называется вектор г-!(а)=А-!а, 1-я компонента которого, 0 =!<и, равна л- ! — ~ аь!о '".
л А О Очевидно, что в результате применения обратного преобразования к преобразованию вектора а получается сам вектор а, т. е. г"-!р (а) а. Преобразование Фурье тесно связано с вычислением полиномов и их интерполяцией. Пусть л-! р (х) = ~~.'„ а,х' !=о — полипом (п — ()-й степени. Его можно однозначно представить двумя способами: списком его коэффициентов а„а„..., а„, и списком его значений в и различных точках х„х„..., х„,.
Процесс нахождения коэффициентов полинома по его значениям в точках х„х„..., х„, называется интерполяцией. Вычисление преобразования Фурье вектора (а„а„..., а„,)г л-! эквивалентно превращению представления полинома Х а,х! Спись сном его коэффициентов в представление его списком значений в точках о!л, о!л,..., о!л-!. Точно так же вычисление обратного преобразования Фурье эквивалентно интерполяции полинома по его значениям в корнях и-й степени иэ единицы. 7.1. ДИСКРЕТНОЕ ПРЕОВРАЗОЕАННЕ ФУРЬЕ Можно было бы определить преобразование, которое вычисляло бы значения полинома иа множестве точек, отличных от корней из единицы.
Например, можно было бы использовать целые числа 1, 2,..., и. Однако мы увидим, что, выбирая степени корня !о, мы делаем вычисление значений и интерполяцию особенно просты- ми, В гл. 8 преобразование Фурье применяется для вычисления зна- чений и интерполяции полиномов в произвольных точках. Одно из основных приложений преобразования Фурье — вычис- ление свертки двух векторов.
Пусть а=[а„а„..., а„,)г, Ь=[Ь„Ь„..., Ь„!(г — два вектора-столбца. Их своркой ЕСи!Ь называется такой вектор и — 1 с= (с„с„..., с,„,)г, что с1=~ч' а1Ь! >. (Полагаем ад — — Ь =О, если 1=-О й(О или й)и.) Таким образом, с,=а,Ь„с, =аЬ,+а,Ь„с,=а,Ь,+а,Ь, +а,Ь„и т. д.
Заметим, что С,„,=О; эта компонента включена только для симме- трии. Чтобы мотивировать рассмотрение свертки, снова обратимся к представлению полинома его коэффициентами. Произведение двух полиномов степени и — 1 и-! и-1 р (х) = ~~.", а;х'„ д (х) = ~ч~ Ь хх !=О !=о является полиномом степени 2и — 2 Ои-О р ! р (х) д (х) = ~ ~ ~ а;Ь, х'. 1О 1О' Заметим, что коэффициенты произведения — это в точности компо- ненты свертки векторов (а„а„..., а„,!" и !Ьо, Ь„..., Ь,)г, составленных из коэффициентов исходных полиномов (коэффициен- том с,„„равным О, мы пренебрегаем).
Если два полинома степени и — 1 представлены своими коэффици- ентами, то, чтобы вычислить коэффициенты их произведения, можно устроить свертку векторов их коэффициентов. С другой стороны, если р(х) и д(х) представлены своими значениями в корнях и-й степени из единицы, то, чтобы вычислить аналогичное представление для их произведения, можно просто перемножить пары значений р(х) и а(х) в соответствующих корнях. Отсюда следует, что свертка двух векторов а и Ь равна обратному преобразованию, примененно.
му к покомпонентному произведению их образов. Формально это записывается так: аСи!Ь=г"-1 (г" (а) г (Ь)). Иными словами, свертку векторов можно вычислить, взяв их преобразования Фурье, вычис- лив покомпонентное произведение и затем сделав обратное преобра- Гл. 7. ВыстРОВ пРИОБРА3ОВАние ФуРье вование.
Единственная трудность состоит в том, что произведение двух полиномов степени и — 1, вообще говоря, является полииомом степени 2п — 2 и для его представления требуются его значения в 2п — 2 различных точках. В теореме 7.1 показывается, как преодолеть эту трудность. Можно рассматривать р (х) и д(х) как полиномы степени 2п — 1, у которых равны нулю коэффициенты при п старших степенях х (т.
е. полиномы степени п — 1 считать полнномами степени 2п — 1). Теорема 7.!. (Теорема о свертке.) Пусть а=[а„а„..., аи „О, ..., 0]г Ь=[Ь„Ь„..., Ьи „О, ..., 01" — векторы-столбцы размерности 2и, а Р(а)=[а'„а,', ..., а;„Дг Р(Ь)=[Ь;, Ь;, ..., Ь;и 212 — их преобразования Фурье. Тогда аОЪ=Р-'(Р(а) Р(Ь)). Д о к а з а т е л ь с т в о, Так как а1=Ь1 — — 0 для п(1(2п, то при 0(1<2п и 1 л 1 а1 —— Х а~ь!1~, Ь! = ~ ЬАБ2!и, Го ь ь Следовательно, и-1 л-1 а;Ь; = Р, ~ а Ь„ь,1м+м (7.2) 1ЬА О ПУсть аОЬ=(с„с„..., с„,,)г и Р(ВОиЬ)=(с „с,)г 2и-1 Так как ср — — Х а Ь, то 1 О 2л-1 2л-1 с1 Х Х ать 1ь2!Р ив!=2 Меняя порядок суммирования в (7.3) и подставляя й вместо р — 1, получаем 2и-12 -1-1 с1 — — Х ~ч', аЬА!л!ол21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
