Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 191
Текст из файла (страница 191)
4. Интерполяция. Создается коэффициентное представление полинома С (х) с помощью однократного применения БПФ к 2и парам точка-значение для вычисления обратного ДПФ. Этапы (1) и (3) занимают время О (и), а этапы (2) и (4) занимают время тз (и1к и). Таким образом, показав, как использовать БПФ, мы докажем следующую теорему.
Теорема 30.2. Произведение двух полиномов степени не выше и в случае, когда исходные полиномы и результат находятся в коэффициентной форме, можно вычислить за время О (и 1я и). Упражнения 30.1-1. Выполните умножение полиномов А (х) = 7хз — хз + х — 10 и В (х) = = бхз — бх + 3 с помощью уравнений (30.1) и (30.2). 30.1-2.
Вычисление полинома А (х) степени не выше и в заданной точке хо можно также производить путем деления А(х) на полипом (х — хо), в результате чего получается полипом-частное 9(х) степени не выше и — 1 и остаток г, так что А (х) = д (х) (х — хо) + т . Очевидно, что А (хо) = г. Покажите, как вычислить остаток т и коэффициенты д (х) за время 6 (и), если заданы точка хо и коэффициенты полинома А. 30.1-3. Найдите представление в виде точек-значений полинома А"' (х) = 2 " о а„ г зхз, если известно пРедставление в виде точек-значений полинома А (х) = ~„" азхз; предполагается, что все точки ненулевые. 30.1-4. Докажите, что для однозначного определения полинома степени не выше и необходимо задать и различных пар точка-значение, т.е.
задание меньшего количества различных пар точка-значение не позволит определить единственный полипом с границей степени и. (Указание: используя теорему 30.1, что можно сказать о множестве из и — 1 пары точка-значение, Глава 30. Полииомы и быстрое преобразование Фурье 935 к которому добавляется еще одна произвольно выбранная пара точка— значение?) 30.1-5.
Покажите, как с помощью уравнения (30.5) выполнить интерполяцию за время 9 (пз). (Указание: сначала следует вычислить коэффициентное представление полинома П (х — х ), а затем разделить на (х — хя) для получения числителя каждого члена; см. упражнение 30.1-2. Каждый из п знаменателей можно вычислить за время О (и).) 30.1-6. Обьясните, что неправильно в "очевидном" подходе к делению представленных в виде значений в точках полиномов, когда значения у одного полинома делятся на соответствующие значения у второго полинома. Рассмотрите отдельно случаи, когда деление полиномов осуществляется без остатка и когда имеется остаток. 30.1-7. Рассмотрим два множества А и В, каждое из которых содержит п целых чисел, заключенных в пределах от 0 до 10и. Мы хотим вычислить декарнгову сумму (Сапегйап яип) А и В, определенную следующим образом: С = (х + у: х е А и у е В) Заметим, что целые числа из множества С заключены в пределах от 0 до 20п.
Требуется найти элементы С и указать, сколько раз каждый элемент С выступает в роли суммы элементов А и В. Покажите, что эту задачу можно решить за время О (и !я и). (Указание: представьте А и В в виде полиномов степени не выше 10п.) 30.2 ДПФ и БПФ В разделе 30.1 утверждалось, что используя в качестве точек комплексные корни из единицы, можно выполнять вычисление и интерполяцию полиномов за время О (п1яп). В данном разделе мы дадим определение комплексных корней из единицы и изучим их свойства, определим дискретное преобразование Фурье (ДПФ), а затем покажем, как с помощью БПФ можно вычислять ДПФ и обратное ему преобразование за время О (п!я п).
Комплексные корни из единицы Комплексным корнем и-й степени нз единицы (сошр1ех ийг гоог оГ ишгу) является комплексное число ш, такое что ш" = 1. Существует ровно п комплексных корней п-й степени из единицы: ез™гь/", где Й = О, 1,..., п — 1. Для интерпретации данной формулы воспользуемся следующим определением экспоненты комплексного числа: егк = соа (и) + г з1п (и) Часть Ч!1. Избранные темы 936 Рис. 30.2. Расположение значений ьф,юв,...,ив~ на комплексной плоскости, где юа = ез"'ув— главное значение корня восьмой степени нз единицы На рис. 30.2 показано, что п комплексных корней из единицы равномерно распределены по окружности единичного радиуса с центром в начале координат комплексной плоскости. Значение зяГ/н Ып ке Е (30.6) называется главным значением кормя гь-й етелеии иэ единицы (1йе рппс)ра! и!и пют оГцлйу); все остальные комплексные корни и-й степени из единицы являются его степенями2.
Указанные и комплексных корней и-й степени из единицы о о'п~~п1' ' '1о'и образуют группу относительно операции умножения (см. раздел 31.1). Эта группа имеет ту же структуру, что и алдитивная группа (ли, +) по модулю гт, посколь(г+а) юоб и кУ из огпп = огпо = 1 следУет, что м~ьопь = ь4 . Аналогично, ып т = мп '.
Основные свойства комплексных корней и-й степени из единицы приведены в следующих леммах. Лемма 30.3 (Лемма о сокращении). Для любых целых чисел п > О, 7с > 0 и г! > 0 аь ь (30.7) Многие авторы определяют ьь, иначе: ьь, = е а и". Это альтернативное определение обычно используется в обработке сигналов. Лежащие в основе математические концепции в основном одинаковы для обоих определений. Часть 1(П. Избранные темы 938 Требование, что 1с не делится на и, гарантирует, что знаменатель не равен О, поскольку ша = 1 только тогда, когда гс делится на и. и Дискретное преобразование Фурье Напомним, что мы хотим вычислить полинам и-1 А(х) = ,'з а хз, у=о степень котоРого не выше и, в точках шо,го~1,..., пгп 1 (котоРые пРедставлЯют собой и комплексных корней и-й степени из единицы)з.
Без потери общности можно предположить, что и является степенью 2, поскольку заданную границу степени всегда можно увеличить, добавив, если необходимо, старшие нулевые коэффициентыл. Предположим, что полинам А задан в коэффициентной форме: а = (аО,а1,...,а„1). ОлрЕдЕЛИМ КОНЕЧНЫЕ рЕЗуЛЬтатЫ уьо й = 0,1,...,И вЂ” 1, с помощью формулы и-1 Уь = А (оган) = ~~1 айогпз у=о (30.8) Вектор у = (уо, у1,...,уп 1) представляет собой дискретггое лреобразоваиие Фурье (ДПФ) (Бйзсге1е Ровпег ТгапзГопп, ПРТ) вектора коэффициентов а = = (ао, а1,..., а„1).
Это можно также записать как у = ПРТ„(а). Быстрое преобразование Фурье С помощью метода быстрого преобразования Фурье (БПФ) (Разг Роипсг Тгапз1опп, РРТ), основанного на использовании специальных свойств комплексных корней из единицы, 1)РТп (а) можно вычислять за время 6 (и1к и), в отличие от метода непосредственного преобразования. В методе БПФ применяется стратегия декомпозиции, в которой отдельно используются коэффициенты полинома А (х) с четными и нечетными индексами, Здесь и на самом деле представляет собой величину, юторая в разделе 30.1 обозначалась как 2п, поскольку прежде чем выполнять вычисление, пределы степени заданных полиномов была улвоены. Таким образом, при умножении полиномов речь в действительности идет о комплексных юриях из единицы 2п-й степени.
'При использовании БПФ в обработке сигналов добавлять нулевые юзффициенты в целях получения степеней 2 не рекомендуется, так как зто приводит к возникновению высокочастотных артефактов. Одним из методов получения размерности, равной степени 2, в обработке сигнааоа является отражение (шнтоппя).
Пусть п' — наименьшая целая степень 2, превышающая п; тогда одним из способов отражения является задание а ь; = и, з для) = 0,1,..., и' — п — 1. Глава 30. Полнномы н быстрое преобразование Фурье 939 чтобы определить два новых полинома А!о! (х) и А!з! (х) степени не выше и/2: А! ! (х) = ао+ азх+ а4х + + а„зх ~ А1~! (х) = а! + азх+ азх + + а„зх"7~ 1 . Заметим, что А]о! содержит все коэффициенты А (х) с четными индексами (двоичное представление этих индексов заканчивается цифрой О), а А!!! содержит все коэффициенты с нечетными индексами (двоичное представление которых заканчивается цифрой !).
Для определенных таким способом полиномов справедливо равенство А(,) А]о](,з)+„]т!( г) (30.9) так что задача вычисления А (х) в точках юо, ыт,..., м,", ! сводится к следующим задачам: 1. вычислить два полинома А!о! (х) и А1~! (х) степени не выше и/2 в точках ( 4)',( И' ( ." ')' (30.10) а затем 2. объединить результаты с использованием формулы (30.9). КЕС!Жя!чЕ РРТ(а) 1 и — 1еидй[а] 2 Ыи= 1 3 твен гетпгн а 4 ы < езлчв 5 м+ — 1 б а — (ао,аз,...,а„з) ]о! 7 а — (аы аз,..., а„з) ]1! З р!о! — Кесария!че ррт(а!о!) 9 у]!! — Кес[жз!че РРТ(а(~!) !> и является степенью 2 Согласно лемме о делении пополам„список значений (30.10) сдержит уже не и различных значений, а только и/2 комплексных корней степени (и/2) из единицы, причем каждый корень встречается в списке ровно два раза.
Следовательно, поли- номы А!о! и А!'! с границей степени и/2 рекурсивно вычисляются в и/2 комплексных корнях и/2-й степени из единицы. Эти подзадачи имеют точно такой же вид, как и исходная задача, но их размерность вдвое меньше. Таким образом, мы свели вычисление и-элементного Рг Т„к вычислению двух и/2-элементных РРТ„7з. Такая декомпозиция является основой следующего рекурсивного алгоритма БПФ, который вычисляет ДПФ и-элементного вектора а = (ао, аы..., а„1), где и является степенью 2. Часть Ч![. Избранные темы 940 10 1ог й — 0 го и/2 — 1 11 по уь Ф уя + ануя [о) 12 Уь~-(а/з) + Уь ь'Уь [о] [з] 13 14 ге(пгп у (> Предполагается, что у — вектор-столбец Процедура Кнсикячн ГРТ работает следующим образом. Строки 2-3 описывают базис данной рекурсии: ДПФ одного элемента является самим этим элементом, следовательно, в данном случае уо=аоыз =ао 1=ао о Строки 6-7 определяют векторы коэффициентов полиномов А[о] и А[з].
Строки 4, 5 и 13 гарантируют, что ь~ обновляется надлежащим образом, т.е. всякий раз, когда выполняются строки 11-12, ы = мь,. (Сохранение текущего значения ы от итерации к итерации позволяет экономить время по сравнению с многократным вычислением ыь с нуля с помощью цикла 1ог.) В строках 8-9 выполняются рекурсивные вычисления РГТ„/з, при этом получаются следующие значения (к = 0,1,...,п/2 — 1): у[ ] = А['] (о~а/ ), или, поскольку согласно лемме о сокращении, ыь = м~~, „[о] 4[о) ( зь) УЯ А[з] ( зь) В строках 11-12 комбинируются результаты рекурсивных вычислений РРТ„/з.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
