Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 26
Текст из файла (страница 26)
Плохо обусловленная матрица может оказаться практически особенной, если ее элементы заданы приближенно. Естесгвенно, что система линейных уравнений с плохо обусловленной матрицей мало устойчива, т. е. ее решение сильно изменяется при малых изменениях как коэффициентов, так и свободных членов. Проследим, как значительна эта неустойчивость. Пусть АХ= Р 143 9 !5] ОБУСЛОВЛЕННОСТЬ МАТРИЦ откуда дхл — = — ал,ху.
дл19 Аналогично из формулы 0 дХ -г дР дУг 0 дхв следует, что — = аы дУБ Таким образом, если элементы обратной матрицы велики, то малое изменение как коэффициентов системы, так и свободных членов влечет за собой значительное изменение решения. Так, например, для рассмотренной выше матрицы Ж' „близкие" свободные члены 32 , 33 , 31 ) 31.999, 32.999, 31.001)' 31.99 , 32.99 , 31.01 )' 3!.9 , 32.9 , 31,1 )' Р, =(23 Р =(23.001. Гз = (23.01, Р, = (23. 1 будут приводить к далеко не „близким" решениям Х,=(1 .
1 . 1, 1 )г Хз=(!.136, 0.918, 0.965, 1.021)' Х, = (2.36, 0.18, 0.65, 1.21 )' Х, = (14.6, — 7.2, — 2.5, 3.1 )'. Явление плохой обусловленности матрицы было известно давно, по-видимому, еше Гауссу. Однако изучение и количественные характеристики этого явления появились недавно.
Мы видели, что „малость" определителя является причиной плохой обусловленности матрицы. Однзко легко видеть, что одна величина определителя не может вполне характеризовать обусловленность матрицы'. Так, например, очевидно, что матрицы, отличающиеся лишь постоянным множителем, надлежит считать одинаково обусловленными. Соответствующие же им определители будут отличаться на л-ю степень множителя.
Отсюда следует, что величину определителя нузкно сравнивать хотя бы с л-й степенью наибольшего 144 точныв мвтоды вешания систем линейных ггавнвннй [гл. и элемента матрицы или и-й степенью какой-либо нормы матрицы. Однако н этого недостзточно. Так, из натрии 20 0 0 0 1 0 0 0 0.05 20 0 О 0 020 0 0 025 005 0 0 005 0 0 О 5 О 0 0 4 0 1 О 0 О 20 и потому одинаковые изменения в элементах данных матриц приведут к разным изменениям в элементах обратнь1х матриц, которые в первой матрице будут более значнтельными.
Для характеристики матрицы с точки зрения ее обусловленности несколькими авторами предложены различные количественные характеристики, называемые числами обусловленности. Это два числа Тюринга ') гч'-число = — % [А) гч(А ) = «[А) л М-чнсло = — — М [А) М (А ) = р, [А), где И[А) = [Г5рА'А и М[А) = и ° шах)аы[ — рассмотренные выше нормы матриц, число Тодда') Р-число = . > [ = Р[А) ии1п! Ц[ где Хг — собственные аначения матрицы А, и Н-число = [1 А [ [А где [[А([ — третья норма матрицы. Легко видеть, что Н-число = у — = з) [А) г, ри где рч и р„наибольшее и наименьшее собственные аначения матрицы А'А. А' — транспонированная с А матрица.
К но, что т) [А) = ф' р [А'А). г) Тю ринг [1). з) Тодд [Ц. первая обусловлена хуже. чем вторая, хотя у них одинаковы как определители, так и наибольшие элементы. Действительно, соответствующие обратные матрицы будут 145 ф 15) овгсловлянность мдтвиц 1(ля симметричных матриц Р-число обусловленности совпадает с Н-чвслом. Числа обусловленности не дают, конечно, исчерпывающей характеристики обусловленности матрицы. Отметим неравенства, связывающие эти числа: ч (А) ( р (А) ( пач (А) «(А) ( ч((А) ( лч(А) р(А) ( ч1(А). Легко подсчитать, что для ортогональных матриц ч(А) = ч)(А) = =- р(А) = 1. Покажем, что все числа обусловленности не меньше единицы. Для р(А) и ч(А) это очевидно, 1(ля ч(А) это следуег из тождества ч(А)= — фг (р + +р )( — „+ + — „)= --'.)7''~(У-9)' где 9, ..., р — собственные значения матрицы А'А.
Числа обусловленности ч(А) и т(А) имеют следующий вероятностный смысл. Рассмотрим систему линейных уравнений А '('= Р, где вектор Р задан точно, а элементы матрицы А являются независимыми случайными величинами со средними значениями а0 и одинаковой дисперсией ае, которая предполагается очень малой по сравнению с величинами коэффициентов, Тогда М-число обусловленности показывает во сколько раз отношение среднего к зад р атичного ошибок неизвестных к среднему квадратичному самих неизвестных превосходит отношение среднего квадратичного ошибок коэффициентов системы к среднему Квадратичному самих коэффициентов.
Н-число дает отношение наибольшей полуоси к наименьшей полуоси для эллипсоида рассеяния вектора, компонентами которого являются ошибки неизвестных'). Легко подсчитзть, что для 'матрицы %', рассмотренной выше, Р-число = Н-число о 01015095 2984 3028868 Н-число = — 'у' 9ЗЗ у~9708 752 4 М-число = — 40 Х 272 = 2720. 1 4 г) 7 юр ииг ~1), Д. К. Фаддеев (4).
10 звв, зг(. Д, Ю Фаддеев е В, Н, Фаддееве 146 точные метОды РешениЯ систем линейных УРАВнений [гл. н Числа обусловленности матрицы Ф' еше не очень велики. В практических расчетах иногда приходится встречаться с системами, матрицы которых имеют числа обусловленности свыше 20000. На вопрос о том, какой характер неопределенности влечет за собой плохая обусловленность системы, в известной степени отвечают следующие рассуждения. Пусть А невырожденная матрица, которую для простоты мы будем считать вещественной, пусть и,, и,, ..., и„ортонормальная системз собственных векторов для матрицы А'А н пусть рн йа,..., р„ соответствующие им собственные значения.
Тогда векторы )г; = 1 = =Аи. образуют ортонормальную систему собственных векторов для матрицы АА'. Действительно, АА'1/г = = АА'Аи; = ~/ е, Аи; = р;)~;; )ГР~ далее ()гн Ру) =, . (Аио АС7~) = 1' и;р.~ = — ' — <А'Аи,, и,) =,"' <и,, и,) = й,у. у Нги,Г Ь Р1ну Пусть теперь дана система АХ= Р с матрицей А. Рааложим вектор гт по векторам Рп 1',, ..., )г„ ге= ~а с;)ге ясно, что сг=(Р, )гг). Далее ищем решение в виде ь х= ~ а,ио Подстановка в систему дает ~~ 1г 'у р- Ка = ~~ сг(го г=т Откуда следует, что сг а )г Можно убедиться в том, что при малых изменениях матрицы А как собственные значения рч матрицы А'А, так и системы векторов <и,) и (У,) иаменяются мало, независимо от обусловленности матрицы А.
Однако при плохой обусловленности матрицы А среди рг $!61 метод ГАуссА имеются очень малые числа, и даже малые их изменения могут оказаться относительно большими. Коэффициенты аг формулы (1), отвечающие малым рн окажутся плохо определенными, так что решение „разбалтывается' в направлениях векторов Уо соответствующих малым йо что мы уже видели раньше на основе вероятностных рассуждений. Вели коэффициенты системы известны точно (что бывает, например, при решении методом сеток краевых задач для уравнений эллиптического типа с постоянными коэффициентами), то источником неопределенности может служить только неточность в коэффициентах со соответствующих малым ро которая, соглзсно формуле (1), увеличивается во много раз при переходе к коэффициентам Фо Однако и это явление может не иметь места, если по условию задачи вектор свободных членов ортогонален или почти ортогонален к векторам Го соответствующим малым ео и потому решение остается устойчивым при небольших допустимых (без нарушения упомянутой почти-ортогональности) изменениях свободных членов.
$16. Метод Гаусса В этом параграфе мы изложим наиболее простой и естественный метод для решения системы уравнений, основанный на последовательном исключении неизвестных. Как уже говорилось выше, он связан с именем Гаусса. Метод имеет много различных вычислительных схем. Мы начнем изложение с рассмотрения так нззываемой с х ем ы единственного деления. Итак, пусть дана система уравнений ацх, + ажхя+ ... + а,„х„=), а,,х, + а,,х,-+...
+ а,„х„=уя а„,х,+а„,ха+ ... +а,„х„=-у„. ага ~Ъ= (у) 1) ап ,1~ а, Мы получим новое уравнение х,+б, х,-+ ... +бщх„=ап (2) Исключим теперь неизвестное х, из всех уравнений (!), начиная со второго, посредством вычитания из этих уравнений уравнения (3), 10* Допустим, что коэффициент аы + О. Разделим коэффициенты первого из уравнений (!) (включая и свободный член) на коэффициент агы который мы будем называть велущим элементом (1-го шага), и обозначим 148 точныи матоды гашения систем линейных гглвнений (гл.
и умноженного соответственно на числа аз,, аа„..., а„,, Преобразо- ванные уравнения будут а22, ЗХЗ+ . ° . + а233, 1ХЗЗ = 12 1 (4) „.,х + г- „„., =-У. о где а;;,=аз.— апЬ12 (1, У «2) ЗсЗ=Л вЂ” апд1. (5) где Исключая неизвестное ха из уравнений (4), начиная со второго, мы придем к уравнениям а33 ° ЗХЗ + ' ' ' + азч. 2 хн УЗ. 2 аьз 2хз+ ° ° + аьз Зхз = УЗ 2, где аЗу З=а1.21 — а12.1ЬЗу (( ./> 3).
А, 2 = Л. 1 — а32, 322. Продолжаем процесс по той же схеме. На т-м шагу мы получим уравнения .+Ь..„.„+ " +Ь, .=й. а234.1т+1. ЗЗХЗЗГ1+ ' ' +от+12. тх2 133+!. 32 (б) а„ч, х „,.+ ... -+а„„. Х„=у„ гле ачьг. ы 1 Ь т= аз„ь. 23 У .23 — 1 КЗЗ а2232 33 (у )«т+ 1). а;д,„— — агт т,— а121,2 1Ь„Ы л Ш=у322. 1 — аЗЗ, „1 12,„. Объединив все первые уравнения каждого шага, мы получим си- стему Разделим далее коэффициенты первого из преобразованных уравнений на ведущий элемент 2-го шага аа,, который будем считать отличным от нуля.
Мы получим уравнение 149 $16) мвтод гласса (8) ха =Ко с треугольной матрицей, эквввалентную исходной системе. Отметим, что описанный процесс возможен только при условии неравенства пулю всех ведущих элементов а„, ,„ ,, так как по хоау процесса на них приходится производить деление. Из системы (8) значения для неизвестных находим последовательно от х„ к х, по очевидным формулам хм=у — 17м ьтх,— ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
