Полиномиальная интерполяция

Мы уже видели, как вычислить A и B для множества всех корней (2n)-й степени из единицы с использованием O(n log n) операций; и как объясняется выше, произ- ведения С(оj^) = A^_ &)B(Kj2n) вычисляются за O(n) дополнительных операций.

Таким образом, для завершения алгоритма умножения A и B необходимо выпол- нить шаг (iii) приведенной выше схемы с использованием O(n log n) операций для реконструкции C из значений корней (2n)-й степени из единицы.

В описании этой части алгоритма следует иметь в виду один важный момент: как выясняется, задача реконструкции C решается простым определением соот- ветствующего многочлена (см. ниже D) и его вычислением для корней (2n)-й сте- пени из единицы. Только что было показано, как это делается с использованием O(n log n) операций, поэтому мы делаем это снова, выполняя дополнительные О{п log n) операций; это приводит к завершению алгоритма.

Рассмотрим многочлен, который нужно реконструировать

по значениям C(шs2n) в корнях (2n)-й степени из единицы. Определим новый многочлен. Теперь рассмотрим значения D(х)

для корней (2n)-й степени из единицы.


по определению. Теперь вспомните, что £⅛h = J . Используя этот факт

и расширяя запись до = (e2,lf J , даже когда s > 2п, мы получаем:


Чтобы проанализировать последнюю строку, мы воспользуемся тем фактом, что для каждого корня (2я)-й степени из единицы со Ф 1, имеем ∑,s_0 ω" = 0 .

Это следует из того, что со по определению является корнем x2n - 1= 0; так как x2n — 1 = (х — l)(Х^_0 *Ч и ω Ф 1, из этого следует, что ω также является корнем

Следовательно, единственная составляющая внешней суммы последней строки, отличная от 0, относится к ct, для которого ωt+j2yi = 1; а это происходит, если t + j

кратно 2п, то есть если t = 2п -j. Для этого значения /_^s=0 ω⅛2= z_^s=0 1= ∙ От-

сюда следует, что s ] = '2пc2jі_j . Таким образом, вычисление многочлена D(х)

в корнях (2n)-й степени из единицы дает коэффициенты многочлена C(x) в обрат- ном порядке (и умноженные на 2n). Подведем итог:

(5.14) Для любого многочлена и соответствующего много-

выполняется условие Все вычисления значений T>(ш_i>2и) выполняются за О{п log n) операций с ис-

пользованием метода «разделяй и властвуй», разработанного для шага (i).

На этом работа подходит к концу: мы реконструировали многочлен C по его значениям для корней (2n)-й степени из единицы, и коэффициенты C определяют координаты искомого вектора свертки c = a * b.

Итак, мы успешно продемонстрировали следующее:

(5.15) Использование быстрого преобразования Фурье для определения произ- ведения многочленов C(x) позволяет вычислить свертку исходных векторов a и b за время O(n log n).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Полиномиальная интерполяция:

  1. 4.4.1. Интервьюируемый определяет реакцию на часть стимульной ситуации
  2. Второй этап - ЗАПУСК НА ПОДСОЗНАНИЕ.
  3. I. 1. 1. Краткая характеристика системного подход.
  4. II. 3. 7. Понятийные базисы.
  5. Источники римского частного права.
  6. ГЛАВА 4. ПОНИМАНИЕ И ПОЗНАНИЕ МИРА (начало)
  7. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  8. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  9. ПЕРЕДМОВА
  10. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  11. Розділ І. Загальні положення цивільного права
  12. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  13. Тема 2. Цивільне законодавство України
  14. Тема 3. Поняття, елементи та види цивільних правовідносин
  15. Тема 4. Здійснення цивільних прав і виконання обов’язків
  16. Тема 5. Захист цивільних прав та інтересів
  17. Тема 6. Об’єкти цивільних прав
  18. Тема 7.ФІЗИЧНІ особи як суб’єкти цивільного права
  19. Тема 8. Юридичні особи
  20. Тема 9. Держава як суб’єкт цивільного права. Територіальні громади та Автономна Республіка Крим як суб’єкти цивільного права