Богачев - Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений (947493), страница 12
Текст из файла (страница 12)
Лемма 11. Произведение матрицы отражения Цх) е М„на матрицу размера и х ш может быть вычислено за 2пш+ О(ш) (п,ш -+ со) сложений и столько же умножений (точнее,за (2п+ 1)ш умножение и (2п — 1)т сложение). Доказательство. Пусть п х ш матрица В = Цх)А есть произведение матрицы отражения У(х) Е М„на п х т матрицу А. Запишем матрицы А = (а;-) и В = (Ь;,) через их столбцы: А = [а~'~,..., а~"0], В = [Ьр~,..., Ь~ ~], где а~~~ = (а1г,..., а,ц,)', Ы"~ = (Ь1г,..., Ьяг)', й = 1,..., ш.
Согласно определению произведения матриц В = Цх)А = [У(х)а~0,...,Цх)а("1], т.е. Ь~") = У(х)а(г~, Ь = 1,...,ш. Таким образом, для вычисления матрицы В = У(х)А надо вычислить ш произведений У(х)а~~~ матрицы У(х) на вектора а~~~, Ь = 1,...,ш. Доказываемое утверждение теперь вытекает из леммы 10. К.Ю.Богачев Точные методы решения линейных систем )з13. МЕТОД ОТРАЖЕНИЙ 55 З 13.2. Алгоритм метода отражений Пусть требуется решить линейную систему Ах = Ь, А Е М„вида (4.1). Обозначим а1 — — (ам,..., а„1)' — первый столбец матрицы А. Согласно лемме 9 существует вектор хр) Е С", равный а1 — !! а1!! е1 !!а1 — !!а1 !/е1 !! АО)х = ЬО), где !!а1!! с12 ...
с1„ (1) (1) О а22 ... 02в АО) = Г(х1'))А = ЬО) = и(хр))Ь. 11) 11) аз2 а в Далее процесс применяется к подматрице (а; );, 2 (1) Пусть сделаны й — 1, й = 1,..., п шагов этого процесса, т.е. система преобразована к виду где 1 А~й-')= П ЦА, Ь1й — ) (2) !!а1 !! сгз сгз с1,й-1 !!а1 !! сзз сз,й 1 М !!а1 !! сз,й — 1 С1й сгв сзй сз л 1й — 2) !! (й-1) ай„ А1й ') = (й — 1) айч (й-1) а„„ а1й ') (11, О О й) (хй)) здесь Т; 1 Е М; 1 — единичная матрицаразмера (г — 1) х (г — 1), Б(хй)) Е М„,1, — матрица отражения размера (н — з+ 1) х (и — г'+ 1), построенная по вектору Π— 1) Π— 1) ~в — 1+1) -!!" !!" С--" Π— Ц !! Π— 1) !! (и — 1+1) !! К.Ю.Богачев Точные методы решения линейных систем такой, что Г(х11))а1 —— !/а1!!е1, где е1 —— (1, О,..., О) Е С", Н1 — — ЕУ(х11)) — матрица отражения.
Умножим систему Ах = Ь на Б1(х11)) слева, получим ()13. МЕТОД ОТРАЖЕНИЙ (' ') =( (' ') ... (" '))' С"-"" () а1 = (а~~,...,ап~ ) Š— первый столбец подматрицы (а; );, 1 „. Согласно лемме 9 существует ма(й-1) трица отражения ~Я-1) е (1с-1) е (в-~+1) Г(х1~)) = Т вЂ” 2х(~)(х(~))*, х(ь) = ~ ' ' ' Е С" ~+', (5) — — — !) (ь-1)!) (~-ь+1)() такая,что ,г(,(~)),( — ) ~~,( — ) ~~,( — - ) (б) Положим 0 У(х1,) Покажем, что матрица 14 является унитарной, т.е. Гь* = С'„'. По правилам перемножения блочных матриц 0 У*(хь) 0 Г(хь) (8) Ы)И 1 Ь~.
Ь 2( ) Тя .~~ (9) (Т,', О ') (~;, О 0 У (хь) ) 1, 0 Т„ь11 что и означает У* = 1У„", т.е. унитарность матрицы Уь. Умножим систему (1) на 14 слева, получим А(")х = Ь("), где 1 1 А(') = и,А("-1) = ПЦА, Ь(") =и,Ь('-') = ПН,Ь, (10) ()И1)! с12 сгз ... С1 ь 1 )(а1 () сзз .. сз,ь 1 (1) //а, !/ ... сз,ь-1 сц, сзь А(") = СЬ 1,Ь.11 ... СЬ 1,„ ()а1 () сь,ь.1.1 ... сь,„ (ь — 1) (ь) (й) а„„1 в+1 ... аЬ+1 „ (й) а„Ь+1 К.Ю.Богачев Точные методы ретения линейных систем где е~1) = (1, О,..., 0) Е С Обозначим С1,Ь~1 ... С1„ С2,~+1 ...
С2„ СЗ,Ь+1 СЗ Ц13. МЕТОД ОТРАЖЕНИЙ зй = ~ ~„ »а й (12) )) (' "))=И»'ч»+а (13) затем — вектор , (й) ( (й-1) Ц (~-0Ц (й-1) (й-1))» С -й»-1 (14) и его норма (15) Теперь можно вычислить искомый вектор х(") х( ):= х( )/Цх( )Ц, т.е. х(:= х, /Цх( )Ц, ) = 1,...,п — и+1. (16) После и шагов этого процесса (т.е.
перехода от матриц и правых частей (2), (3) к (10), (11)) система примет вид (17) Их=у, где у=5(") = ПГ(;Ь, (18) Ца» Ц с»2 с»з ... с»,„2 Цо» Ц сзз сзл — г (1) Ца» Ц сзт-2 (2) С1„1 С1„ С2в 1 С2в СЗ „1 СЗв Ца(" ) Ц Св 2в 1 Ца» Ц с„,„ Цад( ) Ц (напомним, определения векторов а», Й = 1, (й — 1) что а1 = а»). (о) Система (17) с верхней треугольной матрицей метода Гаусса. , и даются в (4), где считаем, В рЕп»аЕтСя Обратным хОдОм К.Ю.Богачев Точные методы решения линейных систем Отметим, что при умножении матрицы С1й вида (5) на матрипу А(й ') вида (3) она умножается только на подматрицу (а», ); й „матрицы А размера "(й 1) (й — 1) и — й+ 1 (остальная часть А(" ') в преобразовании (10) не участвует). Вычисления по формулам (5) осуществляются следующим образом: вначале вычисляются числа '313.
МЕТОД ОТРАЖЕНИЙ 58 3 13.3. Оценка количества арифметических операций в методе отражений Оценим трудоемкость к-го шага алгоритма, а затем просуммируем полученные оценки по всем Й = 1,..., и. 1. На вычисление матрицы 7У(хь) по формулам (5) требуется а) и — й умножений и п — й — 1 сложений для вычисления нь в (12); б) одно умножение, одно сложение и одна операция извлечения корня для вычисления ~~а) ~~~ в (13); в) одно вычитание для построения вектора х~ь~ в (14); г) одно умножение, одно сложение и одна операция извлечения корня для вычисления //х~"~// в (15); д) и — Й+ 1 делений для построения вектора х~"~ в (16). Всего для построения матрицы Б"(хь) требуется (п — Й)+1+1+ (и — 1+1) = 2(п — й) + 3 мультипликативных, (и — й — 1) + 1 + 1 + 1 = п — й + 2 аддитивных операций и 1 + 1 = 2 операции извлечения корня.
2. Компоненты й,...,п й-го столбца матрицы А~"~, равные компонентам (ь — 0 (в — й-~ц вектора ~~а~ ~~ с~ +, уже вычислены в (13). Столбец й вычисляется не по общим формулам (10) для сокращения количества арифметических операций и уменьшения вычислительной погрешности. 3. Поскольку в формуле (10) матрица Уь вида (5) умножается на матрицу А~ь 0 вида (3), то при вычислениях по (10) надо умножить матрипу отражения Цх~"~) е М„ь~, наподматрипу (а~~~ 0); ь „, ь„„матрицы А~" 0 размера (п — 1+1) х(п — й) (й-й столбец матрицы А~ь~ уже вычислен в пункте 2). Согласно лемме 11 на зто требуется 2(п — Зс)(п — К+1)+ 0(п — И) = 2(п — й)~+0(п — й) (п -+ со) умножений и столько же сложений. 4.
На вычисление новой правой части по формуле (10) согласно лемме 10 требуется 2(п — и + 1) + 0(1) (и — ~ оо) умножений и столько же сложений. Итак, на й-ом шаге алгоритма требуется выполнить 2(п — й) + 3+ 2(п — й)2+ 0(п — й)+2(п — 1+1)+0(1) = 2(п — й) +0(п — й) (и -+ ос) мультипликативных операций, и — И+2+2(п — 1с) +0(п — 1с)+2(п — 1с+1)+0(1) = 2(п — й) +0(п — й) (и — ) оо) аддитивных операций и 2 операции извлечения корня. Следовательно, всего для проведения алгоритма требуется выполнить ~ (2(п — Й) + 0(п — Й)) = 2п(п — 1) (2п — 1)/6 + 0(пя) = — и + 0(п~) (п -+ сс) А=1 3 мультипликативных и столько же аддитивных операций, и ~ ~,(2) = 2п операций извлечения корня (которые по трудоемкости по порядку можно сравнить с операциями деления).
На решение системы (17) с верхней треугольной матрицей В обратным ходом метода Гаусса требуется 0(п~) (и -+ оо) арифметических операций. Таким образом, на решение линейной системы методом отражений требуется 5п~ + 0(п2) (п — > оо) мультипликативных и столько же аддитивных операций (что в 2 раза болыпе, чем в методе Гаусса). К.Ю.Богачев Точные методы решения линейных систем ~13. МЕТОД ОТРАЖЕНИЙ Теорема 1 (О ЯВ-разложении). Всякая невырожденная матрица А М„может бъппь представлена в виде А = Я В, гдг матприца Я вЂ” унитарнол, а матрица В вгрянял треугольнол с вещественными положительными элгмгнтпами на главной диагонали. Это разложение единстпвенно.
Доказательство проходит аналогично доказательству теоремы 12.1. Проведем для матрицы А алгоритм метода отражений, осуществимый для всякой 1 невырожденной матрицы. Обозначим в (18) Я = П Ц. Как произведение унитарных матриц, матрица Я унитарна. Тогда (5) имеет вид В = ЯА, откуда А = ®) 'В = ЯВ, где Я = ©' = (Я) '. Здесь матрица Я унитарна, а матрица В имеет вид (19) и потому удовлетворяет условиям теоремы.
Предположим, что возможно два различных разложения А = ЯВ и А = Ч'В', удовлетворяющих условиям теоремы. Тогда ЯВ = Я'В' и ®') 'Я = В 'В'. В левой части последнего равенства стоит унитарная матрица, а в правой — верхняя треугольная. Пересечение группы унитарных матриц и группы верхних треугольных матриц состоит из матриц вида В = Йа8(дм..., а„), где с~, = е'"~, 1' = 1,...,и (проверить самостоятельно). Поскольку диагональные элементы матрицы В В' равны произведениям диагональных элементов матриц В ' и В', то они вещественны и положительны. Следовательно В т В' = 1, т.е. В = В'. Полученное противоречие доказывает теорему. Замечание 1. Справедливы замечания 12.3 и 12.4 о применении ЯВ- разложения.
Э 13.4. Построение ЯВ-разложения методом отражений Построение ЯВ-разложения. Хранение матриц Я и В в памяти. Пусть стоит задача построить ЯВ-разложение для матрицы А. Будем действовать как в теореме 1. Проведем для матрицы А метод отражений и получим в результате матрицу В из (19). При этом матрица Я равна (см. доказательство теоремы 1) (20) Возможны два способа хранения матриц Я и В в памяти.
1. Матрица В хранится на месте верхнего треугольника матрицы А и получается из нее последовательным применением матриц отражения (см. выше алгоритм метода отражений). Для хранения матрицы Я выделяется отдельная матрица Я, которая равна единичной перед первым шагом алгоритма. На шаге Й, Й = 1,...,и эта матрица умножается справа на матрицу Гь .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
