Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 208
Текст из файла (страница 208)
Операция умножения полиномов в форме коэффициентов гораздо сложнее, чем операции вычисления полинома или сложения двух полиномов. Результирующий вектор коэффициентов с, заданный формулой (30.2), также называется сверткой (сопио!шюп) исходных векторов а и Ь, и обозначается как с = а З 6. Поскольку умножение полиномов и вычисление сверток являются фундаментальными вычислительными задачами, имеющими важное практическое значение, данная глава посвящена эффективным алгоритмам их решения.
Представление, основанное на значениях в точках Основанным на значениях в точках лреоставленяем (ро)пика1пе гергезепгайоп) полинома А(х) с границей степени п является множество, состоящее из п яар иточка-значение (ро(пьиа!пе раке): ((хо,Уо) (х| У1) . (х -1 У -1)) таких, что все хь различны и уь = А(хь) (30.3) для /с = 0,1,...,и — 1. Каждый полипом имеет множество различных представлений, основанных на значениях в точках, поскольку в качестве базиса такого представления можно использовать любое множество и различных точек хо,хп...,х„п Получить основанное на значениях в точках представление полинома, заданного с помощью коэффициентов, достаточно просто: следует лишь выбрать п различных точек хс, хп, .,, х„1 и вычислить А(хь) для 6 = О, 1,..., и — 1.
С помощью схемы Горнера такое вычисление можно выполнить за время еэ(из). далее мы покажем, что при разумном выборе хь данное вычисление можно ускорить, н оно будет выполняться за время 8(п )к и). Обратная процедура — определение коэффициентов полинома, заданного в форме значений в точках — называется интерполяцией (1п1егро)а11оп). В следующей теореме утверждается, что интерполяция является вполне определенной, когда граница степени искомого интерполяционного полинома равна числу заданных пар "точка-значение". Чаезнь Нц Избранные анны Таирами 30.1 (Единственность интерноляционного налимами) Для любого множества ((хо, уо), (х1, у! ),..., (х„1, У„1) ), состоящего из и пар "точка — значение*', таких, что все значения хь различны, существует единственный полином А(х) с границей степени и, такой, что уь = А(хь) для (е = О, 1,..., п — 1. Докизизиельствш Доказательство основано на существовании матрицы, обратной заданной. Уравнение (30.3) эквивалентно матричному уравнению 2 н — 1 1 то хо '' хо по Уо 1 х! х21 х" а! У! (30.4) а„! Ун — ! 2 н — 1 Хн-1 Хн-1 ' ' ' Хн Матрица в левой части обозначается как Ъ'(хо, х1,..., х„1) и называется матрицей Вандермонда (Уапз!еппопбе).
Согласно упр. Г1 определитель данной матрицы равен (хь — х ), о<1<ай -1 следовательно, по теореме Г.5 она является обратимой (т.е. невырожденной), если все хь различны. Таким образом, для заданного представления в виде значений в точках можно однозначно вычислить коэффициенты аз: а = 'е'(ХО,Х1,...,Х„1) У Доказательство теоремы 30.1 предлагает алгоритм интерполяции, основанный на решении системы линейных уравнений (30.4). Используя описанные в главе 28 алгоритмы (ЛЗ-разложения, эти уравнения можно решить за время 0(пз).
Более быстрый алгоритм п-точечной интерполяции основан на формуле Лагранжа (1.аятолле'а Гоппп!а): П(.-х ) А(х) = ~~1 уь з =. П(х —.) 1 ф/с (30.5) Можете самостоятельно убедиться в том, что правая часть уравнения (30.5) является полиномом степени не выше и, удовлетворяющим условию уь = А(хь) для всех (е. В упр.
30.1.5 предлагается показать, как с помощью формулы Лагранжа вычислить коэффициенты полинома А за время 9(пз). Таким образом, вычисление и интерполяция по и точкам являются вполне определенными обратимыми операциями, которые позволяют преобразовать представление полинома в виде коэффициентов в представление в виде точек- 945 Глава 30. Полинины и быстрое лреобразотгиие Фурье значений и обратно'. Решение этих задач с помощью описанных выше алгоритмов занимает время ку(пг). Представление в виде значений в точках весьма удобно при выполнении многих операций над полиномами. При сложении, если С(х) = А(х) + В(х), то С(хй) = А(хь)+ В(хь) для любой точки хь.
Говоря более строго, если у нас есть основанное на значениях в точках представление полиномов А Ихо уо) (х1 У1) (х — ьу -1)5 иВ Ихо уо),(х1 Р1) " (х -ьу' 1)) (обратите внимание, что А и В вычисляются в одних и лзех же и точках), то основанное на значениях в точках представление полинома С имеет вид Ихо Ус+Ус) (х1 У1+У1), . (х — ьу — 1+У -1)) Таким образом, время, необходимое для сложения двух полиномов с границей степени п, заданных в форме значений в точках, составляет ту(п). Точно так же представление в виде значений в точках удобно при выполнении умножения полнномов. Если С(х) = А(х)В(х), то С(хй) = А(хь)В(хь) для любой точки хы и можно поточечно умножить представление А на соответствующее представление В и получить основанное на значениях в точках представление С.
Однако возникает следующая проблема: г(еятее(С) = г(ейгее(А) + г(ейтее(В); если А и В имеют границу степени п, то граница степени результирующего полинома составляет 2и. Стандартное представление каждого из полиномов А и В в виде значений в точках содержит и пар "точка-значение". В результате их перемножения получится и пар "точка — значение", однако для однозначной интерполяции полинома С с границей степени 2п требуется 2п пар (см. упр. ЗОВА.) Следовательно, необходимо использовать "расширенные" представления полиномов А и В, которые содержат по 2п пар "точка-значение".
Если задано расширенное представление в виде значений в точках полинома А Ихо уо), (х1, у1),..., (хг -1, уг -1)) и соответствующее расширенное представление в виде значений в точках поли- нома В Ихо уо) (хьу1) (х2 — 1 уг -1)) то представление полинома С имеет вид Ихо уоуо)з(х1зу1Р1) з(х2п — 1 у2п — 1Р2п — 1)) Известна, чш ннтерпаляиия валяется неприятной задачей с точки зрения численной устойчивости: хотя описанные здесь подходы математически изррекзны, небольшие различия во вводимык величинах нлн ошибки округления в ходе вычнсмний мазут привести к значительно различаюшимсв результатам. 946 Часвь Гд избранные темм Если два исходных полинома заданы в расширенной форме "точки — значения", то время их умножения для получения результата в той же форме составляет 9(п), что значительно меньше, чем время, необходимое для умножения полиномов, заданных коэффициентами.
Наконец рассмотрим, как вычислить значение полинома, заданного в виде значений в точках, в некоторой новой точке. По-видимому, для этой задачи не существует более простого подхода, чем преобразовать полипом в форму коэффициентов, а затем вычислить его значение в новой точке. Быстрое умножение полиномов, заданных коэффициентами Можно ли использовать метод умножения полиномов, заданных в виде значений в точках, время выполнения которого линейно зависит от и, для ускорения умножения полнномов, заданных в форме коэффициентов? Ответ зависит от способности быстро выполнять преобразование полинома из формы коэффициентов в форму "точки-значения" (вычисление) и обратно (интерполяция). В качестве точек вычисления можно использовать любые точки, однако тщательный выбор точек дает возможность выполнять переход от одного представления к другому за время 9(п 1й и). Как будет показано в разделе 30.2, если в качестве точек вычисления выбрать комплексные корни из единицы, то представление "точки-значения" можно получить с помощью дискретного преобразования Фурье (ДПФ) (Р(зсгеге Роплег ТгапзГопп — РГТ) вектора коэффициентов.
Обратную операцию, интерполяцию, можно выполнить путем применения обратного ДПФ к парам "точки-значения", в результате чего получается вектор коэффициентов. В разделе 30.2 будет показано, как БПФ позволяет выполнять прямое и обратное ДПФ за время 9(п1кп). На рис. 30.1 данная стратегия представлена графически. Небольшая сложность связана с границами степеней.
Произведение двух полиномов с границей степени п является полиномом с границей степени 2п. Поэтому перед вычислением исходных полиномов А и В нх граниша степени удваиваются до 2п путем добавления п старших коэффициентов, равных нулю. Поскольку теперь векторы коэффициентов содержат по 2п элементов, мы используем комплексные корни 2п-й степени из единицы, которые обозначены на рис. 30.1 как шз„, Можно предложить следующую основанную на БПФ процедуру умножения полииомов А(х) и В(х) с границей степени п, в которой исходные полиномы и результат представлены в форме коэффициентов, а время выполнения составляет 9(п 1я и). Предполагается, что и является степенью 2; это требование всегда можно удовлетворить, добавив равные нулю старшие иээффициенты. 1.
Удвоеиие границы степени. Создаются представления в форме коэффициентов полииомов А(х) и В(х) в виде полиномов с границей степени 2п путем добавления л нулевых старших коэффициентов в каждое. 2. Вычисление. Определяются представления полиномов А(х) и В(х) в форме "точки — значения" длиной 2п путем двукратного применения БПФ порядка 2п. Этн представления содержат значения двух заданных полииомов в точках, являющихся комплексными корнями степени 2п из единицы. рв7 Прслставлснис ( козффнциситами !. аа.ай,.; Лл ы.', Обычное)ывожа1Н Ьь'-Ья.с-я' (тв ( ''( Вымя В(яр! Представление значсннями в тачым Рнс.
ЗВЛ. Графичссвос прсдставлснис эффективной процедуры умнвксннл полиномов. Ввсрху показано прсдставлснис л форме нззффициситов, а внизу — в форме значений в точках. Идущие слова направо стрелки соогввтствукп операции умнвкения. Члены ыз явлтотсл вомплсксными корнлми стспсни 2п из единицы. 3. Поточечное умножение. Вычисляется представление в виде значений в точках полинома С(х) = А(х)В(х) путем поточечного умножения соответствующих значений. Это представление содержит значения полинома С(х) в каждом юрие степени 2гь из единицы. 4. Интерполяции.
Создается представление полинома С(х) ф форме юзффициенгов с помощью однократного применения БПФ к 2п парам "точка — значение*' для вычисления обратного ДПФ. Этапы 1 и 3 выполняются за время ет(п), а этапы 2 и 4 — за время тт(п (к и). Таким образом, показав, как испольювать БПФ, мы докажем следующую теорему.
Теорема 36~2 Произведение двух полиномов с границей степени п в случае, югда исходные полиномы и результат находятся в форме коэффициентов, можно вычислить за время тт(тз (к п). Упражнения Зй 1.1 Перемножьте полиномы А(х) = Тхз — хз + х — 10 и В(х) = бхз — бх + 3 с ис- пользованием (30.1) и (30.2). За1.2 Вычислять полипом А(х) с границей степени п в заданной точке хо можно также путем деления А(х) на полипом (х — хо)„в результате чего получатся полином- частное о(х) с границей степени п — 1 и остаток г, такой, что А(х) = я)(хНх — хо) + т . Глава зй Павиламы и быстрое лрвабраюванлв Фурье ' Пмяисясвмс Время В(л)лл) .з((с(~~',) 'лбавв„) ' .. я((с".яя)(В(ь)вв):!, ' Пстстсчврс~няожсйир Время 0(л) !~'-9«,:,ят:ь) й(а зя-я); ( ; Иитсрповшия ! Врсмв 8(л (ял) ! ', с(!(й,) ! П(а(я',)'; ( ц((яс(зыв - (з э 948 Часть ру.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
