Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 24
Текст из файла (страница 24)
г1, -1 г1~ г2й 12,и — 1 12н 7*3й ... Г3 и 1 Гза ()а1 )( тй 1,й ... гй 1,„1 (й — 2) (й-1) (й-Ц айй ... ай„, (й-Ц (й-'Ц ай,й ... ай,„, А(й ') = (3) (й — Ц а„„1 а(й 1) 1 (здесь П означает, что сомножители берутся в порядке й — 1,..., 1). 1=й — 1 Обозначим а(1 ) = (ай(„),ай(„),О,...,О) Е К (4) — первый столбец подматрицы (а1 ); .
й „. Согласно лемме 1.12.3 существует (й-Ц матрица Тй й, — — Тй й „1(~рй й11), такая, что т й,й+1а1 = ~~~~а1 ~~~ ~Е1 (значения угла 1рйй+1 определяются леммами 1.12.2, 1.12.3), здесь е1 (т) (1, О,..., О)' Е К . Умножим матрипу (3) на Тй й.11 слева, получим 1 А'"'=Т, „А"-ц =ПТ;„„А, 1=й (б) Методы нахождения собственных значений К.Ю.Богачев ()а1 !) тгз (Ц П22 (Ц ~32 ~(а1~~ т12 г1з .. г, й , ~!о1 ~! 12з гз,й-1 (Ц !1а1'~! ... тз й, Г1,в — 1 Г1л О) О) аз „, а2„ (1) О) ОЗ,т — 1 НЗя Гй — 1,п (й-1) ай„ (й-Ц ай„, „ ~9. ЯЛ АЛГОРИТМ где А1й) = ~)а1~~ т,г тгз ...
т,й „ зн1 ~! 123 ° ° т2,й — 1 (1) 1! Г'~! ". 1'1й т!,й-~-1 12й 12,й+1 13й 13,й+1 11,в — 1 11в 12 в — 1 12п тЗ,п — 1 тгп ~)а1 ~) тй 1й 1й — 2) )(а1 )( тй,й 11 (й-1) (й)' ай+1 й, (й) ' 11й-~-2,й+1 1й — 1,в — 1 тй 1,„ тй„ (й) ай 11„ (й) ' ай+2 „ 1 й,в — 1 (й)' ай+1 „, (й) ' Ой+2,п — 1 1 Л=А~" ) = П ~Ъ+ А (8) где ()а1!) т12 т1з ...
т1 „2 !! Г'~! ~!а1 ) ~! тз, — 2 т1,„1 т1„ тг„1 тг 13 п — 1 13в (9) (/а~д ) !) тп 2в 1 ()а1 !) т„1,„ а1" ') (напомним, определения векторов а,, Й = 1,... (й — 1) таем, что а1 = а1). (о) Так как матрицы вращения ортогональные, то чаем , и — 1 даются в (4), где счи- Т1111 = Т11 и из (8) полу- А= ПТ1,„К=ЦЛ (10) искомое ЯВ-разложение.
Хранение матриц Я и В в памяти. Матрица В хранится на месте верхнего треугольника матрицы А и получается из нее последовательным применением Методы нахождения собственных значений К.Ю.Богачев (й) (й) а„„1 а„„ (7) Отметим, что в (6) матрица элементарного вращения Тй й11 умножается только на подматрицу (а;, ); й „матрицы А1й ') размера и — Й+ 1 (остальная часть А1й ') в преобразовании (6) не участвует). Следовательно, матрица А1й) получается из А<~ ') изменением двух строк (Й-ой и (1+1)-ой) длины и — 1+1.
После и — 1 шагов этого процесса (т.е. перехода от матриц (3) к (7)), матрица примет вид ~9. ЯЛ АЛГОРИТМ элементарных вращений (как описано вьппе). Д'1я хранения матрицы Я выделяются два вектора длины т1 — 1. В первом векторе хранятся значения сон 1а1 1+1, 1 = 1,2,...,п — 1, во втором векторе — значения з1п у;;.11, г = 1,2,...,п — 1.
Оценка количества арифметических операций Оценим трудоемкость и-го шага алгоритма, а затем просуммируем полученные оценки по всем Й = 1,..., и — 1. 1. На вычисление матрицы Тй й+1, участвующей в (6), согласно лемме 1.12.2 требуется 4 мультипликативные, одна аддитивная и одна операция извлечения корня. 2. На вычисление компонент й,..., и й-го столбца матрицы А1й), равных компонентам вектора ~~а1 ) ~~ е~ требуется (для вычисления длины век1й — 1) 1п — й-~-1) тора (4)) две операции умножения, одна операция сложения и одна операция извлечения корня. Столбец й вычисляется именно этим способом (а не по общим формулам (6)) для сокращения количества арифметических операций и уменьшения вычислительной погрешности. 3. Поскольку в формуле (6) матрица элементарного вращения умножается на подматрицу (а;, ); й „, й11 „матрицы А1й ') размера (п — 1+1) х (и — Й) (й-й столбец матрицы А1й) уже вычислен в пункте 2), то согласно лемме 1.12.5 на это требуется 4(п — й) умножений и 2(т1 — й) сложений.
Итак, на й-ом шаге алгоритма требуется выполнить 4+ 2+ 4(и — й) = 4(ив Й)+6 мультипликативных операций, 1+1+2(п — Й) = 2(п — Й)+2 аддитивных операций и две операции извлечения корня. Следовательно, всего для проведения алгоритма требуется выполнить 'у '(4(п — й) + 6) = 4п(п — 1)/2+ 6(п — 1) = 2п2+ 0(п) (и — й со) й=1 мультипликативных операций, ~":1'(2(п — к) + 2) = п2+ 0(п) (и — й со) аддитивных операций и ~":1" 2 = 0(п) (и -+ оо) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). Алгоритм построения ЯВ-разложения для почти треугольной матрицы методом отражений Обозначим а1 = (а11, а21,0,...,О)' Е К" — первый столбец матрицы А. Согласно лемме 1.13.9 существует вектор хр) Е С", равный а1 — !) а1() е1 !)а1 — !)а1 ()е1 )( такой, что 1т(х1'))а1 — — /!а1!/е1, где е1 — — (1,0,...,0) е С", Ет1 — — 11(хр)) матрица отражения.
Отметим, что у вектора х0) только первые две компоненты отличны от нуля. Следовательно, матрица Цх11)) отличается от единичной матрицы только блоком 2 х 2, стоящим на главной диагонали. Умножим матрицу К.Ю.Богачев Методы нахождения собственных значений ~9. ЯЛ АЛГОРИТМ А на 17(х(1)) слева, получим матрипу А(') = 17(х(!))А вида (1). Далее процесс применяется к подматрице (оч )14 2 (1) Пусть сделаны й — 1, й = 1,..., и шагов этого процесса, т.е. матрица преобразована к виду 1 А(~ ')= П ЦА, (12) где матрица А(" ') имеет вид (3), (13) здесь 1; ! ~ М; ! — единичная матрица размера (г — 1) х (г — 1), 17(х(1)) е М„11! — матрица отражения размера (п — 1+ 1) х (и — г'+ 1), построенная по вектору (! — 1) ~~ (1 — !) ~~ (п — 1-1-1) ~~ где е( ) = (1, О,..., О) ~ С'". Введем обозначение (4) для первого столбца подматрицы (а! ); 1 „. Со(й — 1) гласно лемме 1.13.9 существует матрица отражения (1.13.5) такая, что выполнено соотношение (1.13.6).
Введем матрицу 171, вида (1.13.7). Соотношения (1.13.8) и (1.13.9) показывают, что матрица У1! унитарна и самосопряжена. Отметим, что у вектора х(") в (1.13.5) только первые две компоненты отличны от нуля. Следовательно, матрица 11ь отличается от единичной матрицы только блоком 2 х 2, стоящим на главной диагонали. Умножим матрицу (3) на Уь слева, получим 1 А(ь) — Б„А(ь — !) — П г,"1А (14) (15) (16) затем — вектор х( ) = (аь(ь ) — //а(! )//,аь(!,~),О,...,О) Е С (17) Методы нахождения собственных значений К.Ю.Богачев где А(") имеет вид (7).
Отметим, что в (14) матрица У1! умножается только на подматрицу (а1- ); ь „матриць! А размера и — й + 1 (остальная часть (~-1) (ь-ц А(" ') в преобразовании (14) не участвует). Поскольку матрица 171! отличается от единичной матрицы только блоком 2 х 2, стоящим на главной диагонали в строках к и 1+ 1, то матрица А(") получается из А(ь ') изменением двух строк (й-ой и (1+1)-ой) длины п — 1+ 1.
Вычисления по формулам (1.13.5) осуществляются следующим образом: вначале вычисляются числа ~9. ЯЛ АЛГОРИТМ и его норма (18) Теперь можно вычислить искомый вектор х!"! х! !:= (х, ///х! ~!/,х~ ///х~ ~//,О,...,О) Е С" + . (19) После п !патов зтого процесса (т.е.
перехода от матриц (3) к примет вид ! ~= 1'"-'=П5,А, (7)), матрица (20) где матрица Л имеет вид (9). Так как матрицы 14 унитарные и самосопряженные, то 5!! — 1 из (20) получаем =Ь;*=Ци (21) Оценка количества арифметических операций Оценим трудоемкость к-го шага алгоритма, а затем просуммируем полученные оценки по всем й = 1,..., п. 1. На вычисление матрицы У(хь) по формулам (1.13.5) требуется а) 1 умножение для вычисления нь в (15): б) одно умножение, одно сложение и одна операция извлечения корня для вычисления ~~а, ~~ в (16),: в) одно вычитание для построения вектора хрй в (17); г) одно умножение, одно сложение и одна операция извлечения корня для вычисления ~~х!">9 в (18); д) 2 деления для построения вектора х® в (19). Всего для построения матрицы 17(хь) требуется 1+ 1+ 1+ 2 = 5 мультипликативных, 1+ 1+ 1 = 3 аддитивные операции и 1+ 1 = 2 операции извлечения корня.
2. Компоненты й,...,п й-го столбца матрицы А~"~, равные компонентам вектора ~~а! ~~~ е!" ~ 1, уже вычислены в (16). Столбец й вычисляется не по общим формулам (20) для сокращения количества арифметических операций и уменьшения вычислительной погрешности. 3. Поскольку в формуле (20) матрица 17ь вида (1.13.5) умножается на матрицу А~" 0 вида (3), то при вычислениях по (20) надо умножить матрицу отражения Методы нахождения собственных значений К.Ю.Богачев искомое ЯВ-разложение. Хранение матриц Я и В в памяти. Матрица В хранится на месте верхнего треугольника матрицы А и получается из нее последовательным применением матрип, отражения (как описано вьппе).
Для хранения матрицы Я выделяются два вектора длины п. В первом векторе хранятся первые ненулевые компоненты векторов х!0, г = 1, 2,..., п, во втором векторе - — вторые ненулевые компоненты векторов хй!, г = 1, 2,..., п. ~9. ЯЛ АЛГОРИТМ 120 1г(х~ь)) Е М„~+д на подматРиПУ (а~ )); ь „1 д+~ „матРицы А~" ') РазмеРа (и — й + 1) х (п — й) (й-й столбец матрицы А<") уже вычислен в пункте 2). Поскольку матрица У(х)")) отличается от единичной матрицы только блоком 2 х 2, стоящим на главной диагонали в строках 1 и 2, то то при вычислениях по (20) надо Умножить матРицУ отРажениЯ У(х~ь)) Е М„ь+~ на подматРипУ (а; ); ь ь~., ьч., „матрицы А размера 2 х (и — й) .
Согласно лемме 1.13.11 (ь-0 (й-1) на это требуется (и — Й)(2 2+1) = 5(п — Й) умножений и (п — Й)(2 2 — 1) = 3(п — Й) сложений. Итак, на й-ом шаге алгоритма требуется выполнить 5+5(п — й) = 5(п — И+1) мультипликативных операпий, 3+ 3(и — й) = 3(и — й+ 1) адцитивных операций и 2 операции извлечения корня. Следовательно, всего для проведения алгоритма требуется выполнить ~~, 5 (п — Й + 1) = 5п(п + 1)/2 = (5/2) п + О(п) (п — + со) 1=1 мультипликативных операций, Я, 3(п — Й + 1) = (3/2)па+ О(п) (и -+ оо) адцитивных операций и 2 ~, 2 = О(и) (и — + оо) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
