Бабенко - Основы численного анализа (947491), страница 97
Текст из файла (страница 97)
Поэтому ранги этих матриц одинаковы. Учитывая равенство рангов по строкам и столбцам, получим, что матрица В особая. Следовательно, система (1) имеет решение, если выполнены условия совместимости, которые проверяются в процессе обратного хода. Итак, если и, =- О (1 =- 1 т 1, 1 — 2, ..., и), то матрица А уже Я Я треугольная в первых 1 т 1 столбцах, и этот шаг исключения пропускается, т,е. АР П =- А1й.
Таким образом, процесс иск1юченил с выбором главного элемента по щполбц м осуществллегпсл полностью при всех обсн1оипельсп1вах. 2. Разложение матрицы. Рассмотрим, как связаны матрицы А и А' ', если используется исключение с выбором главного элемента по Я столбцу. Формула (13) очевидным образом видоизменяется, поскольку теперь А~1~ = Л1111л А~1-Ц, и, следовательно АР1 .—... Л11 111,... М11„,А. Ввиду того, что процесс исключеяия осуществляется полностью, можно положить 1 = п — 1; тогда получим А(п-ц = Л!п 11п 1,п,...ЛХ1111,А. Последнее произведение можно записать в виде А " = ЛХп — 1(1п — 1,1„,Л1п — 21п — 1, 3п — 1) Х Х (1п — 1,1„,1п — г,зп ~зеХп — 21п — 2,зп 21п — 1,1„,) Х Х (1п — 11„~1п — 2.1„21п — З.з зЛХп — 41п — 3,1 зХп — 2,зп 21п — 1,1„— ~) ... х (Хп.1,1„,1п..т,м 2 1п,)А Заметим, что матрица ЛХп 2 .=- 1п 1 п,ЛХп 21п 1 .„, имеет нижний треугольный вид, поскольку она получается из ЛХп и перестановкой поддиагональных элементов.
Поэтому А" ' =ЛХп 1Мп 2...ЛХ1А, где А = 1п 11,, ... 1гаА. и зта матрица отличается от матрицы А перестановкой строк. Мы упоминали, что неособые нижние треугольные матрицы образуют подгруппу группы СХ (и, С). Поэтому матрица ЛХ '... ЛХ„1 = ЛХ 1 нижняя треугольная. Таким образом, А .=. ЛХ 1А1п Ц. Если исключение возможно с фиксированным порядком ведущих элементов, го матрицы Хьн единичные, и мы получим зеХ вЂ” 1 А(п — 1> (20) Ь2, Рсшснис линсйних алгебраических уравнений 473 Таким образом, в этом случае гауссовское исключение неизвестных приводит к разложению матрицы А в произведение двух треугольных матриц — нижней треугольной матрицы ЛХ 1 и верхней треугольной матрицы А1а 1).
Нетрудно проверить, что 1 1 Гас 1,с О О 1лп, от ЛХ только т.е. матрица ЛХ„ отличается элементов. Поэтому матрица знаками поддиагональных 1 т21 1 ган1 Ган2 О 1 Х 1 1 Х 1 г гХ 1 (н — Ц ган1 гва2 ° анп в которой будут представлены подднвгонвльные элементы матрицы ЛХ и элементы матрицы А1н"'1). Если ранг г матрицы А меньше п, элементы тво ДлЯ котоРых 1 ) г, бУДУт неопРеДеленны и могУт быть положены, например, равными нулю. После такого разложения система уравнений Ах =- Ь решается очень просто, поскольку она своднтся к двум системам с треугольными матрицами: И 'у = Ь, А<" ')* = у.
Сравнивая последнюю формулу с формулой (б), гдо положено г = тг — 1, мы заключаем> что вектор у совпадает с вектором (Ь1, 62, ..., 6„). 11) (» — 1) г Решение систем с треугольной матрицей дается формулами 118) и аналогичными формулами для нижних треугольных матриц. Разложение 111)) можно осушествнть непосредственно, не прибегая к методу Гаусса. Для этого достаточно заметить, что если М жвя ЬХ 1 и АО' 1) и приравнивая произведение матрице А, получим пг уравнений апа1ь О Е С,14, =- агм 1.=.! имеет очень простую структуру. Во время прямого хода можно элементы тсб хранить на месте поддиагонвльных элементов матрицы А, и в конце прямого хода мы получим таблицу ам а12 ...
а1а (1) ОО т21 агз ... а 21 474 Глава д, Творил итераций и ллетоди решения ивкоторыт задач л откУДа пРи л ч з полУчим 2,' спссС вЂ”. авп и, слеДовательно, с=с Й, =-а„— ~ ~с„сс)сзэ д' =-л, л-1, ..., и. с=1 (21) Если л > д, аналогично получим соотношение — — л,,~, !=~~-1,~'!-2...., .
(2е с=с В ~ ЛХ"" =- 1, В =- ЛХ" ~. Для специальных классов матриц разложение, аналогичное разложе- нию (19), приводит к некоторым методам решения систем линейных уравнений. 3 ад а ч а 1. Пусть А — симметрическая, положительно опреде.ленная матрипа. Докажите что она может быть единственным образом представлена в виде,4 = СС', где  — нижняя треугольная матрица с положительнымв диагональными эле лентами. Дайте формулы лля определения элементов матрицы В. Указание. Если лсатрлша А положительно определенная, то П 3.
Обращение матрицы. Прялсой ход гауссовского процесса исключения позволяет вычислить определитель матрицы А, поскольку сЫА = аыазэ ... а„„ Сс) бе 1) (23) Если в процессе исключения бьши сделаны перестановки столбцов и строк, то с)есА = ( — 1) апас,',,~...ос„Ц, Из рекуррентных соотношений (21), (22) последовательно находятся элементы матриц Л1 ~ и АСв ~), если только не встретится препятствие обращение в нуль некоторого коэффициента с) „„. Заметим, что разложение (19) реализуется всегда, а разложение (20) —. лишь при выполнении жестких условий.
Легко видеть, что разложение (20) единственно, если считать, что диагональные элементы первого сомножителя равны единице. В самом деле, если Лд лАсв 0 = ВС, то В лЛ4 ' = С[Ас" с)1; но слева стоит нижняя треугольная матрица, в справа — верхняя треугольная матрица. Поэтому зти матрицы диагональные, и, следовательно, '23. Итерационное уточнение резиенин где величина и определяется числом таких перестановок.
В процессе прямого хода можно определить и, .если учитывать изменение знака после каждой перестановки. Произведение (23) вычисляется по правилу (Ц (~ — 1) 1 (1) (~ — 2) аыа,т аи = (азза22 ...ОЭ .. 1)а„ и мы часто сталкиваемся с тем, .что в результате очередного шага может наступить либо переполнение, либо появление машинного нуля. Даже для матриц, строки и столбцы которых нормированы, определитель в редком случив бывает величиной порядка 1. Поэтому естественно ожидать, что определитель либо очень велик (с порядком матрицы), либо очень мал, и поэтому для ЭВМ, у которых под порядок числа отведен малый диапазон, возникает проблема поиска норлп|рующего множителя Л такого, что детерминант с(е((ЛА) уже может быть представлен в виде машинного числа.
Сузцествует несколько способов вычисления обратной матрицы с помощью гауссовского метода исключения. По объему работы все они равноценны. Разберем один из способов. Можно вместо системы (1) рассмотреть систему АХ=1, где 1 единичная матрица, Х неизвестная матрица. Приведя матрицу А к верхнему треуголызому виду, что эквивалентно умножению уравнения (1') слева на матрицу ЛХ, получим соотношение 4(и — 1) у- (24) и, следовательно, достаточно решить и рвз систему уравнений с верхней треутольной матрицей.
Если в процессе прямого хода делались перестановки строк, т, е, использовался метод исключения с выбором главного элемента по столбцу, то вместо соотношения (24) в силу (19) получим А Х = Ми — 11о — з,и,.151п — 2)и — 2,ы..о ° з)1111н (25) Ясно, что в процессе прямого хода нужно накапливать произведение, фигурирующее в правой части последней формулы, и затем и раэ решить систему с верхней треугольной матрицей. Число операций, необходимых для определения обратной матрицы, несложно подсчитать. Так, пользуясь формулой (24), получим, что число умножений и делеяий равно 5112/6+ п2 — бп(6, В п. 11 24 гл.
1 мы рассматривали алгоритм Шграссена обращения матриц и упоминали о существовании алгоритмов Шенхаге и других, дающих меньшее число операций. Однако для параллельных ЭВМ конструкция Штрассена ввиду ее предельной рекурсивности, возмозкно, будет уступать обычному гауссовскому методу, несиютря па пеоптимальность опенки бпз,(6+ пз — бп(6. Что же касается алгоритма Шенхаге, то совершезшо не ясна его практическая ценность. 476 Глава 8.
Теории итераций и ииегподм рси1свьл пскотсрмв задач 'й' 3. Итерационное уточнение решения системы линейных уравнении и элементов обратной матрицы агси 1 С агп — 1 — 1 ) Ггп 1п 1 - С1,— 1Л Ппп 1 Ппп ам Пп — 1,1 Пп1 где с ма,чый параметр, то прн уравновешивании по столбцам и строкам мы получаем резко 11тличающнеся друг от друга матрицы, для которых выбор главных элементов будет происходить по-разному. Так, при уравновешивании по столбцам мы получим матрицу аг „ 1 а1п П вЂ” 1,— 1 С вЂ” 1Л ап „1 Сап„ аы  —.. ап 1Л апг 1.
в'равновешивание матрицы. Перед решением системы ли- нейных уравнений или обращением матрицы часто производится процесс масштабирования матрицы. Он состоит в переходе от данной матрицы А к некоторой эквивалентной матрнпе Р, А.Рв, где Рг — -- г11ая (г1 ) 1 . 111 и Рт = г11ая (11 ) . Поскольку число обусловленности матрицы Р1 АРи 66 .— 1 1=1' зависит от элементов матриц Р1, Ри, то желательно их выбрать так, что- бы получить к|инимальное число обусловленности сопг1р(Р1 ~ЛРи). Уже простые примеры показывают, что число обусловленности матрицы Л может сильно измениться при переходе к эквивалентной матрице. Одна- ко для того, чтобы оптимальным образом выбрать элементы матриц Р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}
