Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 12
Текст из файла (страница 12)
Теперь мы имеем право трактовать метод Гаусса следующим образом. Пусть заданы матрицы А н вектор Е Сначала проводится разложение А в произведение двух треугольных матриц, А=ВС. Затем последовательно решаются две системы уравнений (6) Сх=у (7) с треугольными матрицами, откуда и находится искомый вектор х. Разложение А=ВС соответствует прямому ходу метода Гаусса, а решение системы (6) — (7) — обратному ходу. Заметим, что в алгоритме, изложенном в $ 1, разложение А=ВС и решение системы (6) проводится одновременно. Далее, следуя стандартным обозначениям, нижние треугольные матрицы будем обозначать буквой Е (от английского 1отчег — нижний) и верхние треугольные — буквой У (от английского нррег— верхний).
2. Теорема об ЕЕс-разложении. Обозначим через Лс угловой минор порядка 1 матрицы А, т. е. 1. исс вм1 Теоретическое обоснование возможности разложения матрицы в произведение двух треугольных матриц содержит следующая Теорема 1 (теорема оо Е()разло кенни). Пусть все угловые миноры матрицьс А отлинньс от нуля, Л,ФО, 1'=1, 2, ..., т. Тогда 55 матрицу А можно представить, причем единственным образом, в виде произведения А =1Л/, (8) где Ь вЂ” нижняя треугольная матрица с ненулевыми диагональными элементами и У вЂ” верхняя треугольная матрица с единичной диагональю. Д о к а з а т ел ь с т в о. Докажем сформулированное утверждение сначала для матриц второго порядка.
Будем искать разложение матрицы А [аи а1»1 в виде А=" где („, (»ь („„, и„— неизвестные пока числа. Для их нахождения гридем к системе уравнений („= ась („и,. = ась („= ага (мни+1„=-а»,, которая имеет единственное решение (и=во, им=а~»!и», (ы=ам, аиа,» — а»,ам '22 = аи По предположению теоремы а„ФО, а„амчеамаи, следовательно, злемснты 1„и 1м отлвчны от нуля, Дальнепшее доказательство проведем методом индукции. Пусть утверждение теоремы справедливо для матриц порядка я — ); докажем, что оно справедливо и для матриц порядка я. Представим матрицу А порядка я в виде ао ...а» а,» (9) а», » а,, а »-и1 ' ' ' »-и»-1 а»~ ' ' ' а»,»-» и обозначим А»,= ...,...., а»,= а„,= (а„, ..., а,»,). Согласно предположению индукции существует требуемое разложение матрицы А, „т.
е. А»-3 ~ Ь-1( А ! где 1.» ь У„,— соответственно нижняя и верхняя треугольные мат- рицы, обладавшие указанными в теореме свойствами. Будем искать разложение матрицы (9) в виде А — ~ '' (10) Перемножая матрицы в правой части уравнения (10) и учитывая (9), приходим к системе уравнений 1-»»и»-т =а»-о 1,,и,,=Ь» „ 1» хн», + 1»»=ам. Из предположения индукции следует сушествование матриц 1.»'о (1»',. Поэтому из (11) и (12) получим ц»,= 1.» гв» „1»,=о»,(/»'х и, далее, 1»»»тю 1»-гц»-о Таким образом, У.У-разложение матрицы А порядка й существует.
Остается доказать, что 1„~0. Рассмотрим определитель матрицы А. Из разложения (10) следует, что де1 А = (йе11,,) 1»,(бе1 1/,,) = (с)е1 1,,) 1» . По условию теоремы»)е(АФО, следовательно, 1„,ФО. Тем самым индукцня завершена и доказана возможность требуемого разложения.
Покажем теперь, что такое разложение единственно. Предположим, что матрицу А можно разложить двумя способами: А = 1„11, =1,,У,. Тогда 1»=Е,У,У,' и ии =Е»Е,, (14) Матрица в левой части уравнения (14) является верхней треугольной, а в правой части — нижней треугольной. Такое равенство возможно лишь в случае, если матрицы (1»У,' и Е,'Ез диагональные. Но на диагонали матрицы Ух(1,' (а следоватепьно, и матрицы 1,'Ет) стоят единицьц следовательно, зти матрицы единичные: Отсюда получаем У,=У„1,,=1.„т.
е. разложение (8) единственно. Теорема об 1,(l-разложении полностью доказана. 3 а меч ание. Если хотя оы один из угловых миноров матрицы А равен нулю, то указанное 1»/-разложение невозможно. Это легко видеть на примере матриц второго порядка. бЧ где 1, „н,,— неизвестные пока векторы, 1», = (1»о 1„», ..., 1»л — ), и»- = (мм, нх„, ..., и,, „)*. (11) (12) (13) о ... гн О о' ... ''г„'и о '..'.'! В матрице Ц все элементы главной диагонали кроме 1„равны еди- нице.
Из остальных элементов отличными от нуля могут быть толь- ко элементы 1-го столбца, расположенные ниже 1я. Обратной к (з является элементарная нижняя треугольная матрица 0... !т! н о ... — !,.~и!-,,' о ... — !,еиэ!-,! о ! о...— !и!;,'о...о! Е!" = Рассмотрим для наглядности сначала систему Ах=(, состоязцую из трех уравнений: а их, + а,зхз + аззхз = ! и амхз + аззхз + аззхз = з'з аззхз + аззхз+ аззхз =зз. (15) После первого шага исключения по методу Гаусса преобразован- ная система принимает вид взз й + — -тз =— аи ьа а~з + — х, ан (1б) Отсюда видно, что матрица А, системы (16) получается из исход- 68 Следствие.
Метод Гаусса л!ажно применять тогда и только тогда, когда все угловые Чзаноры матрицы А отличны от нуля. 3. Элементарные треугольные матрицы. Мы уже видели, что метод Гаусса приводит к разложению исходной матрицы в произведение двух треугольных. Более детально описать структуру этих треугольных матриц можно с помощью так называемых элементарных треугольных матриц.
Матрица Ц называется эле,иентарной нижней треугольной матрицей, если она имеет вид ной матрицы А путем умножения А слева на элементарную мат- рицу )(а„о 01 Е( = — ам!аа ! О 1 — аз 1('а(( 0 ! (17) так что А,=Е,А, При этом систему (16) можно записать в виде Е,АХ=ЕД. Матрицу (17) будем называть элеме)(тарной треугольной матрицей, соответствующей первому шагу исключения метода Гаусса. Перепишем систему (16) в виде х, + с„», + с„х, = э'„ (1) и) 3(О а.„х, + а,3 ха = ("3, (о (и .и) азз Х, + а„", Х, = ('3 (18) (19) Нетрудно видеть, что переход от (18) к (19) осуществляется путем умножения системы (18) на элементарную треугольную матрицу ! 0 0 Е.
— 0 )('а(,(,~ 0 Π— ("lа(о ! — а„а,з (20) Таким образом, после второго шага исключения мы приходим к системе Е,,1.,Лх = ЕзЕ,(', (21) где матрицы Е, и Е, определены согласно (17), (20). Наконец, умножая (21) на матрицу 0 ! О получаем систему Е,Е,Е,Л»= Е,Е,Е,~, (22) матрица которой Е(=Е,Е,Е,А является верхней треугольной матрицей с единичной главной диагональю. Отсюда следует, в частности, что А=Е(7, где Е=Е,'Е,'Е„' — нижняя треугольная матрица. Таким образом, Ы-разложение матрицы А может быть получено с помощью элементарных треугольных матриц: сначала строятся матрицы Е,, Е„Е, и вычисляется Е(=Е)ЕЗЕ,А и затем находится Е= и осуществим второй шаг метода Гаусса, т.
е. исключим неизвестное х, из последнего уравнения. Тогда получим систему вида Х( + С(3Хз + С 3Х3 Д) Хз+ СззХ3 =Уз а„„»З =!)3 ° =Е,'Е,,'Е,'.Отметим, что матрицы Е»' имеют простой вид: о о а",! О »» ац! ! О О и а.„а,, ~ Ц1 О1 ~ О , Е,' = аа к -! ам 1.ам 'Н а„ Г1 О о о ам причем на диагонали матрицы Е расположены ведущие элементы метода исключения. Запись метода Гаусса в виде (22) детально описывает процесс исключения.
Все сказанное выше переносится без изменения и на системы уравнений произвольного порядка (2). Процесс искл!Очення можно записать формулой Е Е,...ЕАх=Е Е,... Е1, О О ... О О ... 1,'а!»»»! О ... О О ... — а~»„о»1аЦ, '! 1 ... О О ... — а!»»!/а!»» »1 О ... ! — а,„» а„ Матрица Е, осуществляет исключение неизвестного х, нз уравнений с номерами к+1, к+2, ..., вк Матрицы Е»' существуют и имеют вид 1 ° ° О О ... О О ... а! '! О ... О О ... а!,"„-,'„' ! ... О Е»' = 4 3. Метод Гаусса с выбором главного элемента 1. Основная идея метода. Может оказаться, что система Ах=( имеет единственное решение, хотя какой-либо нз угловых миноров матрицы А равен нулю.
Кроме того, заранее обычно неизвестно, все ли угловые миноры матрицы А отличны от нуля. В этих случа- 60 где элементарная нижняя треугольная матрица Е, на л-м шаге исключения имеет вид ях обычный метод Гаусса может оказаться непригодным. Избежать указанных трудностей позволяет метод Гаусса с выбором главного элемента. Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь выбирается главный, т. е. наибольший по модулю элемент.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
