Алгоритмы - построение и анализ (1021735), страница 190
Текст из файла (страница 190)
Последних результатов в этой области добились Спилмен (Бр!е1шап) и Тенг (Тепй) [284], которые ввели понятие "сглаженного анализа алгоритмов" и применили его к симплекс-алгоритму. Известно, что симплекс-алгоритм работает более эффективно в определенных специальных случаях. В частности, заслуживает внимания сетевой симплекс-алгоритм — разновидность симплекс-алгоритма, приспособленная для решения задач сетевых потоков. Для некоторых сетевых задач, включая задачи поиска кратчайшего пути, максимального потока и потока с минимальными затратами, варианты сетевого симплекс-алгоритма достигают результата за полиномиальное время.
Обратитесь, например, к статье Орлина [234] и ее ссылкам. ГЛАВА 30 Полиномы и быстрое преобразование Фурье Для выполнения непосредственного сложения двух полиномов степени и требуется время 6 (и), однако для их непосредственного умножения требуется время О (из). В данной главе мы покажем, как с помощью быстрого преобразования Фурье (БПФ) (газг гоиг(ег Тгапз(опп, РРТ) можно сократить время умножения полиномов до 9 (и 1к и). Наиболее часто преобразования Фурье (а следовательно, и БПФ) используются в обработке сигналов.
Сигнал задается во временной области (пше боша(п) как функция, отображающая время в амплитуду. Анализ Фурье позволяет выразить сигнал как взвешенную сумму сдвинутых по фазе синусоид различных частот. Веса и фазы связаны с частотными характеристиками сигнала в частотной ойласн1и ((гес(оепсу боша1п). Обработка сигналов — обширная область исследований, которой посвящено несколько отличных книг; в примечаниях к данной главе приводятся ссылки на некоторые из них.
Полииомы Полиномом (ро1упоппа1) относительно переменной х над алгебраическим полем Е называется представление функции А (х) в виде суммы А(х) = ~ а-ху . Глава 30. Полиномы и быстрое преобразование Фурье 927 значения а1, аз,..., а„1 называются коэффициентами данного полинома. коэффициенты принадлежат некоторому полю Е, как правило, это множество комплексных чисел С.
Говорят, что полипом А (х) имеет степень й, если его старшим ненулевым коэффициентом является аь. Любое целое число, строго большее степени полинома, называется границей степени (бейтса-Ьоцп41) данного полинома. Следовательно, степенью полинома с границей степени и может быть любое целое число от 0 до и — 1 включительно. Для полиномов можно определить множество разнообразных операций. Например, сложение полиномов (ро1упощ1а! а4Ы111оп): если А (х) и В (х) — поли- номы степени не выше п, то их суммой (зшп) является полинам С (х) степени не выше и, такой что С (х) = А (х) + В(х) для всех х из соответствующего поля. Таким образом, если п-1 В(х) = ~> Ь хз, и-1 С(х) = ~> с хз где с = ау+6 для всех з = 0,1,...,и — 1.
Например, если А(х) = бхз+ 7хз— — 10х + 9 и В (х) = — 2х + 4х — 5, то С (х) = 4х + 7хз — бх + 4. Умножение полиномов (ро1упопца1 шц111р!1сабоп): если А (х) и В (х) — полиномы степени не выше и, их произведением (ргобцс1) С (х) является полипом степени не выше 2п — 1, таюй что С (х) = А (х) В (х) для всех х из соответствующего поля. Вероятно, вам уже доводилось перемножать полиномы, умножая каждый член полинома А (х) на каждый член полинома В (х) и выполняя приведение членов с одинаювыми степенями.
Например, умножение полиномов А (х) = бхз+ 7хз -10х+ 9 и В (х) = -2хз+4х-5 можно выполнить следующим образом: бхз + 7хз — 10х + 9 — 2х + 4х — 5 — 30хз — 35хз + 50х — 45 24х4 + 28хз — 40хз + Збх — 12ха — 14хз + 20х4 — 18хз — 12хв — 14хз + 44х4 — 20хз — 75хз + 8бх — 45 Часть ЧП. Избранные темы 928 По-другому произведение С (х) можно записать как зи-2 С(х)= ~схз, 3=о (30.1) где с =~) аьЬ (30.2) Заметим„что с1ебгее(С) = с1ебгее(А) + с1екгее(В), откуда вытекает, что если А — полипом степени не выше иА, а  — полипом степени не выше ин, то С— полипом степени не выше ил + ил — 1.
Тем не менее, поскольку полипом степени не выше к является также полиномом степени не выше /с+ 1, мы будем говорить, что произведение С является полиномом степени не выше иА + ин. Краткое содержание главы 30.1 Представление полиномов Представления полиномов в форме коэффициентов и в форме значений в точках в определенном смысле эквивалентны: полиному, заданному в форме точек- значений, соответствует единственный полипом в коэффициентной форме. В данном разделе мы познакомимся с обоими представлениями и покажем, как их можно скомбинировать, чтобы выполнить умножение двух полиномов степени не выше п за время тт (и 18 и). В разделе 30.1 описаны два способа представления полиномов: представление, основанное на коэффициентах, и представление, основанное на значениях в точках.
Для непосредственного умножения полиномов — уравнения (30.1) и (30.2)— требуется время Э (из), если полиномы представлены при помощи коэффициентов, и только 6 (и), когда они представлены в форме, основанной на значениях в точках. Однако с помощью преобразования представлений можно умножить заданные с помощью коэффициентов полиномы за время О (и 18 и). Чтобы понять, как это происходит, необходимо сначала изучить свойства комплексных корней из единицы, что и предлагается сделать в разделе 30.2. Затем также описанные в разделе 30.2 прямое и обратное быстрое преобразование Фурье используются для выполнения указанных преобразований представлений.
В разделе 30.3 показано, как быстро реализовать БПФ в последовательных и параллельных моделях. В данной главе широко используются комплексные числа, поэтому символ 1 будет использоваться исключительно для обозначения ~/ — Т. Глава 30. Полиномы и быстрое преобразование Фурье 929 Представление, основанное на коэффициентах Основанным на коэффициентах представлением (сое1йс!епг гергезеп!а!!оп) полинома А (х) = ~ ":о а хз степени не выше п является вектор коэффициентов а = (ао, ам..., а„1).
В матричных уравнениях данной главы мы будем считать векторы векторами-столбцами. Основанное на коэффициентах представление удобно при выполнении определенных операций над полиномами. Например, операция вычисления (еча!па!- !ля) полинома А (х) в некой заданной точке хо заключается в вычислении значения А (хо). Если использовать схему Горнери (Ногпег'з гп1е), вычисление требует О (и) времени: А(хо) = И ((а„1)хо+а„з)хо+ +аз)хо+а1)хо+по. Аналогично, сложение двух полиномов, представленных векторами коэффициентов а = (ао,ам...,а„1) и 6 = (Ьо,Ьп...,Ь„|), занимает время О(п): мы просто создаем вектор коэффициентов с = (со, см..., с„1), где с = а + Ь, 3' = О, 1,..., и — 1.
Рассмотрим теперь умножение двух полиномов степени не выше и, А(х) и В (х), представленных в коэффициентной форме. Если использовать метод, описанный уравнениями (30.1) и (30.2), умножение данных полиномов займет время 6 (пз), поскольку каждый коэффициент из вектора а необходимо умножить на каждый коэффициент из вектора Ь. Операция умножения полиномов в коэффициентной форме оказывается гораздо более сложной, чем операции вычисления полинома или сложения двух полиномов.
Результирующий вектор коэффициентов с, заданный формулой (30.2), также называется сверткой (сопчо!щюп) исходных векторов а и 6, и обозначается он как с = а ЗЬ. Поскольку умножение полиномов и вычисление сверток являются фундаментальными вычислительными задачами, имеющими важное практическое значение, данная глава посвящена эффективным алгоритмам их решения. Представление, основанное на значениях в точках Основанным ни значениях в точках представлением (рошьча!пе гергезепгабоп) полинома А (х) степени не выше и является множество, состоящее из и пар точка-значение (ро!пг-ча!пе ра1гз): ((хо,ро),(хырг), ",(х -ыр -1)), таких что все хя различны и уь = А(хь) (30.3) Часть Ч!!. Избранные темы 930 для к = 0,1,...,и — 1. Каждый полипом имеет множество различных представлений, основанных на значениях в точках, поскольку в качестве базиса такого представления можно использовать любое множество и различных точек хо,х1,..., х„п Получить основанное на значениях в точках представление полинома, заданного с помощью коэффициентов, достаточно просто: для этого достаточно выбрать и различных точек хо, хы..., х„| и вычислить А (хь) при /с = О, 1,..., и — 1.
С помощью схемы Горнера такое вычисление можно выполнить за время О (из). Далее мы покажем, что при разумном выборе хь данное вычисление можно ускорить, и оно будет выполняться за время 9 (и !я и). Обратная процедура — определение коэффициентов полинома, заданного в форме значений в точках, — называется интерполяцией (!и!евро!апоп).
В следующей теореме утверждается, что интерполяция является вполне определенной, когда граница степени искомого интерполяционного полинома равна числу заданных пар точка-значение. Теорема 30.1 (Единственность интерполяционного полинома). Для любого множества, состоящего из и пар точка-значение ((хо,уо),(хму1),...,(х„п у„1)), таких что все значения хь различны, существует единственный полипом А (х) с границей степени и, такой что уь = А (хь) для !с = О, 1,..., и — 1. 1 хо хо хо ао 1 х1 хзг х", а1 уо (ЗОА) 3 ь-1 хь-1 хп-1 хи †Матрица в левой части обозначается У (хо, хы..., х„г) и называется матрицей Вацдермонда (Уапдеппов$е). Согласно упражнению 28.1-11, определитель данной матрицы равен (хь — х ) о~~<ь<ь-1 следовательно, по теореме 20.5, она является обратимой (т.е.
невырожденной), ес- ли все хь различны. Таким образом, для заданного представления в виде значений в точках можно однозначно вычислить коэффициенты а;: а = У (хо, хм..., х„1) ' у Доказательство. Данное доказательство основано на существовании матрицы, обратной заданной. Уравнение (30.3) эквивалентно матричному уравнению Глава 30. Полииомы и быстрое преобразование Фурье 931 В доказательстве теоремы 30.1 предлагается алгоритм интерполяции, основанный на решении системы линейных уравнений (ЗОА). Используя описанные в главе 28 алгоритмы 1Л3-декомпозиции, эти уравнения можно решить за время О (пз) Более быстрый алгоритм и-точечной интерполяции основан на формуле Лагранзгеа (1 айтапйе'з 1оппп!а): П(.-*.) А(х) = ~г уь ~ я=о П(хь *3) уф.гс (30.5) ((ХО УО),(ХЫУ1) " (Х -ггУ -1)) иВ ((ХО, уО), (ХЫ у1),"., (Хн-Ы ун 1)) (обратите внимание, что А и В вычисляются в одних и глек же и точках), то основанное на значениях в точках представление полинома С имеет вид ((хо,ус+ус),(хг,у1+у1) ".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
