Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (Богачев - Практикум на ЭВМ), страница 10

Алгоритм метода вращений Пусть требуется решить линейную систему А х = й, А Е М„(И.н) вида (4.1). Обозначим а1 — — (ап,..., а„1)' -- первый столбец матрицы А. Согласно лемме 3 сушествуют и — 1 матриц Т13 — — Т13(ф13), Т13 — — Т13(1Р13),, Т1~ = Т1 (1)11 ) таких, что Т1„... ТыТ1за1 — — ~~а1 ~) е1 (причем значения углов 1н1ю й = 2,..., п определяются леммами 2, 3). Умножим систему Ах = й на Т1„... Т13Т13 слева, получим где ()а1)( А1) =Т1в ТгзТгА = О а,д ... а„„ (1) (1) Далее процесс применяется к подматрице (а; ); (1) Пусть сделаны й — 1, й = 1,...,п — 1 шагов зтого процесса, т.е. система преобразована к виду (2) где А1" ')= П ЦТ А, У~'-' = П ПТ,:,, (3) С1н сз ))а~ )(! сь 1,3 (3-1) аьз А1~ ') = (4) К.Ю.Богачев ~!а1~~ с13 с1з )(а, (! сзз ()а1 !) С1,3 1 С1Ь СЗ,3 1 С33 СЗ,Ь-1 Сзь Точные методы решения линейных систем ~12. МКТОД ИПЩКНИй 47 И-1 (здесь П означает, что сомножители берутся в порядке а,...,1+ 1).

Обозначим ~й — 1) ( (й — 1) (й — 1))1 (6) — первый столбец подматрицы (а1 ); й „. Согласно лемме 3 существуют и — 1с (й — 1) матриц Тй,й+1 Тй,й ~-1(ай,й+1) ~ Тй,й+2 Тй,й+2(Фй,й+2) ~ ° ° ° ~ Тй,о Тйв(1Рйв) ) таких, что Тй, Тй,й+2Тй,й.11а, ' = ~)а, ' ~(е„" "+', (6) (значениЯ Углов 1Рйз, ) = 1+1,...,и опРеДелЯютсЯ леммами 2, 3), зДесь е, (т) (1,0,...,О)' б К"". Умножим системУ (2) на Тй„...Тй1, 12Тйй.г1 слева, полУчим А1~)х = Ь1~), где 1 Ьй1 А'"' = П ТйзА'" " = П П Т14А ~'"' = П Ти~" ' = П П Т1А (7) 1й — 2) !)а1 !) Сй 1й Сй 1,й11 ...

Сй 1„ (й-1) ()а1 () сй,й.11 ... сй „ (й) (й) ай„1й+1 ... ай„1„ 1й) (й) ав й+1 ... а„„ Отметим, что в (7) каждая из и — lс матриц элементарных вращений Тй, такова, что ) ) Й и потому в (7) она умножается только на подматрицу (сч );, й (й 1') матрицы А1й ') размера и — й+ 1 (остальная часть А1й ') в преобразовании (7) не участвует). После и — 1 шагов этого процесса (т.е.

перехода от матриц и правых частей (3), (4) к (7), (8)) система примет вид (9) Вх=у, где 1 Ьй! в — 1 Н1 Л = А("-Ц = П П ТЗА, (10) 1=в †11 1=в †11 К.Ю.Богачев Точные методы решения линейных систем ()И1)! С12 Сгз ° .. С1 й 1 )(а1 () сзз .. сз,й 1 (1) //а, // ... сз,й-1 Свй С1,й Г1 ... С1„ Сзй Сз,й+1 ... С2„ СЗй СЗ,й Г1 ... СЗв ~12. МКТОД БРАЩКНИИ 48 ~)а1 ~~ С,2 С1З .. С,,„З ~~а1Ц ~~ СЗЗ ... С2, 'З01 (! ...

СЗя 2 12) С1,„1 С1„ С2,„1 С2„ СЗ,н — 1 СЗн (и-3) ~!а ~~ с-, — с-,. ()а, !) с„1 „ ай" ') 3 12.3. Оценка количества арифметических операций в методе вращений Оценим трудоемкость й-го шага алгоритма, а затем просуммируем полученные оценки по всем Й = 1,..., и — 1. 1. На вычисление и — й матриц Ть 1,.1.1,..., Ть„, участвующих в (6), согласно лемме 2 требуется 4(п — Й) мультипликативных, (и — Й) адцитивных и в — Й операций извлечения корня. 2.

На вычисление компонент й,...,п й-го столбца матрицы А~"), равных компонентам вектора ~)а~ ~) ~) е~ + ) требуется (для вычисления длины векто1й — 1) ~в-ь-~-1) ра (5)) п — 1+1 операций умножения, и — Й операций сложения и одна операция извлечения корня. Столбец й вычисляется именно этим способом (а не по общим формулам (7)) для сокра1цения количества арифметических операций и уменьшения вычислительной погре1пности. 3.

Поскольку в формуле (7) каждая из п — й матриц элементарных вращений умножается на подматрипу (а1 ); ь „1 ь.1.1 „матрицы А размера (и— (й — 1) ~Ь вЂ” 1) 1+1) х (и — й) (й-й столбец матрицы А1"~ уже вычислен в пункте 2), то согласно лемме 5 на это требуется (и — й)4(п — й) = 4(п — й)2 умножений и (и — й)2(п — й) = 2(п — й)2 сложений. 4. На вычисление новой правой части по формуле (7) согласно лемме 4 требуется 4(п — й) умножений и (п — й) сложений. Итак, на й-ом шаге алгоритма требуется выполнить 4(п — й) + (и — й + 1) + 4(п — й)2 + 4(п — й) = 4(в — й)2 + 9(п — й) + 1 мультипликативных операций, (и — й) + (и — й) + 2(в — й) 2 + (и — й) = 2(п — й)2+ 3(в — й) аддитивных операций и и — Й + 1 операций извлечения корня.

Следовательно, всего для проведения алгоритма требуется выполнить и — 1 (4(г1 — й)2+ 9(п — й) + 1) = 4п(п — 1)(2п — 1)/6+ 9п(и — 1)/2+ п — 1 Ь=1 К.Ю.Богачев Точные методы решения линейных систем (напомним, определения векторов а1, Й = 1,..., л — 1 даются в (5), где счи(ь — 1) таем, что а1 = а1). (а) Система (9) с верхней треугольной матрицей В реп1ается обратным ходом метода Гаусса. ~12.

МЕТОД ИПЩЕНИИ 3+О( и) ( ) 3 мультипликативных операций, ~"~ь:,'(2(п — й) +З(п — й)) = ~~из+ 0(п ) (и — + оо) адцитивных операций и ~":1 (и — я + 1) = 0(пг) (и -+ оо) операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления). На решение системы (9) с верхней треугольной матрицей В обратным ходом метода Гаусса требуется О(нг) (и — э сс) арифметических операций. Таким образом, на решение линейной системы методом вращений требуется 1~из + 0(н2) (и -+ ос) мультипликативных операций (что в 4 раза больше, чем в методе Гаусса), и ~~из+ 0(на) (и — э со) аддитивных операций (что в 2 раза больше, чем в методе Гаусса). Теорема 1 (О ЯН-разложении).

Всякая невырожденнол вещественная матрица А может быть предстпавлена в виде А = ЯВ, где матрица Я ортогоналънол, а матрица  — верхняя треугольная с положительными элементами на главной диагонали. Это разложение единственно. Доказательство. Проведем для матрицы А алгоритм метода вращений, осуществимый для всякой невырожденной матрицы. Обозначим в (10) Я 1 И1 П П Т; . Как произведение ортогональных матриц, матрица Я ортогональна. с=и †1з Тогда (10) имеет вид В = ЯА, откуда А = (Ч) 'Н = ЯВ, где Я = (Я)' = ф) Если а~"„О ) О, то матрица В, имеющая вид (11), удовлетворяет условиям теоремы.

Если а~"„О < О, то положим Р = с11аи(1,..., 1, з1йп(а~"„О)) . Матрица Р ортогональна и Рг = Т. Поэтому А = ЩР)(РН), где Я:= ЯР и Н:= РВ удовлетворяют условиям теоремы. Предположим, что возможно два различных разложения А = ЯВ и А = Ч'В', удовлетворяющих условиям теоремы. Тогда ЯВ = Я'В' и ®') 'Я = В 'В'.

В левой части последнего равенства стоит ортогональная матрица, а в правой — верхняя треугольная. Пересечение группы ортогональных матриц и группы верхних треугольных матриц состоит из матриц вида Р Йац(ды...,д„), где 4 е ( — 1,1), 1 = 1,...,н (проверить самостоятельно). Поскольку диагональные элементы матрицы Н 'В' равны произведениям диагональных элементов матриц В и В', то они положительны. Следовательно В 1Н' = 1, т.е. Н = Н'. Также (Я') 'Я = Т, т.е. Я = Я'.

Полученное противоречие доказывает теорему. Замечание 3. ОВ-разложение матрицы А может быть использовано, например, для тех же целей, что и ИУ-разложение. Именно, пусть стоит задача решить серию систем вида Ах = 6;, 1 = 1,...,гп с одной и той же матрицей А и разными правыми частями б,. Построим ЯВ-разложение матрицы А (которое, в отличие от ИУ-разложения, существует для всякой невырожденной матрицы). Для ортогональной матрицы Я легко находится обратная ф О = Я'. Поэтому К.Ю.Богачев Точные методы решения линейных систем ~12. МКТОД ИЧЩЕНИИ 50 х находятся как решения системы В х, = Я' Ь с верхней треугольной матрицей В, например, обратным ходом метода Гаусса.

Замечание 4. ЯВ-разложение матрицы А используется в ЯВ-алгоритме нахождения собственных значений матрицы А. З 12.4. Построение ЯВ-разложения методом вращений Построение ЯЛ-разложения. Хранение матриц Я и Л в памяти. Пусть стоит задача построить ЯВ-разложение для матрицы А. Будем действовать как в теореме 1. Проведем для матрицы А метод вращений и получим в результате матрипу В из (11). При этом матрица Я равна (см. доказательство теоремы 1) 1 ю -~- 1 Ю=( П ПТу)'= П П Т, (12) $=1 1=Н1 Возможны два способа хранения матриц Я и В в памяти. 1. Матрица В хранится на месте верхнего треугольника матрицы А и получается из нее последовательным применением элементарных вращений 1см. выше алгоритм метода вращений). Для хранения матрицы Я выделяется отдельная матрица Я, которая равна единичной перед первым шагом алгоритма. На шаге ь~-1 Й, Й = 1,..., п — 1 эта матрица умножается справа на матрипу Ц Ть; .

К.Ю.Богачев Точные методы решения линейных систем (см. (7), (12)). Произведение матрицы элементарного вращения на матрипу вычисляется по алгоритму из леммы 5 с затратой 4п умножений и 2и сложений. Следовательно, произведение п(п — 1)/2 матриц вращения в (12) может быть вычислено за 2п2(п — 1) = 2па + 0(п~) 1п -+ оо) умножений и п~(п — 1) = па+0(ит) (и -э оо) сложений.

2. Как и в первом способе, матрица Л хранится на месте верхнего треугольника матрицы А. Для хранения же матрицы Ч' отдельная память не выделяется. Заметим, что на |лаге Й, Й = 1,..., п — 1 мы использовали п — Й элементарных вращений Ть ь„и..., Ть„и каждая из этих матриц целиком определяется единственным параметром — значением угла д,у: Ть — — Ть (,~рьу), 1' = й + 1,..., п. При этом после преобразования (6), (7), т.е.