Блейхут Р. - Быстрые алгоритмы цифровой обработки сигналов (1044113), страница 61

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 61)

Помимо вектоРа Рш в шерациях алгоритма Левинсона участ. вует несколько рабочих переменных, задаваемых следующим абра. зом. Скалярные рабочие переменные обоаиачаются череа а„ й, и ул рабючий вектор дливы г обозначается через 1ОИ Все эти ра. бочие пйреьтенныг выбираются на каждом г-м шаге так, чтобы выполнялось следующее дополнительное ватричиое равенство: где в стоящем в правой части равенства векторе все за исключением одной номпаненты равны нулю.

Вееденне Рабочего вектора н дополвнтетьнош уравнения является разумной идеей, повво. лякнцей прополжать нтеративяый нропесс. Мьг хотим итерации организовать так, чтобы все уравнения имели одну и ту же форму. Следующая итерация начинается с уравнения которое определяет у„ и с уравнения которое определвет Р, и в правой части которого стоит вектор, всс внутренние компоненты ноторога равны нулю. Если у, — й, н Р, =- О, та В' †'и и унэп равны соэтветственно Ро и 7оД но с добавленными нулевыми компонентами, увеличиваюшнми нх ллину. В этим случае итерации завергпается В противном слу. чзс векторы Ун' и уог должны бып модифицированы. Как всегда в ренурсивном алгоритме, выберсьг начальные вна.

ненни всех переменных так, чтобы прн г = О выполнялвсь все уравневии, и предположим, что эти уравнения выполняются к копну гг — !Иго шага итераций. Нам надо только покааать, как надо модифицировать рабочие переменные, чтобы эти уравнения выполнялись и к нанну гло шага. Но мы можем также записать уравнения к Го " ~з,1 Из этих уравненвй можно сфорчировзть следующую итерацию.

Пусть дл» подлежащих дальнейшему выбору «онстант й, и й, выполняется зтт зге гз ы Б в сз р е»тв шювт «т и ! ь Р ти л г дуге Тогда откуда следует, гго й и нялнсь равенства у', ', й, лалжны выбираться так, чтобы выпал б = йт)),+й„а, и цгм = йтц,-~.й,() В салу произвольности выбора й, волотним й = а, ('Р в. ные возмажноспг бо выбора Д, приводят, однако. к различной точности.) Тогда йт =. вал, н а т =. — Я, н а, ~ = ц, — ))) Наконец, по.тожн» г, ь Л.,): где константа й, также подлежит вычислению; тогда (', ° ..

~(уг") ~з. ~ (е ~ ~з.) ~ гк,"( ~з, л ~е так, чтобы, . )г где для обеспечения правого равенства й дол б б олжио ыть вы рано ак, чтобы Ь .(- )г згы =. И,. Это завершает итерацию, Длгаритм Левенсона попытожен на рис 11.1. На нем векторы "и 1'о представлены соответственно многочленами 1( т— х . ч- Л к 1 )э', в нотарых опущен индекс г. Вычнслевия не нужлаюгся в фактическом вычисления матрицы Аой во время втераций достаточно вычислять мнагочлены ((к) и 1(к).

т ет. аег л: Сложность г-го прохода по ветви пропорциональна г, н всего имеется л проходов. Следовательно, сложность алгоритма Левинсона пропорциональна пт Шаг рекурсии приводит к неудаче только тогда, когда возникает деление на нуль, 1 что происходит толька тогда, когда одна из глаьч~ык падматриц вырождена. Алгоритм Левинсава прнченим в любом поле. В частности, в поле «омплексных чисел его можно использовать именно в тои виде, в котором ов был выписан. Однако в сея- ,= д,кг, ванных с комплекснмм нолем приложенияк симметричная теслицева матрица возникает ае часто; более распространеяной в этом случае является эрмитова теплицева матрица.

го) — лю,г — ' к Алгоритм Левинсона применим и в этом случае, но с перехадои в соответствующих местах вычислений к «омплексно сопряженным величинам. Реконсгрукнню алгоритма для этого слуяая сделать легко. Иногда вместо алгоритма в Левинсона лучше воспользо. е ° г ваться так называемым олго. рвшмом Лурбияа. Вто возмож- р . Нл. дагер л квв . но в тех случаях, когда матриПа симметрична и теплицева, а вектор в правой части фармиру ся на элементов теплнпевой матрицы так, что уравнение прииим следующий ннд: ,;, чз..г тг 11.1. Л. гор .

Бтра за. й„— й,.—.б и — т, — й,у,' + )),зч = — сню где т,'= — ~ ). '~аг. 1 т„= — ш ),,аг :;/ь! )', Эта л 11.Бн р е л гя вя шляц тмсн Г в Матрицу в оба вектора можно опять разбить на блоки, чт б выя нть лежащую в основе алгоритма повторяющуюся блочную о ми е структуру. Специальные свойства стоящего справа вентор-ст лб ф р руемого вз элементов теплицевой матрицы, позволяют вд у е шить необходимые в алгоритме Левинсона вычисления, так м нь кэк в итерации включается только один многочлен. В рассматриваемом виде теплнневы матрицы часто встреяаются в задачах спектрального анализа, н в зтпх случанх полезен а гор Д б л ритм Дур ина. г.й шаг алгоритма Дурбина начинается с решейяя следующей усеченной задачи: Следуюн1ая итерация начинается с уравнения определнюц1его переменную т, Целью итерации является такая модификация веитора ро, при которой велвчнна т„ стаяовитс» равной а„о Цусть В' " задается равенством )ут") туг 1уг' ! Узт У)"" )Л' ( 'У!",! !а) .-, „.'(,;Г.! )У'," ") ьо ) со ! )г ! Если нам удастся выбрать й„ и й, « ак, чтобы регенерировать же.

ла емый внд уравнений, то мы построим хороший алгоритм. Но при йекаторых у, и т,' имеет место равенство Для обеспечения нужного равенства й, н й, в оианчательном виде надо выбрать так, чтобы вьнюлнядись тсловия С.гедовательно, й, н )), надо полагать равными — тй д, =. )), и )), .=— !яз т)) Выписанные равенства позволяют продолжить решение г-го шага до решения )г, 1)-го шага, так что триваальнос решение нулевого шага рекурсивно продолжастсн до решения л-го шага.

Это завершает по- т строение алгоритма Дурбина. Окончательная форма алгоритма представлена блок-схемой на рис. 1!.2. 11.2. Алгоритм Треича В зависимости от наличия различных дополнительных свойств тенлицеву систему уравненвй можно решать многими различными алгоритмами В разя. 11.1 был расгмотрен случай, ко~да теплицева матрица снммегрячна В этом случае применим алгорнтлг Левинсона или Дурбина. В нв. стоящем параграфе рассматривается более общий случай, коп;а . дате тр а эвз <=-и, ...,2, ) = л, ..., 2, [э!') ь"" откчда Ыз Га )) Б р ' < а Р *с«л<м и своей н мней лолуераницей ло нисхсдяи!ей рекурсии 6«г, .= 6п )- — [ЬаЬ~ — Ь<Ьг), где лереал и последняя строка мотлицм равны соотеетстеенно' )Ьт )г [, 6,), а ледемй и последний столбны латр цм диелм соап еетгтегино [6<, Ь ) и [Ь, 6<).

Док зотельслмо. В теореме 1!.2.2 мы уже доказал», что Тэ» как матрица В<а является нерснмметрнчной, то можно также записать равенство Используя зти два разбиения матрицы В<'), выразим ес злеменпе 6<) двумя спосабаын Первый нз ннх дает 6)) =«') '+ — <Ь<"Ь<')г) ! — 1, ..., п--1, эс Второй дает е !— Исклк)чая элементы 6,<, прнхалнм к равенствам < — и о ) —.1, ...,н — 1, которые теперь содержат только помеченные индексам г величавы Зтк равенства задают восходящую рекурсию.

Аналою<чва странщя нвсходящая рекурсия, н эта заканчивает доказательство. 2) Доказательств) содержит еще один информатнвный фрагмент, который бущт ниже нспользоваа Выражая таящий э первой строке я первом столбце элемент нч первого равенства, получаем уран.

пенне < — и Т как Ь Ьг = Ь Ьг н согласно второму равенству 6)< — 6' ', то оно мажет быть переоисана в виде эе ) < — н <называющем величины Ьо' и Ьс Теперь нам нужно постронть алгоритм, вычисляющий папу. А<"). Но нас аннцу матрацы Вт) па полугранние матрицы у)ке выпвсавы уравненнн, связывающне границу ма р т ицы Ва) г г аннцей матрицы Ао). тек чта дтя построения зтога алтари<ма г тра вам остается талька нсключить матрацы А ' ' н М. Так челке можно выполннть, вводя обратна полутранииу предыдущего шага нтеравнй Теорема !1.2.4. Полу<ронино матр цм Вн) удеелетеодяе п с,мдующим рекуррентнмм уроенелт<м: '-:!'- ~ '"'.', ":-': "" й'3 м ![и:") <В»Ы -"+а! м,.,)[йф.е)) < Докитательстео Третье уравненне уже бм.

б ло вынедено кзк твае нз теоремы ! !.2 3. Из соображений симметрии ясно, что следствае нз теор . если выполняется первое равенство, то выполняет р С вательно, надо южно получить тем же самым способом. Следа показать толька первое равенства. Начнем р са вто аго з множестве полученных в докаэательстзе теоремы 1!. У р .2.2 четы ех равенств: Ао 'Ь") — , 'втбс<) О Так как матрнпа А<'-п является перснмметрнчной, то зто равен. ство можно танже нерепнсать в виде А< — и гЬ< ) ' аа)бе<') = О, Теперь воспользуемся снова уже применявшимся р ся анее разбиением ь<атрнпы В<' — '): где ач'.

записан в в анде вектора а' ') с одной дополнительной компонентой. Эю уравневне уже определяет искомую ренурсню, Зач Гл 11. Г ри и хн р м ппм х азарт р гр П Стаи Р»а 11.3. а юр н Тр 3 на мы уточниы его, = — Ь,о пВо "" '„'. ат воспользовавшись равенствам Ь' Тогда чта можно переписать в виде, входящем в формулировку теоремы Теперь у нас уже есть все необходимое для формулировки гаритма Т енча Все, р , что осталось спелать, сводится к гапону пе определению обоэн обозначений. при котором все величины, индекс !1.3. Алгоритм Берлекпмпа — ййесси Алгоритм Берлекэмпа — Месси представляет собой алгоритм решени» в произвольном пале р теплниевой системы уравнений вида '! Г. "," !-'1 ь а,= — ~Лат ь 1=-и, ..., йп.— 1.

4!атрнпа системы не нвляетгя сииметрической, что требуется для прим нимости алгоритма Левинсона. С другой стороны, стоящий а правой части систены вектор не являетси произвольным, а составлен из компонент петрины системы. Лучшим подходом к алгоритму Бервекэмпа — Мессн является кнтерпретапия выписанного чатричнаго уравнения как описания ааторсгрессиониого фильтра. Предположим, что вектор 1 итве стен. Тогда первая строка рассматриваемого натричмага уравнения ааределяег а„ через ам ап ..., а ,, вторая строка определяет аиы через ип ..,, а„, н т. д. Этот па" тедовгжельный прапесс описывается уравнением уе ше синволом г, стоят в левых частях рекурренткых уравнений, а зелнчины, индексируемые символам г — 1, стоят в правой части. Алгоритм Тренча подытажен на рис.

Характеристики

Список файлов книги