|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[231] ния многочленов А(х) и В(х) в точках, являющихся корнями степени 2га из единицы. 3.Поточечное умножение. Поточечно умножить полученные значения многочленов А(х) и В(х) друг на друга. В результате получаются значения многочлена С(х) = А(х)В(х) в корнях степени 2га из единицы. 4.Интерполяция. Получить коэффициенты многочлена С(ж) при помощи обратного быстрого преобразования Фурье, примененного его значениям в корнях из единицы. Шаги 1 и 3 требуют времени О(га), а шаги 2 и 4 - времени в (га lgra), как мы увидим в следующем разделе. Тем самым будет доказана следующая теорема: Теорема 32.2 Произведение двух многочленов степени меньше га может быть вычислено за O(ralgra) операций. (Многочлены на входе и выходе задаются векторами коэффициентов.) Упражнения 32.1-1 Найдите произведение многочленов А(х) = 7х3 - х2 + х - 10 и В(х) = 8х3 - 6х + 3, используя формулу (32.2). 32.1-2 Значение многочлена А(х) степени меньше га в данной точке жо можно найти, разделив А(х) на многочлен (ж - жо) и получив частное q(x) (которое является многочленом степени меньше га - 1) и остаток г, для которых А(х) = q(x)(x - жо) + г. Ясно, что А(хо) = г. Покажите, как вычислить остаток г и коэффициенты многочлена q(x) за время О(га), если даны жо и коэффициенты многочлена А. 32.1-3 Многочлен А(х) = 5j=o азх3 задан набором своих значений в га отличных от 0 точках. Укажите га пар аргумент-значение, задающих многочлен Arev(x) = 2~j=o an-i-jX3 (Другими словами, надо указать га различных точек и найти значения многочлена Arev в этих точках.) 32.1-4 Покажите, как использовать формулу (32.5) для интерполяции за время 0(га2). (Указание: Сначала вычислите Па:(ж - хк), для вь1 числения j-oro слагаемого надо разделить полученный многочлен на (ж - Xj). См. упражнение 32.1-2.) 32.1-5 Почему не удаётся делить многочлены тем же методом, деля их значения поточечно? Рассмотрите отдельно случаи, когда многочлены делятся друг на друга нацело и и когда имеется остаток. 32.1-6 Рис. 31.3 32.2 Значения ш$,и>1,... ,и>1 на комплексной плоскости, где uig = е2тгг/8 - главное значение корня степени 8 из единицы. Рассмотрим два множества, А и В, каждое из которых содержит га целых чисел в диапазоне от 0 до Юга. Мы хотим найти их декартову сумму (Cartesian sum) А и В, определяемую как С = {х + у : х £ А п у е В}. Заметьте, что С может содержать целые числа от 0 до 20га. Нас интересуют элементы множества С, а также их «кратности» (сколькими способами данный элемент можно получить, сложив элемент А с элементом В). Покажите, что эта задача может быть решена за время в (га lgra). (Указание: представьте А и В многочленами степени не больше Юга.) 32.2 Дискретное преобразование Фурье. Быстрый алгоритм В разделе 32.1 мы собирались использовать комплексные корни из единицы как точки, в которых вычисляются значения многочлена, и говорили, что вычисление значений в них и интерполяция проводятся за время О (га lgra). Мы сейчас объясним, как это делается с использованием дискретного преобразования Фурье и быстрого алгоритма его выполнения. Комплексные корни единицы Комплексным корнем степени га из единицы (complex rath root of unity) называют такое комплексное число ш, что Имеется ровно га комплексных корней степени га из единицы. Они имеют вид е2жгк1п для к = 0,1,... , га - 1. Вспоминая формулу для экспоненты комплексного числа, можно написать еги = cos и + г sin и. На рисунке 32.2 видно, что комплексные корни единицы равномерно распределены на окружности единичного радиуса с центром в нуле. Значение ип = е2™1п(32.6) называется главным значением корня степени га из единицы (the principal rath root of unity). Остальные корни из единицы являются его степенями. Комплексные корни степени га из единицы образуют группу по умножению (см. раздел 33.3). Эта группа имеет ту же структуру, что и аддитивная группа (Zra, +), поскольку равенство oj™ = oj® = 1 j иj + k(j + k) mod n . i показывает, что 0Jnn = un = Аналогично, ujn = cj™-1. Докажем некоторые свойства корней из единицы. Лемма 32.3 (Лемма о сокращении) Для любых целых га О, fc 0 и rf > О 32.7 Доказательство Согласно (32.6), dk / 2iri/dn\dk dn Vе) 2Tri/n\k = LO, n к Следствие 32.4 Для любого чётного га > О ,гг/2 = CJ2 = -1. п Доказательство оставляется читателю в качестве упр. 32.2-1. Лемма 32.5 (Лемма о делении пополам) Если га > 0 четно, то, возведя в квадрат все га комплексных корней степени га из единицы, мы получим все га/2 комплексных корней степени га/2 из единицы (каждый - по два раза). Доказательство тт-hк-\-п/2 Легко проверить, что корни Lon и ujn отличаются знаком и при возведении в квадрат дают одно и то же число иа = ип/2 Лемма о делении пополам позволит свести вычисление значений многочлена в корнях из единицы степени га к вычислению значений других многочленов в корнях из единицы степени га/2. Лемма 32.6 (Лемма о сложении) Для любого целого га 1 и неотрицательного целого к, не кратного га, выполнено равенство Доказательство По формуле (3.3) (которая верна и для комплексных чисел) имеем (знаменатель не обращается в нуль, так как к не кратно га). Дискретное преобразование Фурье Вспомним, что мы хотим вычислить значение многочлена п-1 = о. 3=0 п-1 |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||