Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 60
Текст из файла (страница 60)
В этом случае стандартная итерацвя алгоритма Евклида на иоловину снижает размерность задачи, и мы ничего истерием, поскольку процедура дублирования' неприменима. форма полученной прк раэбвении второй половины задачи сов. плдает с формой исходной задачи, так что для ее вычисления можно опять вызвать процедуру ЕвкАлг Первая половина задачи амеет акалогнчную, но не идентичную форму, таи «ак вычисления с.че. дует закончить, если степени многочленов слишком малм Полы вану задачи можно также разбить пополам, так что мы приходим к формулировке вычислений в рекурсивном виде. Такая рекур.
санная процедура показана на рнс. 10.8 Обосноваггие этой про. дедуры можно провести метолам индукции. Нам надо показать, что вычнглякпся те же самые итерации алгоритма Евклида, которые опясываются теоремой 19.7.3 Зто всегла выполняется при о рав. ном 1 ц 2, так как в этом случае мм движемся по левой ветви иа рнс. 1О 8.
При движении по правой ветви в результате первого обращении к процедуре «Половина ЕвкАлг» согласно предпаложе вию индукции степень бей ) (х) уменьшаетсн до (л + й)72, что со. ставляет примерно ЗИ исходной степени мнагочлеиа у (х). Второе обра ценив к процедуре «Половика ЕвкАлг» аавершает описывае. мыс теоремой 10.7.3 итерации. 1О.В. Вычисление тригнноиетрнческих функций Для вьлнсления тригонометрических функций обычно исполь.
эуется некоторое разложение в степенной рнд. Такнеметоды сильно отличаются от рассматриваемык нами методов Имеется. однако, ряд приложений с привкусом стратегии дублирования, для ното- рых более подходяшимн яв.чяются описываемые нами методы. Первый из рассма~риваемых нами методов дается алгоритмом одновременного вычисления значений функний э|п О к соз 0 при заданном угле О Процесс вычислевии основываетсн на тригоно- метрических тождествах для упвоения угла э(п 20 = 2*1п Вес*О, соэ 2В = 1 — 2 нп' О, *(п 20 = 2 яп Π— 2 ми О чегэ В, чегэ 20 = 2 нп' О, гяе тегэ 0 = 1 — соз В Для вычисления начальных значений данный угол О делится на веноторую степень двух и испаль*уются приближенные форе а е мулы дая малых углов ыо — =.— и ьегг — =.О.
2 2 2 Точнагть а.ггоригма управляется вьгбором эвола ж. Велнчвнз угла 0 выражается в ралнавах и расположена в нрелелах шя. Алгоритм автомати чески помешает результат в правнльный квад. Зза Г Ю.К Р« 99 ь. 9 ю Р „а, Р«! азизы е« ЗЗ9 рант, так что не требуется нзкакого спецнального определения квадранта.
Окончательным результатам работы алгоритма яп ляется вычнсленне яп 9 к 1 — со* 6. Для того, чтобы числовые величины не становнлнсь слишком малымн, введем новые переменные 2 Х„== — „(ып 6)„, У„= — „(чета 8)„. Прн этом рекуррентные ураанення прнннмают знд Х =- Х„, — 2"ы-"Х,У, ь Х, =- 2"ш Х', где ш обоаначает полное чнсло шагов рекурснн, и начальные с. алто нт. ловца ранцы Х, = В, У, = О. На первой нтерацнн точи р ма определяется петре«пностью начального пркблнження ость н равна (Х,). = — (1)6) (6)2 )'. Эта погрешность прнводнт к (!)6) я«2 — ': финальным погрешностям, ограниченным сверх 3 рху елнчнной (ззпО). < — пзй — «, (созО) < 1 22 5 1 з Следовательно, если прк умножепнн обеспечено достаточное число точных батов, бнтах.
, ка!кдый шаг итерации увеличивает точность в дв ух Вюрой тригонометрический алгорнтм представляет собой нето ново ота. Вго р . можно использовать для аы'шслення декартовых коордннвт точки, поаернутай на угол В, нлн для вычнслення полярных коорднаат точки, заданной дека . товымн коордннатамн, н екар. 8 = агс19 — ",,и ч г Ллго нтм со р стоят нз некоторых вычислений н проверки логнческнх условий.
В основе злгорнтма лежит ю! ф , тр нт пу! факт, 'по трнганометрнческне тождества !26 мпО = и соьВ =. Р !2' й ) 2 2 !Ь Е позволяют легко нычнслнть поворот вектора на канн ны В = агс(й (2 '), В агом случае р каннретный угол 1 1 2 ып(агстй 2-") = — и соз(агс16 2 «) —— )' ь!тф) и 1О З Ли Рзпн Р «ж Рха" ю так что поворот вектора (х, у) на уюл 6» = агс(62-' задается равенствами (х —; 2 "у), УЗВБ )з у'= (у — 2 «х). Р' 1 -1- (2 ")! Для поворота на отрнцательный угол агс!9 2-" нснользуются те авнення, но с заменой знака у 2 «. Это не влияет на зелнчнну стоящего перед скобкой множителя. Длина вектора умножзет ся на фнкснрованную константу. Произвольный угол Оможсг быть прелстаален в виде В = ~ 90' †,' ~ [~ а!с!9 2 «) нлн В $9«уз 2; 6«агс!62 « = Е 6«9» «=9 — ! где й = — 1, О, 1, ..., 6« разно 1 нлн — 1, а 6«затабулнражтны на рнс.
10.9. Поворот на угол 9 просю сводится к поворотам на каждый нэ углов 8» с направлением, определяемым йю Неэавнснмо от знака каждого ннднвндузльного поворота после и! нтерапнй усиление разно ! В опчательном виде алгоритм показан на ркс. 10.10 Правило ок поворота нектара на первом шаге на угол ШВО' несколько т чается ог правнла остальных позоротаа. В дальнейшем решенне о 2 ! 5 1 2 9 ю а ц2 !м и! ! !ь !М2 1 Ы !лж »25Ь 1,5 ! !ЛО2« 99' «5' ж зькцс м озим-' ! ! гзом з змзз«' ! 7999П' Э 995!1«' Рыть «' ЕЗЗГМГ о !пня 9.955955* зП Рс (Осо ПО Гл Ю Б ре Рс ПРР . ИЫ * о повороте оа угол 6 .
— р Э ь вли †принимае т знакатыр уы квк скалирный множно едет лгоритм почти не соде ржет умножений Д д оичному сдвигу, так р тавление величины у Даваемое алгоритмом усилении известно ровано умножением ! бр Ою может быть пир у ыичину после выпа. Рао рати юв нтма. В больших задачах е лучше упритлть неся в д уп а и Дл вычислевпа а ! ( ' ) гс й (х,'у) некто апач у) ю ыжътй нт . ' направлеаии, кото итешош гюо(Р мы Ре у а фо р нем величин 6 с уче анан т, а рчированве гла 6 четам их знаков. ) 6 пр оп!пса су. ми. т Задачи Нлй Ы Рет атб ИРС р .б РО.2 Про «р Р*.иу « ° (З. Р,б,в,т, З, О, З, 2, б, Р, 4, В, 2, З, !), ЮЗ. а. Пр бл хе у БПФ- р тю Кули — Т Р ес ю еим .
Прюе б «.сыму ал ори луб иро и е в ре ур и й фори вю ь ксюрмт д р т и иий. Н й еффыти вмй ытгср у !е.з. Рюр болт ышр ра сЙр ир еюии р имюпр и ю), р й с ра ввт) Ро.7 Ис,тыу ир еыыжй ю ри (ОРО ы рл, е чи ит ' гй(2) (0.9. И, еу ы рит Ш р с ю, мж лв ь пр лыис ютрви Замечании р б х К уж Побй) и Ах, Х р фте и У стаи 6974) Обисие ((974). Ф лу (Ю72) р ме ил к ры м БПФ.елссри Ку — Тс,юы с Ф Ыйо РЬ Ы чыар ю я Б ру ((959), лы в ро- зтз л=( !!.!.
Алгоритмы Левинсона и Дурбина !лови 11 БЫСТРЫЕ МЕТОДЫ РЕШЕНИЯ ТЕПЛИЦЕВЫХ СИСТЕМ не вве Стандартный метод решения сясгемы л линейны» уран и стными состоит в записи этой системы в мат инно х уравнений с л А1 = й, в отысканы !=Ар,ли с ии решения либо с помощью обращения матр — ба помощью метода Гаусса Сложность стандартных методов обращения матрицы пропарпнанал в '.
И ьн лц нагда матрица имеет такой тамный вид, что им можно а освользоваться для построения более быстрого алгарнтиа. мат и а А Система линейных уравнений называется тепл ицевол, если ее пений возил атрина А теплицева. Задача решения тсплицевой о системы уран. нос о знлкает во многих ариложенвях, включвюлци х гпектраль. пеннвание, линейное предсказание, пос.„о снонвых фнльт ов и т , пос.„осипе авюрегрес. нльтров и теорию кодов, контролирующих ошибка. ак как теплипеаы системы уравнений имеют очень частвый вид, то для их решения существуют методы, которые намного лучше составляю п общих методов решенпя систем линейных уравнений Зг 1 щие предмет исслеповання в данной главе, справедливы длн проклвольвого поля. лнчаются Рассматрнваемме в настоягцей гаазе алгаритчы р несколько от.
све тли или от тех алгоритмов, которые мы постронли дл я вычислевня р и преобразования Фурье Свертка н преобразование па ' суитеству свалятся н матричному умножению, а в алллло~ Поэтом не иви адача решения системы линейных уравневнй.
наст осиным у уд шльно, что мы ве гможелг прямо воспальзав р . и ранее алгоритмами, катя такай метод, лаа дубливаться раввине, окажешься полезным. Задачи об а енв держат задач е р щ я свертки нлн спектрального оиеннван л у р щения теплицевой системы уравнений, за,лаваемой матричным раиенством гзо Л аредставляст собой теплицеву )п м п).матрац) Вычвсллжельная задача состои~ а вычислении вектора 1 па за. данным вектору й и теплииевой матрице А Одным из возможных исходов решени», конечно, является обращение матрицы А, од.
пако. првктически и може~ быть больше 100 или лаже ИЮО, так чта важно отыскать бачее эффективные методы решения задачи, Алгоритм Леви сана валяется эффективным алгоритмам, прю ченнмыы в том частном случае, когда матрица Л являегси адно временно теплюевай и симметричной В этап случае система уран. пений записывается в ниде Равделенве ллатрицы и векторов на блоки заесь сделано для тато, чтобы подчеркнуть лежащую в основе алгоритма повторяемость структуры. На каждол~ шаге )ктерация) к матрице А лобавляегся полояийв границы, состоящая из новой строки гнпзу и нового столбца справа Используя обменную матрнпу 3, уравнение Аг = — й можно переписать в виде 3Л33! — 3й, и 3А3 = А, так как матраца А ивляется симметричной н теолнцевай. Следовательно, ил«ест элес«о также равенство Зта форма уравнения также будет испояьзаватьгя при построении алгорлшиа Левинсава.
Алгоритм аперкрует с!« к «)-палматркцгми катрены Л вида зтз ы ~ д. в лш«с и дуэв '",г (с 7-к о, , 'и.~ Сг , ' з. Г ~г 7, в а, а а, ... а,, в гю г а г" гу которые получаются взматрицы А отбрасыванием последних л — г столбцов и такого же числа нижних строк Алгоритм Левенсона является гггератнвным. зти итерацан индексируются буквой г На г.м шаге алгоритм Левинсона вычис. лает решение г.го усечения задачи где верхний индекс г указывает на то, что вектор Во является ре. шепнем г.га усечення задачи. Вено, что если даже ро я является решением усеченной задачи, ои не равен усечеиию решения исходной задачи. Алгоритм Левинсона рекурсивно модернизирует Ум) таким образом, что уыг равно решению исходной задачи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
