Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 209
Текст из файла (страница 209)
Избранные тены Очевидно, что А(хо) = т. Покажите, как вычислить остаток г и коэффициен- ты а(х) за время еэ(и), если заданы точка хс и коэффициенты полинома А. 30.1.3 Найдите представление в виде значений в точках полинома А""(х) 2 ". с а„1 хз, если известно представление в этом виде полинома А(х) с абхз; пРедполагаетсЯ, что все точки ненУлевые. Докажите, что для однозначного определения полинома с границей степени и необходимо задать и различных пар "точка-значение*', те. задание меньшего количества различных пар "точка †значен" не позволит определить единственный полинам с границей степени п. (Указание: используя теорему 30.1, что можно сказать о множестве из и — 1 пары "точка-значение", к которому добавляется еще одна произвольно выбранная пара "точка-значение"?) 30.1. 5 Покажите, как с помощью уравнения (30.5) выполнить интерполяцию за время ез(из).
(Указание: сначала следует вычислить представление полинома П. (х — х ) в форме коэффициентов, а затем разделить его на (х — хь) для получения числителя каждого члена; см. упр. 30.1.2. Каждый из и знаменателей можно вычислить за время 0(п).) 30.1. б Объясните, что неправильно в "очевидном" подходе к делению представленных в виде значений в точках полиномов, когда значения у одного полинома делятся на соответствующие значения у второго полинома. Рассмотрите отдельно случаи, когда деление полиномов осуществляется без остатка и когда имеется остаток. 30.1.7 Рассмотрим два множества, А и В, каждое из которых содержит и целых чисел в диапазоне от 0 до 10и.
Необходимо вычислить декарзваеу сумму (Саг1ез1ап ашп) А и В, определенную следующим образом: С = (х+ у: х б А и у Е В) Заметим, что целые числа из множества С заключены в пределах от 0 до 20п. Требуется найти элементы С и указать, сколько раз каждый элемент С выступает в роли суммы элементов А и В. Покажите, как решить зту задачу за время 0(п 1я и). (Указание: представьте А и В в виде полиномов с границей степени 10п.) Глава ЗО.
11спинассы и быстрое преобразование Фурье 949 30.2. ДПФ и БПФ В разделе 30.1 утверждалось, что, используя в качестве точек юмплексные корни из единицы, можно выполнять вычисление и интерполяцию полиномов за время ст(и 1я и). В данном разделе мы дадим определение комплексных корней из единицы и изучим их свойства, определим ДПФ, а затем покажем, как с помощью БПФ можно вычислять ДПФ и обратное ему преобразование за время сг(и 1я и). Комплексные корни из единицы Комплексным корнем п-й степени нз единицы (сощр1ех ийз гоог о1' шпгу) является комплексное число ы, такое, что п Существует ровно и комплексных корней и-й степени из единицы: ез г"г" при к = О, 1,..., и — 1.
Для интерпретации данной формулы воспользуемся следующим определением зкспоненты юмплексного числа: сои = соа(и) + таш(и) . На рис. 30.2 показано, что ть комплексных корней из единицы равномерно распределены по окружности единичного радиуса с центром в начале координат комплексной плоскости. Значение зкс,гп п (30.6) называется ааавнмм значением корня и-й степени нз едннннм (01е рппсгра! ийг гоо1 от оп(гу); все остальные комплексные корни и-й степени из единицы являются его степенямиз, Указанные и комплексных корней и-й степени из единицы о п — 1 С'гпс ц~пс ' ' с цсп образуют группу относительно операции умножения (см, раздел 31.3). Эта группа имеет ту же структуру, что и аддитивная группа (Ж„, +) по модулю и, по- 3 1с У 1 /с 0-1-Гс) псос1 п сюльку из цгп = ыо = 1 следует, что ызыь = ыг = цгй . Аналогично цг„1 = цг„" '.
Основные свойства комплексных корней и-й степени из единицы приведены в следующих леммах. тыногис авторы определяют ы„иначт ы„= с т Нс". Это альтернативное определанна обычно используется в обработка сигналов. Лсжыцис в основе ыагсыатичсскнс концепции в осиовноы одинаковы для обоих определений. Часть рц Избранные темы Рне. 30.2. Значения ыа, ьза,..., май на юмплексной плоскости, где иа = ез" га — главное значение корня восьмой степени из единицы. Лемма 30.3 (Лемма о сокрагнеиии) Для любых целых чисел и > О, )с > 0 и д > 0 130Л) Доказательство. Данная лемма непосредственно следует из уравнения 130.6), поскольку аа ( зльубп) " ( 2т(п) Следсизвие 30.4 Для любого четного целого и > 0 Мл/ =Шз = — 1.
и/2 Доказательство. Доказательство предлагается провести самостоятельно в качестве упр. 30.2.1. Лемма 30.5 (Лемма о депеиии иоиолам) Если и > 0 четное, то квадраты и комплексных юрней и-й степени из единицы представляют собой и/2 корней и/2-й степени из единицы. Доказательство. Согласно лемме о сокращении для любого неотрицательного целого и справедливо 1озь)2 = оз"„~2. Заметим, что если возвести в квадрат все комплексные корни и-й степени из единицы, то каждый юрень и/2-й степени из 95/ Глаеа ЗП Полинины и быстрое лреобралоаание Фурье единицы будет получен в точности дважды, поскольку Ь+н/212 2Ь+н га н гь и ( ь)2 Таким образом, квадраты ы„и ш„одинаювы. Это свойство можно также ье /г н/2 Ь+н/2 доказать с помощью следствия 30.4: из ьи„= — 1 вытекает ьи„ следовательно, (1и„ / )г = (и1ь)2. ь-у /г г Как мы увидим далее, лемма о делении пополам играет исключительно важную роль в применении декомпозиции для преобразования полиномов из представления в форме коэффициентов в форму значений в точках и обратно, поскольку она гарантирует, что рекурсивные подзадачи имеют половинный размер.
Лемме Зйьб (Лемма о суммировании) Для любого целого и > 1 и ненулевого целого lс, не кратного п, н-1 (ьан) = 0 . у=о Локвзвевельсвееа. Уравнение (А.5) применимо как к юмплексным, так и к действительным числам, так что имеем (ы"„)" -1 Е( ~)у на ( и)Ь ь (1)ь ь О. Посюльку мы требуем, чтобы к не было кратно и, и посюльку и1„" = 1 толью тогда, когда /с делится на и, это гарантирует, что знаменатель не равен нулю. ° 952 Часть 1гц Избранные темы Дискретное преобразование Фурье Вспомним, что мы хотим вычислить полинам и — 1 А(х) = ) айхз с границей степени и в точках ш'„',ш„',шг,...,ш„" 1 (которые представляют со- бой и комплексных корней и-й степени из единицы)з. Предположим, что поли- нам А задан в форме коэффициентов: а = (ас, а1,..., а„1).
Определим резуль- таты уы где 5с = О, 1,..., и — 1, с помощью формулы уй = А(шй) гг-1 а шйз з=с (30.8) Быстрое преобразование Фурье С помощью метода, известного как быстрое нреоброзонание Фурье, БПФ (Габг Гоцпег Тгалб1опп — ГРТ), основанного на использовании специальных свойств комплексных корней из единицы, ДПФ„(а) можно вычислять за время еу(п )л и), в отличие от метода непосредственного преобразования, имеющего время работы ез(пг). Будем считать, что и является точной степенью 2. Хотя известны методы, работающие и с другими значениями, в нашей книге они не рассматриваются. В методе БПФ применяется стратегия декомпозиции, в которой отдельно используются коэффициенты полинома А(х) с четными и нечетными индексами, чтобы определить два новых полинома, А(с) (х) и А(') (х), с границей степени п/2; А( )(х) = ос + агх + адх + .
+ а„— гх~~ А( ) (х) = а1 + азх + абх + + а„гх"~ Заметим, что А(с) содержит все коэффициенты А(х) с четными индексами (двоичное представление этих индексов заканчивается цифрой 0), а Ай) содержит все коэффициенты с нечетными индексами (двоичное представление которых закан- Еэдесь п на самом деле предстаыысг собой величину, которая в разделе 30.1 обозначалась как 2п„поскольку, прежде чем выполнять вычнсленне, граннпы степеней заданных полнномов была удвоены Таким обравгм, прн умноненнн полнномов речь в дейсгвнтельноспг ндег о комплексных корнях нз еанннпы 2гг-й степени.
Вектор у = (ус, ум..., у„1) представляет собой дискретное лреоброзование ФУРье, ДПФ (бзйсгеге Роппег 1гапвропп — РРТ) вектоРа коэффиЦиентов а = (ас, а1,..., а„1). Можно также записать у =ДПФ„(а). Глава ЗО. Полинины и быстрое нреобралование Фурье 955 чивается цифрой 1). Отсюда следует, что А(х) = А(о)(хг) + хА(1)(хг) (30.9) так что задача вычисления А(х) в точках ьоо,ыг,...,ьо„" 1 сводится к следующим задачам: 1. вычисление полиномов А(о)(х) и А)1)(х) с границей степени и/2 в точках О)2 ( 1)2 ( о-1)2, (30.10) 2.
а затем объединение полученных результатов в соответствии с уравнением (30.9). Квс15кз1чп-РРТ(а) 1 и = а.1епдгЬ 2 11п==1 3 гегпгп а 4 ы„= егн1!о 5 ы=1 6 а)о) = (ао,аг,,а„-г) 8 у~~) = Кпс15кячп-ЕЕТ(а~~)) 9 У~1) = Квс15кячв-ггТ(а~11) 10 1огк = Отоп/2 — 1 11 ун = ун + ыу„ 1о) !1) )о) 01 Уь~-(о/2) = Уь ыуь 13 ы = 1оьо„ !4 гетпгп у // и является степенью 2 // Считаем, что у — вектор-столбец Процедура Кпс15кячп-РРТ работает следующим образом. Строки 2 и 3 представляют базис данной рекурсии: ДПФ одного элемента является самим этим Согласно лемме о делении пополам список значений (30.10) содержит не и различных значений, а только и/2 комплексных корней степени и/2 из единицы, причем каждый корень встречается в списке ровно дважды.
Следовательно, полиномы А)о) и А(0 с границей степени и/2 рекурсивно вычисляются в и/2 комплексных корнях и/2-й степени из единицы. Эти подзадачи имеют точно такой же вид, как и исходная задача, но их размерность вдвое меньше. Таким образом, мы успешно свели вычисление и-элементного ДПФ„к вычислению двух и/2-элементных ДПФ„~2. Такая декомпозиция является основой следующего рекурсивного алгоритма БПФ, который вычисляет ДПФ и-элементного вектора а = (ао, а1,..., а„1), где и представляет собой степень 2.
Часть Ис' Избранные темы элементом, следовательно, в этом случае Уо = по ш1 О =ос 1 у[о) А[о) (шь Уь = 4 (ша(2) с [1) [ц ь или, поскольку согласно лемме о сокращении ш„" = шз", [о) 1[0) ( 2ь) „[) А[()( 2ь) В строках 11 и 12 выполняется комбинация результатов рекурсивных вычислений ДПФ„72. Для уо, ум..., У„(г 1 строка 11 дает УЬ = Уь + шаУь [о! ь Р! А[о)(,Р') + шьА[()(шзь) = А(ш„") (согласно (30.9)) . Для у„72, у„(2~1с..., У„н полагая к = О, 1,..., и/2 — 1, в строке 12 получаем [о) ь [Ц уь-ь(. !2) = уь — шауь [0) + Ь+(а!2) [1! А[0)(с ~2Ь) ) с ~Ь~-(ас'2) 4[Ц(с ~2Ь) ~[0)( 2М-а) + ШЬ+(а/2) 1[Ц( 2Ь+а) ~а ~а И = А(шь"(*12)) (так как ш„( ~ ) = — шь) (так как ш2" с " = ш2") (согласно (30.9)) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
