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

Обозначим А = А+ Е, Ь = Ь+ е. Таким образом, точное решение х удовлетворяет системе Ах = Ь, а приближенное решение х удовлетворяет системе (А+ Е)х = Ь+ е . Пусть ~(. ~) — произвольная матричная норма, согласованная с векторной нормой ~! . ~). Будем считать, что ошибка, вносимая в матрицу при проведении 1 алгоритма, не очень велика: ~(Е~~ <, . По теореме 2.2 отс1ода следует, что матрица А+ Е обратима и (А+ Е) ' = 2. ( — 1)"(А 'Е)ьА ' . Вычислим а=о погрегпность х — х: Р. ОШИБКИ В РЕШЕНИЯХ ЛИНКИНЫХ СИСТКМ Часто, чтобы оценить точность полученного приближенного решения х, вычисляют вектор невязки г = 6 — А х .

Оценим относительную погрешность решения через невязку г. х — х=А «б — х=А «(6 — Ах)=А «г, ~И '~! И ~, !1~ '~1~! 11= (А) Ы ~Щ ~~Щ ~Щ ~~~«!! Пример. Рассмотрим линейную систему А = < (1 «« х = ~ ) . Рассмотрим приближенное решение х ~о) о вектор невязки г = ««г, вектор о«пибки х — х Ее точное решение < — «/г '1 ьг) . Поэтому ~~г~~ величина невязки = 0(г~«~) -+ О (в -+ О),: ~й !)х — х!) величина ошибки = 0(в '«~) + оо (а — ~ О); )(х() а) относительная б) относительная Свойства числа обусловленности 1. к(А) > 1.

2. к(А) = к(А ') . 3. к(АВ) < к(А)к(В) . Первые три свойства следуют непосредственно из определения числа обусловленности и основных свойств матричных норм. 4. Если А = А*, то по отношению к спектральной норме к(А) = л„, (А)', ~ппп( ), где Л, (А) и Л ы(А) соответственно максимальное и минимальное по модулю собственные значения матрицы А. Доказательство. В силу замечания 1.1 (см. лемму 1.4) для самосопряженных маврин //А!/г — р(А) = /Л (А)!, !/А «!/г — — р(А «) = !Л „„(А «)/ /Л ы(А)/. Поэтому к(А) = ЦА!/ /!А '// = л (А) пип( ) К.И.Богачев Точные методы решения линейных систем )(х — х!) М Здесь называется относительной погрешностью в решении х, )(е)! называется относительной погрешностью в матрице А, называется относительной погрешносгпью в правой части 6.

Ц4. МЕТОД ГАУССА 5. Для всякой матрицы А Е М„число обусловленности относительно любой Л „(А) матричной нормы к(А) > Лппп(А) оказательство вытекает из леммы 1.4: А > А = Л А А 'Ц > Ц Ц р() ~-()~ Ц р(А ') = !Л „(А ') / = /Л ы(А) !; поэтому к(А) = ЦАЦ ЦА ' Ц > Л ы(А) 6. Для всякой матрицы А Е М„и любых унитарных (ортогональных) матриц Б; Ъ' е М„число обусловленности относительно спектральной нормы к(А) = к(ГгАЪ') . Это свойство непосредственно следует из леммы 1.5. 7. Для всякой невырожденной матрицы А Е М„ ЦАЦ ЦА — ВЦ В вЂ” вырожденная ~ 4.

МЕТОД ГАУССА Ц 4.1. Алгоритм метода Гаусса Пусть требуется решить линейную систему Ах = 6, А Е М„ аих1 + аггхг + .. + ашх„= бг йг1х1 + Яггхг + ° ° ° + агах~ = нг нв1х1 + нлгхг + .. + Й~„х„= б~ Метод Гаусса состоит в том, что элементарными преобразованиями над строками матрицы она приводится к треугольному виду с главной диагональю, состоящей из единичных элементов (прямой ход метода Гаусса); полученная система с треугольной матрицей решается в явном виде (обратный ход метода Гаусса). Предположим, что аи ф О. Поделив первое уравнение системы (1) на ап, перепишем его в виде (2) х1+ с1гхг +... + с1„х„= уь К.Ю.Богачев Точные методы решения линейных систем Доказательство.

Покажем, что для всякой вырожденной матрицы В Е М„ справедливо неравенство ЦА — ВЦ > 1/ЦА 'Ц. Предположим, что это не так, т.е. существует вырожденная матрица В, такая, что для матрицы С = А — В выполнено ЦСЦ с 1/ЦА ' Ц . Тогда по теореме 2 2 матрица А — С = А — (А — В) = В обратима, что противоречит вырожденности В. Таким образом, установлено, что для всякой вырожденной матрицы В ЦА ' Ц > 1/ЦА — ВЦ.

Следовательно, к(А) = ЦАЦ ЦА 'Ц > ЦАЦ/ЦА — ВЦ для всякой вырожденной В е М„. Поскольку левая часть этого неравенства не зависит от В, то из него вытекает требуемое соотношение. ~4. МЕТОД ГАУССА О~2 Х2 + + ( ) (1) „ (1) где а1 = а; — с1уа11, (г; = (1; — У1ан, 2,) = 2,...,п. Далее этот процесс применяется к подматрице А = (а ); 2 „Е М„1. (О (1) Пусть сделаны Й вЂ” 1, Й = 1,...,и шагов этого процесса, т.е. система (1) преобразована к виду х1+с1гхг+... +с1й 1хй 1+ с1йхй +...+ сг,х, = У1 Хг + ..

+ Сг,й 1Хй 1+ СгйХй + ... + СЬ,Хв = Уг + сй 1,йхй + ... + сй 1,„х„= уй 1 (й-1) (й-1) (й-1) ий й хй + ... + ай „х„= бй (4) а( 1, )хй + ... + а~~„ОХ„= 6( Предположим, что айй ~ О. Поделив й-е уравнение системы (4) на айй (й — 1) (й — 1) перепишем его в виде (б) хй + сй,й11хй„1 +... + сй„х„= уй, где (й-1) "йу сй, = айй ( (й — 1) й Уй= (й 1) айй )' = 1+1,...,п, Умножим уравнение (5) на а,й и вычтем его из 2'-го уравнения системы (4) (й-1) (г = Й+ 1,..., п). В результате система (4) примет вид х1 +с12хг+...

+с1 й 1хй 1+ с1 йхй + с1 й 11хй 11 +...+ с1 х хг +... +сгй 1хй 1+ сгйхй + сгй,1хй.11 + + сг х У1 У2 +ей йхй+сй 1й11хй11+...+ей 1„х„ хй + ейй-11хй-11 +...+ сй„х„ (й)' (й)' ай„11 й 11Хй.11+... + ай, 1 „Х„ (7) = Уй (й) =Ьй11 а„й,1хй.11 +...+ а„„х„= 6„ (й) (й) р) К.Ю.Богачев Точные методы решения линейных систем где с„= а1,/а11, )' = 2,...,и, У1 — — Ь1(а11. Умножим уравнение (2) на ап и вычтем его из 2'-го уравнения системы (1) (1 = 2,..., п). В результате система (1) примет вид х1 + с12хг + ...

+ с„,х„= у1 (1) (1) (1) 022 Х2 + ° ° ° + Иг~х = 62 34. МЕТОД ГАУССА где а~"~ = а(, ~ — а~ь ~сь, 6( ~ = 6( ~ — а~~ ~дь, г, 1 = й + 1,...,п. (8) Выражения (6), (8) являются формулами перехода от системы (4) к системе (7). Если обозначить а," = а;., й; = 6;, г, 1 = 1,..., и, то переход от системы (1) к системе (3) будет осуществляться по тем же формулам при й = 1. После проведения вычислений по формулам (6), (8) при й = 1,..., п (которые составляют прямой ход метода Гаусса) система (1) примет вид х1 + сьзхз + ...

+ с1х„1 + с1х„= д1 хз + ... + сах„1 + с1нхп = уг (9) + с„~,„х„= у„1 х„1 Решение системы (9) средственно (методом хп ~ хн — 1» х1 ) с треугольной матрицей может быть найдено непопоследовательного исключения неизвестных в порядке х„=у„, х;=д; — ~~, с;,х,, г=п — 1,...,1. у=н1 (10) Вычисления по формулам (10) составляют обратный ход метода Гаусса.

3 4.2. Оценка количества арифметических операций в методе Гаусса К.Ю.Богачев Точные методы решения линейных систем Здесь и далее при оценке количества арифметических операций мы будем отдельно находить количество аддитивных операций (сложений и вычитаний) и количество мультипликативных операций (умножений и делений).

Для упрощения выкладок мы будем находить только главный член асимптотики количества операций при и -+ оо . 1. На вычисление сь при 1' = й + 1,...,п, й = 1,...,п по формулам (6) требуется ~,",,(п — й) = ~,":„'з = п(п — 1)/2 = 0(п ) (и — + со) операций деления. 2. На вычисление а( ~ при г, 1' = й + 1,..., п, й = 1,..., и по формулам (8) требуется Я,(п — й)2 = ~,":„' Р = (п — 1)п(2п — 1)/6 = п~/3+ О(п ) (п — э оо) операций умножения и столько же операций вычитания.

Итак, на вычисление коэффициентов сь~, 1 = Й+ 1,...,п, Й = 1,...,п системы (9) требуется 0(п~) + пэ/3+ 0(п2) = пз/3+ 0(па) (и -+ оо) мультипликативных операций и столько же аддитивных операций. 3. На вычисление уь при й = 1,..., и по формулам (6) требуется и операций деления. 4. На вычисление 6; при ю' = й+ 1,..., и, й = 1,..., и по формулам (8) тре(ь) буется Я,(п — й) = ~,',":„' г = п(п — 1)/2 = 0(п ) (и + со) операций умножения и столько же операций вычитания. 34.

МЕТОД ГАУССА 3 4.3. Представление метода Гаусса в виде последовательности элементарных преобразований Преобразование системы, задаваемое формулами (6), эквивалентно умножению матрицы системы слева на матрицу Рь = Йа8 ( 1,..., 1, (ац, ), 1,..., 1 1, (где Йа8 ( 4п..., д„~ означает диагональную матрицу с элементами Ы1,..., д„на главной диагонали) . Преобразование системы, задаваемое формулами (8), эквивалентно умножению матрицы системы слева на матрипу (не обозначенные элементы матрицы Ьь равны нулю).

Следовательно, прямой ход метода Гаусса эквивалентен умножению матрицы системы (1) последовательно на матрипы Ь|Рь, Й = 1,..., п: (П) 1„,.Р„... 7 Р1 .Ах = й„Р„..... Й,Р1 6. причем матрица сГ = Л„Р„... Л,Р1 А есть матрица системы (9), т.е.

является верхней треугольной с единицами на главной диагонали. Обозначим через ЬТ(и) группу невырожденных верхних треугольных матриц. Тогда для всех Й = 1,...,п Рь, Йь Е 1Т(п) и потому матрица Ь = Ь„Р„... Ь!Р1 Е 1Т(п). К.Ю.Богачев Точные методы решения линейных систем Итак, на вычисление правых частей уь, й = 1,...,п системы (9) требуется О(п2) (п -+ оо) мультипликативных операций и столько же аддитивных операций. Таким образом, прямой ход метода Гаусса требует из/3 + 0(ия) + 0(п ) = и~/3+ 0(п~) (и — + оо) мультипликативных операций и столько же аддитивных операций. 5.

На вычисление решения по формулам (10) (т.е. на проведение обратного хода метода Гаусса) требуется ~,":1'(и — г) = ),":,' г = и(и — 1)/2 = 0(п ) (и — ) оо) операций умножения и столько же операций вычитания. Следовательно, метод Гаусса требует п~/3+0(п~)+0(п2) = п~/3+0(п2) (и -+ оо) мультипликативных операций и столько же аддитивных операций. Всего: (2/3) пз + 0(пя) (и -+ оо) арифметических операций. 34.