Самарский А.А. Гулин А.В. - Численные методы, страница 13

Тем самым, если де1А~О, то в процессе вычислений не будет происходить деление па нуль. Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем па примере системы из двух уравнений а„х, + а„х,=~ь анх, + амх,= ~в 12) Предположим, что )а„~>)а„). Тогда па первом шаге будем исключать переменное х,. Такой прием эквивалентен тому, что система (2) переписывается в виде (3) а„х,+а„х,=), а„х,+а„х, =1„ и к (3) применяется первый шаг обычного метода Гаусса, Указанный способ исключепия называется методом Гаусса с выбора>и главного элемента по строке.

Оп эквивалентен применению обычного метода Гаусса к системе, в которой па каждом шаге исключения проводится соответствующая перенумерация переменных. Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что )а„~ > )а„), Перепишем систему (2) в виде а„х,+а„х,=1„а„х,+авх,=~, и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выоором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений.

Иногда применяется и метод Гаусса с выбором главного элемента по всей матрице, когда в качестве ведущего выбирается максимальный по модулю элемент среди всех элементов матрицы системы. 2. Матрицы перестановок. В предыдущем параграфе было показано, что обычный метод Гаусса можно записать в виде Е Е,...Е,Ах=Е„,Е,...Е,~, где Ем у=1, 2, ..., о>,— элементарные нижние треугольные матрицы. Чтобы получить аналогичную запись метода Гаусса с выбором главного элемента, нам необходимо познакомиться с матрицами перестановок.

Определен не 1. Матрнцей перестановок Р называется квадратная матрица, у которой в каждой строке и в каждом столбпе только один элемент отличен от нуля и равен единице. хз + хз + 33 = )м 2х, + хз=йз бхз+ Зхз =~3. Система имеет вид (1), где (4) А= з о ! (5) Максимальный элемент первого столбца матрицы А находится во второй строке. Поэтому в системе (4) надо поменять местами первую и вторую строки и перейти к эквивалентной системе 2хз + хз 12~ х,+ хз+ х,=1о 5х, + Зхз = 13.

(6) Систему (6) можно записать в аиде Р„Ах=Р,21, (7) т. е. она получается из системы (4) путем умножения на матрицу перестановок Далее, к системе (6) надо применить первый шаг обычного метода исключения Гаусса. Этот шаг, как мы видели, эквивалентен В2 Определение 2. Элементарной матрицей перестановок Р„ называется матрица, полученная из единичной матрицы перестановкой й-й и 1-й строк.

Например, элементарными матрицами перестановок третьего порядка являются матрицы Р„= ! о о, Р„,= о ! о, Р = о о Отметим следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения. !'. Произведение двух (а следовательно, и любого числа) элементарных матриц перестановок является матрицей перестановок (не обязательно элементарной).

2'. Для любой квадратной матрицы А матрица РнА отличается от А перестановкой й-й и 1-й строк. 3'. Для любой квадратной матрицы А матрица АР„, отличается от А перестановкой й-го и 1-го столбцов. 3. Пример. Поясним применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу. Рассмотрим следующий пример системы третьего порядка: умножению системы (7) на элементарную нижнюзо треугольную матрицу (см. (17) нз $ 2) 1 — а о 2 ! — — 1 О г О О ! В результате от (7) перейдем к системе (,Р„Ах=(,Р,Д (8) или, в развернутом виде, х, )- — х,= —, 1 ° 1з 2 2 х,+ — х,='7,— — ', (9) 5хз+ Зхз = !з Из последних двух уравнений системы (9) надо теперь исключить переменное х,.

Поскольку максимальным элементом первого столбца укороченной системы хз+ хз =~~ (з 2 2 (107 5х, + Зх, = ~з является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе х,+ хз = (з 2 2 бхз+ Зхз = 1з* (1! 1з х + — х,=1,— —, 2 2 которую можно записать в матричном виде как Р„Е,Р„А х= Р„7, Р„~. (12) Таким образом, система (12) получена применением элементарной матрицы перестановок Р = о о к системе (8). Далее, к системе (11) надо применить второй шаг исключения обычного метода Гаусса. Это эквивалентно умножению системы (11) на элементарную треугольную матрицу (.з = О 1!5 О 63 В результате получим систему Е,Р„Е,Р„Лх=Е,Р„Е,Р„~ или (13) (14) Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (14) уравнением х, = — 10 ~~1 — — -'- — — '~.), 7 2 5 что эквивалентно умножению (!3) на матрицу Е,=010 Таким образом, для рассмотренного примера процесс исключения Гаусса с выбором главного элемента по столбцу записывается в виде ЕзЕг~ 11Е1Р1-Ах =)-17 1ръзЕРл1 (16) По построению матрица Е1= Е,Е,Р,,Е,Р„А (! б) является верхней треугольной матрицей с единичной главной диагональю.

Отличие от обычного метода Гаусса состоит в том, что в качестве сомножителей в (!6) наряду с элементарнымн треугольными матрицами Е„могут присутствовать элементарные матрицы перестановок Р,. Покажем еще, что из (16) следует разложение РА =1ЛI, (17) где Š— нижняя треугольная матрица, нмеюшая обратную, и Р— матрица перестановок. Для этого найдем матрицу Е,=Р11Е1Р„.

(18) По свойству 2' матрица Р„Е, получается из матрицы Е, переста- новкой второй и третьей строк, ! — О 0 0 0 ! — !12 ! 0 Р„Е,= ! + — ха 2 3 х, + — 'х. 5 — — хЗ !о Г1 2 ! з ! 2 5 Матрица Х, согласно свойству 3 получается из Р„Ь, перестановкой второго и третьего столбцов, ! — о о а ! о — !/2 0 ! т. е.

Е,— нижняя треугольная матрица, имеющая обратную. Из (18), учитывая равенствоР,,' =Ран получим ХаРаа= РааЬа. (19) Отсюда и из (!6) видим, что Б=ЬаЬайсРтРаА=Ь 'РА, где обозначено Р=ЄЄ, Ь=Е-'Ь,'Ь,'. Поснольку Р— матрица перестановок и Ь вЂ” нижняя треугольная матрица, свойство (17) доказано. Оно означает, что метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к матрице РА, т. е. к системе, полученной из исходной системы перестановкой некоторых уравнений.

4. Общий вывод. Результат, полученный здесь для очень частного примера, справедлив и в случае общей системы уравнений (1). А именно, метод Гаусса с выбором главного элемента по столбцу можно записать в виде Ьа.Ь„,Рм ал,[,к а Ьйра,!ЬЬараиАх= =1 1,Р,; 1„„, ... Ьйра,!аЬ Раув (20) где Рй ! — злементаРные матРицы пеРестановок такие, что й<)а~ (уп и Ь,— элементарные треугольные матрицы. Отсюда, используя соотношения перестановочности, аналогичные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к системе РАх=Р1, (21) где Р— некоторая матраца перестановок. Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме.

Теор е и а 1. Если бе! АФО, то существует матрица перестановок Р такая, что матрица РА имеет отличные от нуля угловые миноры. Доказательство теоремы ! приведено в п. 5. Следствие. Если де!А~О, то существует матрица перестановок Р такая, что справедливо разложение РА=Ш, (22) где Ь вЂ” ниясняя треугольная матрица с отличными от нуля диагональными элементами и У вЂ” верхняя треугольная матрица с единичной главной диагональю. 3 А, А. Самарский, А, В. Гулка ~ пм паз) все угловые миноры отличны от нуля. Пусть утверждение теоремы верно длп любых квадратных матриц порядка пг — 1. Покажем, что оно верно и для матриц порядка пь Разобьем матрицу А порядка гн на блоки где отм зп ам ...

а,„,, Ь 1 (пщ! пауз .. и ь !)„ Достаточно рассмотреть два случая: де1 А !тьО и бе1 А !=О. В первом случае по предположению индукции сушествует матрица перестановок Р порядка т — 1 такая, что Р,А ! имеет отличные от нуля угловые миноры. Тогда для матрицы перестановок Р ~гт-! ) имеем Р„,А„Р,аь,, РА = бег тт причем деЦРА) = жбе1 Ачьо. Тем самым все угловые миноры матрицы РА отличны от нуля. Рассмотрим второй случай, когда де1А !=О, Так как бе1АФО, найдется хоти бы один отличный от нуля минор порядка л! — 1 матрицы А, полученный вычеркиванием последнего столбца и апной-либо строки, Пусть, например: агт...а,м г-хпч-! Й.1,1 ' ' ' !ы,м-г (23) !зт! и ион-! Следует подчеркнуть, что в методе Гаусса с выбором главного элемента матрица Р не задается заранее, а строится в процессе исклкзчения, как это было показано в примере из п.

3. Как правило, не требуется знать эту матрицу в явном виде. Б. Доказательство теоремы 1. Докажем теорему 1 индукпией по числу !ив порядку матрицы А. Пусть пг =2, г. е. "=1:,",;",) Если апФО, то утверждение теоремы 1 выполняется при Р=Е, где Š— единичная матрица второго порядка.

Если ап=О, то аз!ФО, так как де1 АтьО, Прв атом у матрицы где (Ф))ь Переставляя в матрице А строки с номерами ! и о), получим матрацу Р(„А, у которой угловой минор порядка т — ! имеет вид ам...а, а .. „о (-1,1 ' " (-г,ггг-1 т1 гяпгя-1 ~(й),1 О(м,т-) о ...о гя 1,1 ' ' т 1,ггг-1 и отличается от (23) только перестановкой строк. Следовательно, этот минор ае равен нулю к мм приходим к рассмотренному выше случаю. 6. Вычисление определителя.