Алгоритмы - построение и анализ (1021735), страница 191
Текст из файла (страница 191)
(х -ыу -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 П; и ч "ии тетин.ттееие ~ тазе сй~;„'-'),' Преаставаеиие "тачка-значение" арена еп Рис. 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и из единицы. 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
