Беклемишев - Дополнительные главы линейной алгебры (947281), страница 27
Текст из файла (страница 27)
Пусть система уравнений описывает связи, имеющиеся между составными частями некоторого реального объекта. Прн большом числе составных частей естественно, что не все они окажутся связанными друг с другом непосредственными связями. Если непосредственно связаны те из частей, номера которых отличаются не больше чем на К то матрица связей окажется ленточной. Для часто встречающихся специальных видов матриц разработаны модификации большинства известных алгоритмов и специальные алгоритмы, позволяющие использовать вид матрицы. Так, существуют отдельные алгоритмы для решения систем линейных уравнений с симметричными или с ленточными матрицами, и для нахождения собственных значений и собственных векторов преобразований с такими матрицами. Эти алгоритмы работают более эффективно 'и позволяют решать задачи большей размерности за счет использования специального нида матриц.
Мы не будем заниматься этими алгоритмами. Выбор метода решения системы линейных уравнений или вообще любой задачи, касающейся матриц, самым существенным образом зависит от способа хранения матрицы. Такие методы, как известный из общего курса метод Гаусса, хороши для не слишком больших матриц общего вида. Для больших матриц, при хранении которых используются их особые свойства, методы решения систем уравнений, основанные на преобразовании матрицы системы, применять неудобно.
В процессе преобразований разреженная матрица становится плотно заполненной, если только не принять специальных мер по поддержанию разреженности. Точно так же, если элементы матрицы вычисляются по простым формулам, элементы преобразованной матрицы, вообще говоря, уже не сбладают этим свойством. Поэтому для решения систем линейных уравнений с большими матрицами чаще применяются специальные методы, например итерационные методы, рассматриваемые в $4. гл.
и!. ВВедение В числаииые мвтоды $2. Обусловленность 1. Верхняя оценка возмущения. Пусть дана исходная система линейных уравнений Ах=В, (1) где А — квадратная матрица порядка п и йе1 А ~ О. Рассмотрим возмущенную систему (А+ ЬА) у =-(з+ Ьд. (2) Прежде всего, не ясно, будет ли система (2) иметь единственное решение так же, как и (1). Ниже мы наложим иа ЬА достаточное для этого условие. Наша ближайшая задача — оценить при этом условии норму разности решений обеих систем.
В этом параграфе под матричной нормой всюду понимается норма, обладающая кольцевым свойством и согласованная с нормой в пространстве столбцов. П р е д л о ж е н и е 1. Лусть для некоторой матричной норма квадратная матрица В удовлетворяет условию !! В !!» р ( 1. "л'огда существует матрица (Е + В) ' и !! (Е + В) ' !! - (1 — р) '. Д о к а з а те л ь с т в о '). Из оценки спектрального радиуса матрицы (предложение 1 у 5 гл. 11) вытекает, что все собственные значения матрицы В лежат в круге ! Х !» р, т. е. внутри круга сходимости разложения функции (1 + Х) ' по степеням Х. Это гарантирует существование матрицы (Е + В) ', равной сумме ряда Š— В+ Вз —... Для частичной суммы этого ряда, согласно (12) р 4 гл. 1, имеем оценку !Яа!» у ~ Вь!» '~~!~ В!з о о Отсюда переходом к пределу при я- оо получаем требуемое неравенство.
Перейдем теперь к оценке нормы возмущения решения, т. е. 1! Ьх !! = !! у — х !!, где у — решение системы (2), а х — решение (1). Для этого вычтем (1) из (2). Мы получим (А+ ЬЛ) (х+ Ьх) — Лх = 6Ь, нли (А+ ЬА) Ьх+ 6Лх = ЬЬ. Запишем А+ЬА в виде А(Е+Л 'ЬА) и предположим, что !А-'! (ЬА(=р(1.
(4) ') !1ояавательство использует материал гл. 11. Читателю, ие изучавшему втой гаазы, можно припять предложение 1 без доказательства. 5 а ОБуслОВленнОсть Тогда 1А '6А1(р и, согласно предложению 1, матрица Е+ + А-'6А имеет обратную. Следовательно, (А+ 6А)-' = (Е+ А-' 6А)та А-', и из (3) бх = (Е+ А-' 6А)-' А-' 6Ь вЂ” (Е+ А ' 6А)-' А-'6Ах. Отсюда [бх[~ —,1А '| ,'|6Ь~[ — — 1А '1 16А1 1х1.
1 1 Из равенства (1) следует, что 1Ь1~1А1 [х1. Усилим неравенство, умножив первый член правои части на 1А1 [х1/1Ь1. Тогда 1бх 11: с(А):|х|| |,'6Ь) с(А))х1 16А1 1 — в 1ь1 1 — о 1А1' где (б) с(А) =1А-'1 1А 1. Разделим на 1х| и учтем, что р=|6А,'| 1А-'[=с(А)— 16А 1 ,|А( Мы получим окончательную оценку |~бх,') с(А) /16А'| [А) )х1 16А) ( (А,'| 161/' ('; А;| Число с (А), введенное формулой (5), называется числом обусловленности матрицы А в рассматриваемой норме. Теперь мы можем сформулировать следующий результат.
П р е д л о ж е и и е 2. Пусть матрица коэффициентов и столбец свободных членов системы (!) получили возмущения ЬА и 6Ь, причем в некоторой лсатричной норме || А ' |1 1|6А|| < 1. Тогда возмущенная систелса имеет единственное решение, и относительное возмуи(ение ||бх ||/|| х || решения системы (1) оценивается через относитгльныг возмуи|ения о = || бА ||/|| А |1 и 6 = 116Ы[/[1 Ы| матрицы системы и столбца свободных членов формулой ; бх, с(А) (сс+6) (б) (х, ( ! — (А)и где с (А) — число обусловленности матрицы А в рассматриваемой норме. Примечательно, что в правую часть (б) входят только относительные возмущения А и Ь. Матрица А представлена только своим числом обусловленности, а столбец Ь не входит совсем.
2. Число обусловленности. Согласно предложению 2, чем больша число обусловленности, тем большее относительное возмущение решения возможно при таких же относительных возмущениях нс- !24 Гл. н!. ВВедение В численные методы ходных данных. Число обусловленности определяется не только матрицей, но и выбором нормы. Для различных норм формула (6) будет давать разные оценки относительного возмущения, более грубые или более точные. В этом пункте мы рассмотрим вычисление числа обусловленности матрицы и выведем некоторые его свойства.
Начнем со следующих простых соотношений, имеющих место для любой нормы. Непосредственно из определения вытекает с(Л) = с(А-'). (7) Перемножая неравенства И АВ ~! == И А И И ВИ и И (АВ) ' ! = = И В 'А 'И ~ ИВ 'И И А 'И, получаем с(АВ) с(А)с(В). (8) Далее, из А 'А = Е следует с (А) ==- ~! Е И. Поскольку И Е И )! (см. (!!) 6 4 гл. 1), получаем с(А) гв(Е(еь 1. (9) Пусть а, и а„— наибольшее и наименьшее сингулярные числа матрицы А. Согласно предложению 14 4 4 гл. 1 для спек!ральной нормы имеем 1А 1! = а„а по формуле (16) 5 4 гл. 1 ИЛ ' И = а„'.
Поэтому число обусловленности в спектральной норме (или, как говорят, спектральное число обрсловлечности ' находится по формуле с(А) = — "'. (10) я В $ ! из геометрических соображений мы получили, что обусловленность системы нз двух уравнений с двумя неизвестными характеризуется отношением полуосей некоторого эллипса (прообраза окружности при линейном преобразовании, определяемом матрицей системы).
Вспоминая геометрический смысл сингулярных чисел и формулу (10), мы замечаем, что это отношение как раз и есть спектральное число обусловленности. Из (1О) сразу следует, что для ортогональной (а также для унитарной) матрицы спектральное число обусловленности равно 1. Из соответствующего свойства спектральной нормы (предложения !3 5 4 гл. !) следует, что спектральное число обусловленности с (А) не меняется при умножении А на ортогональную (унитарную) матрицу. В силу этого обстоятельства при решении систем линейных уравнений предпочтительнее умножать матрицу системы на ортогональные преобразующие матрицы. Рассмотрим теперь неравенства, связывающие числа обусловленности, соответствующие различным нормам.
Если две нормы ф и ф таковы, что для любой матрицы <р (А) ~ ()ф (А), то соответствующиечислаобусловленности, как легко видеть, связаны неравенством СВ:И ~'Сэ, 125 5 в оаусловлвнность Евклидова норма матрицы равна квадратному корню из суммы квадратов ее сингулярных чисел, а спектральная норма — максимальному сингулярному числу. Поэтому из неравенства ас « ~ а,*«па', с=! следует (А1«1А(сл«)с и )А 1, и потому с(А)«св(А) «пс(А). (П) Аналогично, из снах ~ асс,сс « ~', ! оп 1' =- и' гп ах , 'ац ~з мы получаем неравенства для нормы )А), =пгпах (ас~( и евкли- ьс дозой нормы )сл =) А(" «1А )л«(А)', а из них — оценки для чисел обусловленности 1 — с~ «сл«сж.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
