Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 14
Текст из файла (страница 14)
а„„ (8) Отметим, что в (7) каждая из и — Й вЂ” 1 матриц элементарных вращений Тй„,, такова, что у > Й+ 1 и потому в (7) она умножается только на подматрицу (а~, )); й.1.1 „, й „матрицы А1й ') размера (и — й) х (и — й+ 1) (остальная часть А1й ') в преобразовании (7) не участвует). Умножим матрицу А на (Тй.1.1„...Тй„й~г)* = Т„*+, + ...Тй+,„справа, (й) Ф Э получим из (8) (с учетом того, что при умножении справа на Тй~1 „)' = й + 2,...,п столбцы 1,..., й матрицы А1й) не изменяются) и й-1-2 ч П Тй-1-1д П Тй-нйА П ~й~1йо З=й-~-2 З=ч у=й+г (9) а» с12 сгз С1,й 1 С2й 1 СЗ,й-1 Сзй (й-г) ай,й, Сй 1й Арй (й — Ц айй /~а~ ) // 1й) 1й-Ц а„й„, ...
а„„ (10) элементарных вращений и потому в (9) она умно- матрицы А1й ') размера (9) не участвует). Отметим, что в (9) каждая из и — й — 1 матриц Т,,'+, (йгй~1 ) = Тй.11 ( — 1рй„1 ) такова, что ) > й+ 1 -(й — ц ЖаеТСЯ ТОЛЬКО На ПОДМЗТрицу (а' ' )1 — 1 П у — й 1.1 ч и х (и — й) (остальная часть А1й ') в преобразовании К.Ю.Богачев Точные методы ретения линейных систем ()а1 )( агг сгз (ц ~)а1 ~! азз (/а~д )!) ()а1 )( агг сгз (ц ~!а1 ~! азз //а~ )!/ (й — Ц а1,й 1.1 (й-ц аг,и.1 (й-ц аз,н.1 (й — ц ай, й, (йбц айй, (й)' ай, й„, (й) ' ай„г й, (й) а,й, (й) аг й„, (й) аз,й+1 (й) ай, й, (й)' айй, (й)' ай , й„, (й) ай 12 й 1 1 (й-ц аьз (й-ц а2ч (й-ц аз„ (й — ц ай,„ (й-1) ай ~й) ай,„ (й) ' ай+2 „ (й) а1п (й) а,„ (й) ази 1й) ай,„ (й)' ай„ (й) ай,„ (й) ' ай-12, '314.
ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 65 После и — 2 шагов этого процесса (т.е. перехода от матриц (3), (4) к (9), (10)) матрица примет требуемый почти треугольный вид 2 1+1 и — 1 и В=А("-'= П Пт;,АП П т,,', 1=и — 1 1=и 1=2 1 =1-1-1 (и — 2) а,и, (и — 2) а2„, (и — 2) аэ,и — 1 (и-2) а, (и — 2) а2и (и-2) аэи С1и 2 С2и 2 СЗ,и — 2 ам с12 сы !МЛ (1) ~~а1ц!! а22 ~3,(2) и (12) (и-3) а и — 2,и — 2 (и — 2) а и — 2,и — 1 а (и — 2) и — 1,и — 1 (и — 2) аи,и-1 (и — 2) 2 (и — 2) аи,„ (и — 2) !/а(1 ) // (напомним, определения векторов а,, й = 1,..., и — 2 даются в (5), где счи(й — 1) таем, что а, = а1).
(о) Оценка количества арифметических операций в алгоритме приведения матрицы к почти треугольному виду унитарным подобием методом вращений Тй.1-1,1мй.1.1,3) Тй.1-1 1( 1)2й-1-1,1 ) и в формуле (9) каждая из этих и — й — 1 матриц элементарных вращений умножается только на подматрицу (а;, ); 1 и й+1 „матрицы А размера (й — 1) (й-1) К.Ю.Богачев Точные методы решения линейных систем Оценим трудоемкость й-го шага алгоритма, а затем просуммируем полученные оценки по всем Й = 1,..., п — 2. 1. На вычисление и — й — 1 матриц Тй й+1,..., Тйи, участвующих в (6), согласно лемме 12.2 требуется 4(п — Й вЂ” 1) мультипликативных, 2(п — Й вЂ” 1) аддитивных и и — Й операций извлечения корня.
2. На вычисление компонент й+ 1,..., и й-го столбца матрицы А("), равных (й — 1) (и — й) компонентам вектора ~(а1 ~( е, требуется (для вычисления длины вектора (5)) п — Й операций умножения, и — Й вЂ” 1 операций сложения и одна операция извлечения корня. Столбец й вычисляется именно этим способом (а не по общим формулам (7)) для сокращения количества арифметических операций и уменыпения вычислительной погрешности. 3. Поскольку в формуле (7) каждая из п — й — 1 матриц элементарных вращений умножается на подматрипу (а; ); й.1.1 и й+, „матрицы А размера (й — 1) (й — 1) (п — И) х (п — й) (й-й столбец матрицы А(й) уже вь1числен в пункте 2), то согласно лемме 12.5 на это требуется (п — й — 1)4(п — й) = 4(п — й)2 — 4(п — й) умножений и (п — й — 1)2(п — й) = 2(п — й)2 — 2(п — й) сложений.
4. Поскольку матрица, транспонированная к матрице элементарного вращения, опять является матрицей элементарного вращения: '314. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 66 и х (и — й), то согласно лемме 12.5 на это требуется (и — И вЂ” 1)4п = 4и(п — й) — 4и умножений и (п — й — 1)2п = 2п(т~ — к) — 2т~ сложений. Итак, на й-ом шаге алгоритма требуется выполнить 4(п — 1с — 1) + (и — й) + 4(п — й)' — 4(п — й) + 4п(п — й) — 4п = 4п(п — й) + 4(п — й)' + (и — й) — 4п — 4 мультипликативных операций, 2(п — Й вЂ” 1) + (и — Й вЂ” 1) + 2(п — Й)з — 2(п — Й) + 2п(и — Й) — 2п = 2п(п — Й) + 2(п — Й) + (и — Й) — 2п — 3 гддитивных операций и и — Й операций извлечения корня.
Следовательно, всего для проведения алгоритма требуется выполнить и — 2 ~,(4п(п — й) + 4(п — 1с) + (п — й) — 4п — 4) = 4п((п — 1)(и — 2)/2 — 1) я=1 +4((тз — 1) (и — 2) (2п — 3) /6 — 1) + (и — 1) (и — 2)/2 — 1 — 4(п — 2) (п + 1) 2пз «О(п~) «йиз «О(пз) -«О(пз) ьйиз «О(пз) (п + со) мультипликативных операций, 2 ~,(2п(п — Й) + 2(п — lс) + (и — Й) — 2п — 3) = Япз+О(пз) (и — + со) аддитивных операций и ~ ".:д(п — к) = О(пз) (п — + оо) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). Таким образом,на приведение матрицы к почти треугольному виду унитарным подобием методом вРащений тРебУетсЯ з" пз + О(пз) (и — ~ оо) мУльтипликативных операций и зпз+ О(пз) (и — ~ оо) аддитивных операций.
Заметим, что зто количество операций в два с половиной раза болыпе, чем нужно для решения линейной системы методом вращений. Теорема 1. Всякая невыроокденная вещественная матрица А моэкет быть представлена в виде А = ЯЛЯ', где матирица Я вЂ” ортогональная, а матрица Л вЂ” верхняя т~очти треугольная. Доказательство.
Проведем для матрицы А изложенный вьппе алгоритм, осуществимый для всякой невырожденной матрицы. Обозначим в (11) Я = г и~ П П Т;,. Как произведение ортогональных матриц, матрица Я ортогональз=й 11=И на. Тогда (11) имеет вид Л = ЯАсг1, откуда А = Щ) 'ЛЩ') ' = ЯЩ', где Я = Я)' = (Я) ' — ортогональная матрица. Матрица Л, имеющая вид (12), удовлетворяет условиям теоремы. Замечание 1.
Как отмечалось выше, построенное в теореме 1 разложение используется в ряде алгоритмов нахождения собственных значений матрицы. Хранение матриц Я и Л в памяти осуществляется одним из способов, изложенных при обсуждении алгоритма построения ЯЛ-разложения для матрицы А методом вращений. Трудоемкость алгоритма построения описанного вьппе разложения складывается из количества арифметических операций, необходимых для проведения самого алгоритма, и количества арифметических операций, необходимых К.Ю.Богачев Точные методы решения линейных систем ~14. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 67 для построения матрицы Я. Подробные выкладки были проведены при обсу- ждении алгоритма построения ЯВ-разложения методом вращений.
~ 14.2. Случай симметричной матрицы Рассмотрим ситуацию, когда описанный выше метод приведения к почти треугольному виду применяется к симметричной матрице А Е М„. Согласно (1), (2) Аи = Я1АЯ1~, где Я1 — — Тг„...Тг4Тгг — ортогональная матрица, т.е, А(ц и А унитарно подобны. Следовательно, Ац~ симметричная матрица. Согласно (7), (9) на Ь-ом (Ь = 1,...,п — 2) шаге алгоритма А~"~ = ЯьА~ь ЦЩ, где Яь = Ть+1, Ть+ць+3Ть+1,ф+2 ортогональная матрица. Следовательно, А~ь~ и А унитарно подобны, и А~ь~ симметричная матрица для всякого й = 1,...,п — 2.
Таким образом, В = А~" г~ - почти треугольная и симметричная, т.е. трехдиагональная матрица. Запишем описанный вьппе процесс приведения симметричной матрицы к трехдиагональному виду так, чтобы максимально уменыпить объем вычислительной работы за счет использования симметрии.
Лемма 1. Для всякой матрицы элементарного вращения Т; Е М„и всякой симметричной матрицы А Е М„матрица В = Т; АТ," 'моэкет быть вычислена эа 4п+ 8 умноэкений и 2п+ 4 сложений. Доказательство. Матрица В = Т; А согласно лемме 12.5 вычисляется за 4п умножений и 2п сложений. Матрица В = (Ьи) = Т; АТ," 'унитарно подобна А и потому симметрична: С другой стороны, матрица В = ВТ," 'получается из матрицы В = (Ьы) измене- нием элементов, расположенных только в ь'-ом и 1'-ом столбцах: Ь„=ььь 1Фь,~, Ь,1=1,..., .
Из последних двух равенств получаем: Ьы = Ьы, (Ь,1) ф (г,ь), (ь',1), О,ь) (~,Я Ь,1=1,...,п, т.е. у матриц В и В отличаются только 4 элемента с индексами (г, ь), (ь', 1'), Ц, ь), (у, 1). Эти элементы получаются умножением ь'-й и 1'-й строки матрицы В на матрицу Т;, справа и вычисляются по формулам Ьн — — Ьи соз д + Ь;. яп ~р;, Ь; = Ьн яп ~р; — Ь; соз ~р;, Ь,; = Ь;созд +Ь,яви;,, Ь = Ь" япд — Ь,,сезар; . Эти вычисления требуют дополнительно 8 умножений и 4 сложения.
Складывая это с трудоемкостью построения матрицы В, получаем требуемую оценку. К.Ю.Богачев Точные методы решения линейных систем 314. ПРИВЕДЕНИЕ МАТРИЦЫ К ПОЧТИ ТРЕУГОЛЬНОМУ ВИДУ 68 Замечание 2. Для несимметричной матрицы А вычисление матрицы В = Т;,АТ,', требует 8п умножений и 4п сложений (см. лемму 12.5). Обозначим а1 — — (агы..., а„1)'. Согласно лемме 12.3 существуют и — 2 матриц Тгэ = Тгг((ггг), у' = З,...,п, таких„что Тг„...ТгзТгза1 = ~~а1~(е," (причем (и — 1) значения углов <рг„у = 3,..., п определяются леммами 12.2, 12.3). Обозначим Аз' — ТгзАТгйз, А«') = ТгзАзДОТг~4, ..., А(,» = Тг„А~''1Тг'„. Все матрицы А,'), у = 3,4,...,п унитарно подобны А и потому симметричны.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
