Самарский А.А., Гулин А.В. Численные методы (1989), страница 12

Тогда матрицу А можно представить, причем единственным образом, в виде произведения А =1.У, (8) где Š— нижняя треугольная матрица с ненулевыми диагональныати элементами и У вЂ” верхняя треугольная матрица с единичной диагональю. Доказательство. Докажем сформулированное утверждение сначала для матриц второго порядка. Будем искать разложение матрицы А=~" еи ьм в виде [~и ~~ а~ где 1„, 1ти 1гь и„— неизвестные пока числа. Для их нахождения придем к системе уравнений 1„=а„, 1„и„=а„, 1„=ами 1„и„+ 1„=аги которая имеет единственное решение 1„= а„, и„= а„/а„, 1„= ато анап — ае,ам еи По предположению теоремы а„чьО, аиамчьаиап, следовательно, элементы 1„и 1„отличны от нуля.

Дальнейшее доказательство проведем методом индукции. Пусть утверждение теоремы справедливо для матриц порядка я — 1; докажем, что оно справедливо и для матриц порядка й. Представим матрицу А порядка я в виде аи ... а„~ а ... а йчл'''йтя1 ал, ... а»„, и обозначим Ь„,= (а„„..., а...). Согласно предположению индукции существует требуемое разложение матрицы А„„т.

е. Аа-~ = Са-1 Уь-и где 1., „ У„, — соответственно нижняя и верхняя треугольные мат- (1 1) (12) (13) Из предположения индукции следует существование матриц 1а'„ У~й. Поэтому из (11) и (12) получим 1 1 иа,= Ц йад „1й й=Ьй йУ» й и, далее, 1йй=айй 1й-Фй-й. Таким образом, 1.У-разложение матрицы А порядка й существует. Остается доказать, что 1ыФО. Рассмотрим определитель матрицы А. Из разложения (1О) следует, что бе1А= (де((.й й)1й,(бе1 У,,) =(де(Ей й)1м,. По условию теоремы бе1АМО, следовательно, 1ййчь0. Тем самым индукция завершена и доказана возможность требуемого разложения.

Покажем теперь, что такое разложение единственно. Предположим, что матрицу А можно разложить двумя способами: А=ЛйУ,=1.,У,. Тогда 1.й=ЬйУ,У,' и У,У =1;ййЬ,. (14) Матрица в левой части уравнения (14) является верхней треугольной, а в правой части — нижней треугольной. Такое равенство возможно лишь в случае, если матрицы У,У,' н Ь,"1.з диагональные. Но на диагонали матрицы У,У,' (а следовательно, и матрицы Ь,'Ев) стоят единицы, следовательно, эти матрицы единичные: УйУйй = Сто.з =Я. Отсюда получаем У,=У„Ей=1.м т. е.

разложение (8) единственно. Теорема об ЬУ-разложении полностью доказана. 3 а меча н ие. Если хотя оы один из угловых миноров матрицы А равен нулю, то указанное Ш-разложение невозможно. Это легко видеть на примере матриц второго порядка. 67 рицы, обладающие указанными в теореме свойствами. Будем искать разложение матрицы (9) в виде А ~' ]( '"'], (10) где 1„„и,,— неизвестные пока векторы, 1й-! — (1й! 1йй ° ° 1й,й-й) ий-! = (иы ийы .. ий-й й) Перемножая матрицы в правой части уравнения (10) и учитывая (9), приходим к системе уравнений Ь йиай — — ай„ 1 йУь й=Ь „ 1ь.йиь-й + 1ьй = айа. о ...

!!! О О ... г,".+ь! ! — е! о ... ! о В матрице !.! все элементы главной диагонали кроме 1„равны еди- нице. Из остальных элементов отличными от нуля могут быть толь- ко элементы !иго столбца, расположенные ниже 1в. Обратной к Ез является элементарная нижняя треугольная матрица о о !! о ! о ...

— 1;! о ... о Рассмотрим для наглядности сначала систему Ах=), состоящую из трех уравнений: аых, +а,зх, + аззхз=го а„х, + а,зх, + аззхз = )м (15) аыхз + аззхз + аззхз = )з. После первого шага исключения по методу Гаусса преобразован- ная система принимает вид в1з 6 + — х,= —, ан аи + — х, аа а„ х, (- — ) (- — )- азнчз '~ ! аз~а~в 1 в~з - азз (хз+ (азз )хз=!з зо аа ( аи ви (16) Отсюда видно, что матрица А, системы (16) получается из исход- 88 Следствие. Метод Гаусса можно применять тогда и только тогда, когда все угловые миноры матрицы А отличны от нуля.

3. Элементарные треугольные матрицы.Мы уже видели, что метод Гаусса приводит к разложению исходной матрицы в произведение двух треугольных. Более детально описать структуру этих треугольных матриц можно с помощью так называемых элементарных треугольных матриц. Матрица 1! называется элементарной нижней треугольной матрицей, если она имеет вид ной матрицы А путем умножения А слева на элементарную мат- рицу 1/адд 0 0 ! 7- = ~ — д1ад ! О~, 1 — адд/адд 0 1 (17) так что А,=Е,А.

При этом систему (16) можно записать в виде Е,Ах=Ед). Матрицу (17) будем называть элементарной треугольной матрицей, соответствующей первому шагу исключения метода Гаусса. Перепишем систему (16) в виде х, + с„х, + с„х, = у„ ддд, <д) дш а„х,+а„х,=1д, <д> (дд 1д) аддх, + адд х, = ~д (18) и осуществим второй шаг метода Гаусса, т. е.

исключим неизвестное х, из последнего уравнения. Тогда получим систему вида х +с хф+сдх, =уд х,+с, х =у„ адДддХ, = д (19) Нетрудно видеть, что переход от (18) к (19) осуществляется путем умножения системы (18) на элементарную треугольную матрицу 1 0 0 О 1Лддд! О (20) 7.дЕ,Ах = 7, Ц, (21) где матрицы Е, и Ед определены согласно (17), (20). Наконец, умножая (21) на матрицу Е = О 1 О получаем систему Ь,ЦЕ,Ах=1.дд'.д(.д1, (22) матрица которой У=А,д.дд.,А является верхней треугольной матрицей с единичной главной диагональю.

Отсюда следует, в частности, что А =ЕУ, где Е=Е,'1, (,," — нижняя треугольная матрица. Таким образом, ЛУ-разложение матрицы А может быть получено с помощью элементарных треугольных матриц: сначала строятся матрицы 1.„д.„д,, и вычисляется У=д'.,1.дЕ,А и затем находится Ь= Таким образом, после второго шага исключения мы приходим к системе =Е,"1.,'1.,'.Отметим, что матрицы Ез' имеют простой вид: о о а(1) 0 22 а(1) ! Зз о о аз(',) 0 (1) (2) о 0.1 о~, /.,'= о 1~ ао г -1 1 1 а21 1.аз( ан ам аз( О ...

1/а~з;1) О ... О 0 ... — а( 1)~/а~22 1) 1 ... 0 0 ... — а(„2 ~)/аз(~2 ') 0 ... ! МатрИца 1,1 ОеущЕСтВЛяЕт ИСКЛЮЧЕНИЕ НЕИЗВЕСТНОГО Хз ИЗ ураВНЕНИй с номерами й+1, й+2, ..., т. Матрицы Ез' существуют и имеют вид ! ° .. 0 0 0 ... а(22 1) 0 0 ... а(2 1) ! 221 З 1-21 = 0 ...

а(2,1) 0 ... 1 5 3. Метод Гаусса с выбором главного элемента 1. Основная идея метода. Может оказаться, что система Ах=/ имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. Кроме того, заранее обычно неизвестно, все ли угловые миноры матрицы А отличны от нуля. В этих случа- ев причем на диагонали матрицы Ь расположены ведущие элементы метода исключения.

Запись метода Гаусса в виде (22) детально описывает процесс исключения. Все сказанное выше переносится без изменения и на системы уравнений произвольного порядка (2). Процесс исключения можно записать формулой /. 1, Е(АХ=1. Е,...Ь()', (23) где элементарная нижняя треугольная матрица /.1 на й-м шаге исключения имеет вид ях обычный метод Гаусса может оказаться непригодным. Избежать указанных трудностей позволяет метод Гаусса с выбором главного элемента. Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю.

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

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

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

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

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

2'. Для любой квадратной матрицы А матрица Р„А отличается от А перестановкой й-й и 1-й строк. 3'. Для любой квадратной матрицы А матрица АР„отличается от А перестановкой Ьго и 1-го столбцов. 3. Пример. Поясним применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу. Рассмотрим следующий пример системы третьего порядка: х,+ х,+ х,=)„ 2х1 + хв=)м бх,+Зх,=~,.

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

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