Комплексные корни из единицы

На этой стадии необходимо вспомнить несколько фактов, касающихся комплекс- ных чисел и их роли в решениях полиномиальных уравнений.

Нам известно, что комплексные числа могут рассматриваться как точки «ком- плексной плоскости», оси которой соответствуют действительной и мнимой части числа.

Комплексное число записывается в полярных координатах по отношению к этой плоскости в виде reθi, где e = -1 (и e2mг = 1). Для положительного целого числа к полиномиальное уравнение Xk = 1 имеет к разных комплексных корней, которые легко определяются. Каждое из комплексных чисел ωJ.k = e2mjг/к (для j = 0, 1, 2, ..., к - 1) удовлетворяет этому уравнению, поскольку

(e2щHk)k = e2 %ji = (g2пj'у = у = у.

А так как все эти числа различны, то и корни тоже различны. Эти числа назы- ваются корнями k-й степени из единицы. Их можно представить как множество из k точек, разделенных одинаковыми расстояниями на единичном круге комплексной


Для наших чисел x1, ..., x2n, для которых должны вычисляться A и B, мы выберем корни (2n)-й степени из единицы. Стоит запомнить (хотя это и не обязательно для понимания алгоритма), что использование комплексных корней из единицы лежит в основе самого названия быстрого преобразования Фурье: представление много- члена P степени d его значениями для корней (d + 1)-й степени без единицы иногда называется дискретным преобразованием Фурье для P; «сердцем» нашей процедуры является метод ускорения этих вычислений.

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

Еще по теме Комплексные корни из единицы:

  1. § 21 Монетная единица платежа. – Уравнение ценности при замене одной единицы другой. – Понятие о законной, металлической и курсовой ценности. – Постановления иностранные и русского законодательства об уравнении ценности в платежах.
  2. Часть IV Корни
  3. Русские корни
  4. ВОСПРИЯТИЕ: ЕДИНИЦА ОПЕРАТИВНАЯ
  5. выделение единиц анализа
  6. ПСИХИКА: АНАЛИЗ: ЕДИНИЦА
  7. Корни
  8. Корни
  9. МЕТОД КОМПЛЕКСНЫЙ
  10. КОРНИ СПРАВЕДЛИВОСТИ