Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 190
Текст из файла (страница 190)
Избранные темы 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) ". (х -ыу -1+у' 1)) Таким образом, время, необходимое для сложения двух полиномов степени не выше и, заданных в форме значений в точках, составляет 6 (и).
'Известно, что интерполяция является сложной задачей с точки зрения численной устойчивости. Хотя описанные здесь подходы математически корректны, небольшие различия во вводимых величинах или ошибки округления в ходе вычислений могут привести к значительным различиям в результатах. Можете самостоятельно убедиться, что правая часть уравнения (30.5) является полиномом степени не выше п, удовлетворяющим условию уь = А (хь) для всех й. В упражнении 30.1-5 предлагается показать, как с помощью формулы Лагранжа вычислить коэффициенты полинома А за время О (пэ).
Таким образом, вычисление и интерполяция по и точкам являются вполне определенными обратимыми операциями, которые позволяют преобразовать коэффициентное представление полинома в представление в виде точек-значений и наоборот . Решение этих задач с помощью описанных выше алгоритмов зани- 1 мает время О (пз). Представление в виде значений в точках весьма удобно при выполнении многих операций над полиномами. При сложении, если С(х) = А(х) + В (х), то С (хь) = А (хь) + В (хь) для любой точки хы Говоря более строго, если у нас есть основанное на значениях в точках представление полиномов А Часть Ч11.
Избранные темы 932 Аналогично, представление в виде точек-значений удобно при выполнении умножения полиномов. Если С (х) = А (х) В (х), то С(хь) = А(хь) В(хь) для любой точки хы и можно поточечно умножить представление А на соответствующее представление В и получить основанное на значениях в точках представление С. Однако возникает следующая проблема: с1еягее (С) = 11ейгее (А) + с1еягее (В); если А и В имеют границу степени т1, то граница степени результирующего полинома составляет 2п.
Стандартное представление каждого из полиномов А и В в виде значений в точках содержит т1 пар точка — значение. В результате их перемножения получится п пар точка-значение, однако для однозначной интерполяции полинома С с границей степени 2т1 требуется 2т1 пар (см. упражнение 30.1-4.) Следовательно, необходимо использовать "расширенные" представления полиномов А и В, которые содержат по 2п пар точка-значение каждое.
Если задано расширенное представление точки-значения полинома А, ((ХО~ УО) 1(Х1~ У1) ~ ~ (Хзь-1~ Узь — 1)) и соответствующее расширенное представление точки-значения полинома В ((хо Уо) (х1 У1) 1хз -ы У2 — )) то основанное на значениях в точках представление полинома С выглядит следу- ющим образом: ((хо~ УоУо) ~ (хы У1У1) ~. ~ (хзи-11Узп-1У2ь-1) ) Если два исходных полинома заданы в расширенной форме точки-значения, то время их умножения для получения результата в той же форме составляет О (п), что значительно меньше, чем время, необходимое для умножения полиномов, заданных в козффициентной форме. Наконец, рассмотрим, как вычислить значение полинома, заданного в виде значений в точках, в некоторой новой точке.
По-видимому, для зтой задачи не существует более простого подхода, чем преобразовать полипом в козффициеитную форму, а затем вычислить его значение в новой точке. Быстрое умножение иолиномов, заданных в коэффициентной форме Можно ли использовать метод умножения полиномов, заданных в виде значений в точках, время выполнения которого линейно зависит от т1, для ускорения умножения полиномов, заданных в козффициентной форме? Ответ зависит от способности быстро выполнять преобразование полинома из козффициентной формы в форму точки — значения (вычисление) и обратно (интерполяция).
Глава 30. Полиномы и быстрое преобразование Фурье 933 ~ Иичитн сне ~ рреи~ епт~!' 'т' тртр~,„" Ч.лртр;„" Ч > Преаставаение с крэффнииентаии Освеикч З тек ки~,~.: . с .с, л:снр О~". ~ ~ Юи рир. ~ ~ ~р~ ик з ~че Г срез".„3 и; и ч "ии е таин некие ~ 1езт сй~;„'-'),' Преаставаеиие "тачка-значение" арент еп Рис. 30.1.
Графическое представление эффективной процедуры умножения полино- мов. Вверху приводится представление в коэффициеитиой форме, а внизу — в форме точек-значений. ткущие слева направо стрелки соответствуют операции умножения. Члены ыз„являются комплексными корнями степени 2п из единицы В качестве точек вычисления можно использовать любые точки, однако тщательный выбор точек дает возможность выполнять переход от одного представления к другому за время ез (тз 1я п).
Как будет показано в разделе 30.2, если в качестве точек вычисления выбрать комплексные корни из единицы, то представление точки-значения можно получить с помощью дискретного преобразования Фурье (ДПФ) (131зсге1е Ропбег Тгапз1опп, 13ЕТ) вектора коэффициентов. Обратную операцию, интерполяцию, можно выполнить путем применения обратного дискретного преобразования Фурье к парам точки-значения, в результате чего получается вектор коэффициентов. В разделе 30.2 будет показано, что БПФ позволяет выполнять прямое и обратное ДПФ за время О (и 1кп).
На рис. 30.1 данная стратегия представлена графически. Небольшая сложность связана с границами степеней. Произведение двух полиномов степени не выше и является полиномом степени не выше 2п. Поэтому прежде чем вычислять исходные полиномы А и В, их границы степени удваиваются и доводятся до 2п путем добавления зз старших коэффициентов, равных О. Поскольку теперь вектора коэффициентов содержат по 2п элементов, мы используем комплексные корни 2п-й степени из единицы", которые обозначены на рис. 30.1 как ыз„.
Можно предложить следующую основанную на БПФ процедуру умножения двух полиномов А (х) и В (х) степени не выше и, в которой исходные полиномы и результат представлены в коэффициентной форме, а время выполнения составляет сР (и 1я тз). Предполагается, что гр является степенью 2; это требование всегда можно удовлетворить, добавив равные нулю старшие коэффициенты. 1. Удвоение границы степени. Создаются коэффициентные представления полиномов А(х) и В(х) в виде полиномов с границей степени 2п путем добавления и нулевых старших коэффициентов.
934 Часть Чй. Избранные темы 2. Вычисление. Определяются представления полиномов А (х) и В (х) в форме точки — значения длины 2и путем двукратного применения БПФ порядка 2и. Эти представления содержат значения двух заданных полиномов в точках, являющихся комплексными корнями степени 2и из единицы. 3. Поточечное умножение. Вычисляется представление точки-значения поли- нома С (х) = А (х) В (х) путем поточечного умножения соответствующих значений. Это представление содержит значения полинома С (х) в каждом корне степени 2и из единицы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
