Марпл - Цифровой спектральный анализ и его приложения (1044218), страница 19
Текст из файла (страница 19)
(![о] с [!] ... с [м] !я с[о] ... с [м — !]! Н,ч —— (3.154» [с[м] с[м — !] с [0] Заметим, что Не= Н Вдакнам случае векторы элг -г,г (3 155) вхозящяе в уравнение!3!29), связаны свойством комялексной симметрии, поэтому зассет упрощенна рекурснй уменьшается калнчество вычислеапй необходимых для определенна обратной мшрнцы. В частнасюс,сетрудно показать, что векторы Ьм=ам (3 156| и скаляры (3.157) Тм=.бл связаны комплексно.соряженными соотнашеннямн.
Скалярный В ) ! 0 .. О][ 1 (ап[м] ... чг[!] !) [ О о о „о]( ьл [м] Рл с ., О, ! ьп[П . ьл[м] о) ь„[!] .. ьл[м] ! Ьл[1] ~- о О о„[М] «л [!] 0 ал [ '!4] М7 ыб Гаааа 3 чла р, который теперь удовлетворяет уравнению Рлл Рлг-л(1--[ал[М]!'), (3.158) явлегся действительным и положительным Это означает, что м бе( Ня = р, Д (1 — !а [й] !') > О. (3 159) л=! За чет использования соотношений (3.!56) — (3.!58) количество вычслеиий, требуеымх для определения вектора ам, я «эрмитов м» случае, уменыцается примерна вдвое но сравнению с «нермитовым» случаем.
В приложении 3.8 приведена написан. наяна Фортране программа ЕЕЧ!))50И, предназначенная для вымслен и коэффициентов а и скеляра Рм в случае эрмитоэой тел иценой матрицы. гналагнчно выражению (3.153) для обращения тецлицевой мапицы в общем случае можно зиоясать следующее выражение дляобращення зрыиюаой теплицевой матрицы !3.16О) 3.8.. Разложение на теплнцевы треу ольные атрнцы Алпритм Левинсона позволяет также определять элемааьц не. обхдимые для эффектпвного разло'кения матрицы, обратной эрмтовой теплицезай матрице, на треугольные мзтрицы по метод деленного [1, 21]. Поскольку процелура вычисления нсех аскаров решений низкого парадна аь..., ам является составнойчытью этага алгоРптма, можно опреаелить пронзеедение миоин (3.151) Тоби=О,, гдсТн — арчи»она тгнлнцевл матрице, а А,—.ни.
Реуголь- о ... о) [ ам[М] ... а [1] о о ом [М] Рм ! он [1] .. о',„[М] .-[1] ... В[М]1 (о ... о О) (О ам[М] ... ач [1] о! ам [М], 1]о о][о .. о о ная матрица, составленная из «екторов а, ш=о,..., М 1 о ... о о! а[1] 1 ... О О! ам[2] ая,[1] ... О О' (3.162) Ам = алг[М вЂ” 1] ол, [М вЂ” 2] ... ! 01 [ам [М] алл, гМ--1] ...
а,[1] 1! Используя уравнение (3.127), можно показать, что матрица б)и в правой части уравнения (3.161) предстааляет собой треуголь- ную матрицу слелуюшего вида: (Рл, л ... х О рн, ... к к! (3.163) Ом= о о ... р, [ о о ... о р,! где х обоаначает ненулевые недиагональпые эленеиты, конкрет. ные значения которых нас сейчас не интересуют. Если обе части уравнения (3 161) умножить слева на матрицу, армиюио сопряженную матрице Ан, то получим АнмТмАц А~иЯм Рл~ (3.164) где Ри — диагональная матрица следлюшего вида: Рл О ., О О о рм,, о о (3.165) О О О О р, О о (3.! 66) которая получштся в ре.лулызте перемножения двух эерхнетреугольных матриц. Альтернативным разложению (3.!М) является факторизация обратной лрмитовон теплнпевой матрицы по.
средством треугольаых матриц следующего внпа. Т:! =Алр,ч'А»" .!в э Н9 3.83. Бшение тепл цевык линейньж уравнений Алгоркм Левинсона лежит также в основе зл~аритмов, предназначен~их для решения систем линейных уравнений, содержащих тплицеву и эрмнтову теплнцеву матрицы. Рассмогрпм общие тплицевы линейные >равнения следующего вада.
Тихи — — зд, (3 167) где гя — известный (М - 1)-вектор-столбец (з[0] ! хо=.- ) (з[ ]) н хэ — неизвестнмй (М -Г!)-мерный вектор-столбец (хв (О) (3. (ьб) (3.169) хз,. -—— (хе[М]) Т х,=к, (3.170! где ААХМ, н а — (ж 11)-мерина вехтпр, образованныд из пер- вых тЕ! элементов векторе *ч, можно рекурсивно вычислить по векору решений х, чорядла т — 1 с помощью следующего уравнена (3.171) где а — не готорый сьаляр, котормб необходимо определить, а Ь вЂ вект.
определенный в (3.132). Для тога чтобы показать справцливпсть (3 171), просто умножим обе его сторонм слева на наряду Т и используем разбиение (3329), что дает об х х,—.-( ]4. и 0 тр Г (3.172) которьз необходимо определить Решение для к может быть осущезвлено на основе рекурсивного алгоритма Левинсона, если з метись, что вектор решения х параш з т тля линейных уравнннй где (1„.= г г У х,, —.
~ к [Д] 1 [ю — Д] . о (3.73) Шуро» д «азана теор мз, то лля зюа Э р ю стм сгзуэт орт нн. р а Вудсе верх э г В ( , ° г«г , ер, ( 1 с бэ) — Прим р д. Указанное равенство выполняется ярп а, .— (з [гл] — 9,„)(р (3.74) Таким абрахом, начиная с пухово~а порялкэ Г [О] х [О] = з [О], (3.75) вектор решения моднфидяруется в соответтвии с уравнеыем (3.171) иа каждом шите алгоритма Левинона для 1(тфМ. В случае эрмитовов матрицы вслользуется подстановка а,ь.= р Ь В приложении ЗГ приведена написнная нз Фортрне программа ТОЕРЕ!Т2, предназначенная д,я решения систмы линейных уравнений для случая комплекснг1теплицевой марнцы общего вида.
Этот алгоритм требует Здз операций умнскения н сложения и памяти объемом 6М (нл 5М, если вектаом решения является вектор в правой частя Равнения) В пр ложенни З.Д приведена написанная ь- Фортране прогрмма НЕЕМТОЕгР, предназначенная для решени системы линейых уравнений для случая эрмптовой теплицевй матрицы. В э!миговом случае количество вмчислнтельных аераций умеиьшется да 2М', а обьем памяти — до 4М (или д ЗМ, если нсползуются операции замещения). Цнбенко [6] станавил, что пгоритмы на основе алгоритма Левинсона бладают сравнжой численной устойчивостью с менее вычислмельно-эффектиным способам решения системы линейных уравнний на основе ьэтода факторизации Холецкого.
Ряд других вцросов, касающхся практичес~ад резлнззпии численных метоов решена» синем линейных уравнений, обсужпается в рантах [4, 9, 20, 13, 25, 26] Хотя рекурсивный алгоритм Лсвинсонавполие отнасити к числу наиболее шнрохо известных алгоритме для быстрого~явленного решения теплчцевых линейных урннеанб па ЭВМили микропроцессорах, это ни в коем случае неазначает, что огявлнется единственным бмстрым алгоритмом С помощью сврхбольших интегральных схем (СВИС) был геалнзаваналгортм [14], основанный на лгоритме Шура, хворый позволяетиспользовать преимущества систем обработк с парзллельноработающнмн процессорами. Операции вычсленвн скалярого произведения в алгоритме Левинсона >равнения (3.36), сзс 7) " (3.!7!!] будт« требав.«ть 1ой«М последоательнык сряменений М параллельных процессоров, поскольку олько по. сонина операний сложения может быть выполнена ж каждом ваге, что яэет общую пропускную способность така системы, авную М !ой«М рабочих циклов Общее количества вычнслнельных операций, требуемых алгоригмоы Шура, ропорцяа~ально М«, однако его структура проще алгоритма 1ееинсонв по«воляет устранить операции вы всаения скалярноо произее«ения и, следовательно, прп использовании М парллельныл ~роцессоров требуется М рабочих циклов.
.8.4. Характерист ческие свойства теплнцевых матриц 1есмотря на то что теплицева матрица имеет весьма оецифиче кую структуру, изучено не так уж много свойств сбствениых наченин и «об«таща«ыт аекторое конечначерных тпднцевых ~атрид [7, 17]. Пусть А (з)= ~ о[4]г « «=« (3 178) -характеристический полинам, формяруечый из «лементов [й] собственного вектора теплнцезо! (Мч.() Х (Мч!)-матрны Тм. Если Т вЂ” эрмитовз матрица, та она являетс частным лучаем центросямметрнчной матрипы.
Ее сабствсннь. векторы удут либо сопряженно симметричными, либо антисаряженно имметричными (см полр*зд. 373), а это означает,что полном А(з) будет также лабо сопряженно симметрия~мы, либо нтисопряженно симметричным. Применительно к это«у нолииау можно показать, что такой симметрией обладают .ории, явяющиеся взаимообратиымн парами [17). Таким обр ом, если — один из корней, то корнем будет тактке н 1С», Есд г лежит нутри единичной окружности, то 1)г, будет расположи вас ее. слн з, лежит на единичной окружности, то 1 з,=г,*будет его амплексна-сопряженным корнем (и тзк ке булег лжать на циничной окружности).
Если коэффициенты полиыма А(а) енстаительны, то комплексные нули являются кампсексно-соряженными парами. Если ««аксило«злое собственное значение ма«рицс Т знантельно отличается ог других ее собственных значени, то иожз показать (см. Разд, «Задач«ю), что корни полипом, образоаннаго из собственного ве«тора, соответствующего вксич альому собственному значению, лежат на единичной омужности о же справедливо и для собственного вектора, соатвествующе.
т минимальному собственному зизчеис«со, если оно акже су,естаенно отличается от других собстаенаых значений. Корни ыолнномз, образованного из остап .зых собствеинык зектороа, могут лежать, з чог)т и не лежать на езпничнои окружности, и« же спраиедливо, если максимальное иди минимальное собственные значения не единственны Из выражений (3 79) н (3 !45) пал)чаем, что собственные знзчения тсплицеаой матрицы 1, и «лементы Р, саят ны соотна. шепнем м м бе!Тм=П Р«=П 1"« «=з «=а След таяли~евой (Мя ЦХ(М-Ь1)-матРиЦм Тм пРосто Равен (М-1-1)С[0]. Исаользуя далее (3 8Ц, получаем [о]= — — ~' йм 1 М -!. ! Как будет показано а гл. б, элемент С[0] соответствует члену ав.
токорреляпионной последоавтельностн некоторого случайного процесса с нулевым временным сдвигом, т. е. полной мощности этого процесса. Таким образом, среднее собственных значений характеризует полную ыощность процесса. Можно определить асимптотическое паэедеянс собственных значений теплнцевык матриц, связав их с собственными значениями некоторой циркулянтной матрицы, для которой известна аналитическая сару«лура сабстиеннык значений.
Например, трехднагональную теплицев! (4Х 4)-матрицу с[о] с[-ц о о с[ц с[0] С] — ц 0 о с[ц с[о] с[ ц ( 0 О с[Ц с[0] можно аппроксимяровап наркулянтной матрицей с[о] 1(-..ц о с[ц с[ц с[о] с[. ц о о с[ц с[о] с[ — ц/' с[ ц о с[ц с[о] просто обаяляя соответствующие элемеаты в противоположных углах. 1!оскалину размер (4Х4)-матрицы можно увеличить до (пХл), то дае матрицы становятся ближе друг к другу в том смысле, что у них совпадает л' элементов ио всех позициях, кроме двух угловых.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
