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

Доказательство. Проверим выполнение свойств 1)-4) из определения матричной нормы. 1) ))А)( = и!ах !)Ах() > 0; ~И=! 2) !)ЛА!) = !пах ()ЛАх(! = и!ах )Л! ()Ах!) = )Л! шах ))Ах)) = )Л( )(А(! . 3) !)А+ В)( = !пах ()(А+ В) х)( = шах )(Ах+ Вх() < шах(!)Ах()+ )(Вх(0 < (И=! ~И=! (И=! гоах ()Ах!) + шах ()Вх!) = !)А)(+ !)В() . ~И=! ~И=! )(АВхо ))АВх(! !)Вх)( < )(Ау)( !)Вх(! < ж~о !)х)( хФО ()Вх!) ))х)( иапо ()у(! и~а !)х(! ~)А)~ ~)В(~ .

Проверим вь!полнение дополнительных свойств этой нормы. К.Ю.Богачев Точные методы решения линейных систем ~1. МАТРИЧНЫЕ НОРМЫ ~)А~! = шах . Следовательно, для всех х Е С" < ~~А~), т.е. ))Ах!) ()Ах)( *Фо !)х)( ~~х~~ ()Ах)( < ()А)( !)х(! . (Щ = шах ()1 х!) = »пах )(х!) = 1 . ((х))=1 ((ж))=1 Определение. Максимальной столбцовой нормой называется )/А!)» — — »пах Ч~, )а; (. — — »=1 Лемма 1. Норма ~)А~(» подчинена векторной норме ~~х~(» — — ~ ~х;~ »=1 Доказательство. Надо проверить, что »пах ~ ~а;,~ = шах ~~Ах~)» . Запи»<»<в; — » о~о»=» шем матрицу через ее столбцы: А = (а»,..., а„~, где а, = (а»»,..., а„у)' .

Тогда ()А)(» = »пах !)а, !)» . С другой стороны, для х = (х»,..., х„)' Е С" »<»<~ ()Ах!)» — — )! ~ хуан < ~ )х ) !)а~!)» < ~ )х~! шах )(ао)(» — — )(х!)» )(А()». Следовательно, »пах )(Ах()» — — »пах < )(А()» . )(Ах!)» ' ощ»=» ~Фо )Щ Если максимум п»ах !)а;)(» — — ()А)(» достигается при» = ао, то, выбрав х »<»<в равным е,, — стандартному координатному орту, получаем !И»=» шах ))Ах)(» ) )(Ае;,)(» — — )(а;,)( = !)А()». Отсюда вытекает требуемое равенство шах ~ (а,"! = шах !)Ах)(» »<~<<о»=» !И~»=» Определение. Максимальной строчной нормой называется !)А)/ = »пах Ч~» (а;,).

Лемма 2. Норма (/А)/, подчинена векторной норме )/х()„= »пах (х;! . »=»,...,и Задача. Доказать самостоятельно. Доказательство. Имеем для всех х е С" ()Ах)( = шах)~ "а;,хд~ < »пах ~~ '~~а;,~ (х ! < шах 1 '~а»~~ )(х(! = !)А() !)х!) — ' —" у=» « 3 — — з=» Следовательно, »пах !)Ах)( < !)А!) !И« =» К.Ю.Богачев Точные методы ретения линейных систем ~1. МАТРИЧНЫЕ НОРМЫ 1О Пусть максимум »пах ~ (а» ! = ОА() достигается при 1 = го. ()АО »<1<ну — 1 1.

~а»ог ~ . Рассмотрим вектор у = (у»,..., у„)' с компонентами =( если а»оэ ~ О, если а;,„= О. Тогда ~)у~) = 1, у,а;, = ~а»ог~, 1 = 1,...,и. Поэтому п»ах !)Ах)/ > )!Ау)/ = шах(~', а;,уг~ > !/х/Ь„=» 1<1<ч 1 — 1 ) ~ а;, уг~ = ) х, ~а;, ~О' = ~ )а», ( = (/А!) ()А!)г = шах1ъ~Л: Л собственное значение матрицы А*А). (здесь А* означает матрипу, сопряженную к матрице А: А* = (А)' в комплексном случае и транспонированную матрипу А' в вещественном случае). Отметим, что это определение корректно, т.е. указанные квадратные корни всегда существуют. Действительно, для всякого собственного значения Л матрицы А'А и соответствующего ему собственного вектора х из равенства А*Ах = Л х вытекает (А"Ах, х) = Л(х, х), откуда Л =, и потому Л е К, Л > О (здесь ~~Ах~)г ()х Йг (, ) означает евклидово скалярное произведение в С" ). Лемма 3.

Норма ОА~~г подчинена евклидовой векторной норме ~~хОг ~г)1/2 Доказательство. Рассмотрим п1ах ~)Ах~~2 — — п»ах (Ах, Ах)'1~ = шах (А'Ах,х)1»2, ~И =1 ~~х1! =1 ~ФЬ=» Обозначим В = А*А. Матрица В самосопряжена (симметрична в вещественном случае): В* = (А*А)" = А*(А*)' = А*А = В. Как показывается в курсе линейной алгебры для матрицы В существует такая унитарная (ортогональная в вещественном случае) матрица У, что В = »1*Лс», где Л = »1»ак(Л»,..., Л„), Л. - собственные значения матрицы В = А'А. Поэтому шах ~)АхОг — — п»ах (Г*ЛГх, х)'1~ = шах (ЛУх, Ух)'»~. ~~4Ь=» ~~4Ь=» 11х~Ь=» К.Ю.Богачев Точные методы ретения линейных систем т.е. шах (/Ах!) > !)А)/ .

С учетом доказанного вып»е это означает требуемое П4! =1 равенство »пах (/А х)/ = (/А!) //х//~„=1 Определение. Спектральной нормой называется 'Ч. МАТРИЧНЫЕ НОРМЫ Поскольку матрица С ' = Н* является унитарной (ортогональной в вещественном случае) и не изменяет евклидовой длины векторов: ~)7У ' х~~~ — — 'ПхП2 для всех х, то (заменяя в последнем неравенстве у = Нх ) шах ПАхП2 — — п1ах (Лу,у)ьа = п1ах(Лу,у)'~~ = шах(~Л )у (~)'~ . П4Ь=1 Пп 'и~Ь=1 ПМЬ=1 ПкП2=1 1 Пусть Л, — максимальное из Л, . Тогда шах )ПАх!)а < У~Л~;, шах (~, )у~( ) = ~/Лао — — ~1~!12. С другой стороны, если е, есть 1о-й координатный орт, то шах ПАхП2 — — шах(~ Л,)у (~)'~ > (~;Л (е„)~)'~ = ~/Л, = ПАПа.

Из последних двух соотноптений вытекает требуемое равенство п1ах ПАх(/а — — 'ПАП2. !/ХП2=1 Определение. Спектральным радиусом матрицы А называется р(А) = шах( )Л): Л вЂ” собственное значение матрицы А). Лемма 4. Для всякой матрицы А Е М„и всякой матричной нормы на М„ справедливо неравенство р(А) < ПАП . Доказательство. Пусть Л - максимальное по модулю собственное значение матрицы А, т.е. ~Л~ = р(А), х - соответствующий собственный вектор, т.е.

А х = Лх. Рассмотрим матрипу Х Е М„, все столбцы которой равны собственному вектору х . Тогда А Х = Л Х . Для всякой матричной нормы П 'П имеем ~Л~ 'ПХ П = 'ПЛ ХП = 'ПА ХП < ПАП 'ПХП, следовательно, )Л( = р(А) < ПАП . Замечание 1. Если А = А*, то р(А) = ПАП2 . Это следует непосредственно из определения спектральной нормы и того, что собственные значения матрицы А'А = Аа равны квадратам собственных значений матрицы А .

Определение. Унитарно инвариантной матричной нормой называется матричная норма П 'П, удовлетворяющая равенству ПАП = !)ГАЪ''П для всех матриц А Е М„и всех унитарных матриц Н, $" Е М„. Лемма 5. Спектпральная норма является унитарно инвариантной. Доказательство. Пусть А — произвольная матрица из М„, Г,Ъ' — произвольные унитарные матрицы.

Собственные значения матрицы (НЛЛ")*(НАЪ') = Ъ'*А*И*НАГ = 'г' 'А*У 'НАГ = 'г' 'А АЪ' те же, что и у матрицы А*А . Следовательно, спектральные нормы матриц НАЪ' и А совпадают. К.Ю.Богачев Точные методы ретеиия линейных систем ~2. ОБРАТИМОСТЬ МАТРИЦЫ, БЛИЗКОЙ К ОБРАТИМОЙ МАТРИЦЕ 12 ~ 2. ОБРАТИМОСТЬ МАТРИЦЫ, БЛИЗКОЙ К ОБРАТИМОЙ МАТРИЦЕ Теорема 1. Пусть ~~ . ~( - матпричнол норма на М„.

Если ~(А~~ < 1, то матрица 1 — А обратима, причем (1 — А) ' = 1 А". в=в Доказательство. Рассмотрим ряд 1. А". Поскольку для всякого р ) ь=о ти-~-р ти-~-р О ~! ~ А ~~ < ~ ~(А~)~ -э О при тп — ~ ос, то последовательность частичных й=ж й=ж т сумм я = ~ А" является последовательностью Копти. Так как в силу полноты ь=о т,Р С" пространство М„полно по норме ~~ ~~, то определен предел В = 1пп е 3П-~ОС 00 00 ь=о А~, прием в силу непрерывности нормы )(В(! < 1 )(А(г = .

Имеео 1 — ~!А!! ем: В(1 — А) = 1 А"(1 — А) = ~ Ах — 1 А" = 1. Аналогично проверяем ь=а ь=а (1 — А)В = 1 . Следовательно, В = (1 — А) Теорема 2. Пусть !) !) - матричная норма на М„, А - обратпимая матри- 1 ца. Если В Е М„, ~~В~! <, то матрица С = А+ В обратима, причем С ' = (А+ В) ' = ~ ( — 1)" (А 'В)"А '. ь=о Доказательство. Рассмотрим матрипу Р = А 'С = А '(А+В) = 1+А 'В . Так как по условию ~)А 'В~( < ~~А '~) ~(В~~ < 1, то по предыдущей теореме существует матрица П ' = 1.

( — 1)"(А 'В)", обратная к .О. Рассмоь=о трим матрицу С = .0 1А 1 и вычислим СС = П ~А 1(А+ В) = .0 1(1+ А-'В) = 11-'11 = 1, СС = (А+ В)0-'А-' = АА-'(А+ В)11-'А-' А(1+ А 'В)Р 'А ' = АА " = 1. Следовательно, существует С ' = С В-'А-' = ~- (-1)'(А-'В)'А-' . ь=а ~ 3. ОШИБКИ В РЕШЕНИЯХ ЛИНЕЙНЫХ СИСТЕМ Пусть решается линейная система Ах = 6, А е М„, 6 е С" .

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

ь=1 ь=о х — х= Следовательно, )(х — х)( < ( ~ ()А ~Е)(ь) ()х)( + ( ~ , ')(А 1Е!)"))(А 1е(), ()х — х(! )(А ~Е!) 1 !)А «е)( !)х)( 1 — !)А-'Е!) 1 — !)А — 'Е() !)х)! Так как Ах = Ь, то !)Ь!) = ()Ах!) < ()А)(!)х() и < . Поэтому ()А)( )(х)( !)Ь!) ()х — х(! )(А '!) !)Е(! 1, )(е() ()х)( 1 — !)А Ч ()Е)! 1 — )(А — ')! !)Е() !)Ь!) ' ии -ч'~"~ ~1х-4 И1, 1 ~~ ~~ ~~ -1~~ И вЂ” — ц~~ р )(А() ()А!) Определение.

Числом обуслонленностии матрицы А по отношению к матричной норме !) . )! называется ) )(А)) ()А '(), если А невырождена, со 7 если А вырождена. С использованием этого обозначения последнее неравенство можно переписать в виде )(х — х)! к(А) ~'!)Е() !)е)( ') '-, „(А)Ф!! ~~!А~!'~й1 !)А)( К.Ю.Богачев Точные методы решения линейных систем Ах = Ь.