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

Далее, к системе (11) надо применить второй шаг исключении обычного метода Гаусса. Это эквивалентно умножению системы (11) на элементарную треугольную матрицу Г! 0 О! 0 !/5 0 0 — 1(5 1 В результате получим систему мли (13) + «з= > ! 1з 2 2 з «з+ «з = !з 5 5 ! й !, — — «. =1 — — — — 6. !О 2 5 «, (14) Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (14) уравнением «,= — 1О ~~,— — — — ~,), 1. ! 2 5 что эквивалентно умножению (13) на матрицу ! = О ! О Таким образом, для рассмотренного примера процесс исключения Гаусса с выбором главного элемента по столбцу записывается в виде (16) По построению матрица И= 1.,1.,Р„1.,Р„А (16) (17) где Г.— нижняя треугольная матрица, имеющая обратную, и Р— матрица перестановок.

Для этого найдем матрицу х ~ =Рм7.1Рм. (18) По свойству 2' матрица Р„Е, получается нз матрицы (., переста- новкой второй и третьей строк, ! 0 0 2 о о — !/2 ! 0 является верхней треугольной матрицей с единичной главной диагональю. Отличие от обычного метода Гаусса состоит в том, что в качестве сомножителей в (16) наряду с элементарными треугольными матрицами Е„могут присутствовать элементарные матрицы перестановок Р„. Покажем еще, что из (16) следует разложение РА=Ш, Матрица Е! согласно свойству 3' получается из Р„Е, перестановкой второго и третьего столбцов, ! — О О 2 О ! Π— !/2 О ! т.

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

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

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

3 А. А. Самарский. А. В. Гумми где !ты. Переставляя в матрице А строки с номерами ! и ш, получим матрицу Р, А, у которой угловой минор порядка и†! имеет вид оп ° .. а и отличается от (23) только перестановкой строк. Следовательно, этот минор не равен нулю н мы приходим к рассмотренному выше случаю. 6. Вычисление определителя. В большинстве существующих стандартных программ одновременно с решением системы линейных алгебраических уравнений (1) вычисляется определитель матрицы А.

Пусть в процессе исключения найдено разложение (22), т. е. построены матрицы Т. и У. Тогда бе1(РА) =бе1Т. йе1 У=бе1Ь=(,Ах...1 т. е. произведение диагональных элементов матрицы Е равно определителю матрицы РА. Поскольку матрицы РА и А отличаются только перестановкой строк, определитель матрицы РА может отличаться от определителя матрицы А только знаком.

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

Действительно, рассмотрим укороченную систему (см. (11) из $1), которая получается на Й-м шаге исключения: айаиха+... +ай их =)ча ~~, ~а-ох (а-н "а-и аа„,ьха+ ... + аа х,„=г"а„, (24) а„а ха+ ... + а х =1„ ~а-и <а-и !й-и При решении системы (24) могут возникнуть два случая: 1) хотя бы один из коэффициентов аьч, па+па,..., а ч отличен от ~а~ а-и нуля; 2) а~~~ "=а~~,',~ь=... =а'",~а=О. Если для всех й=1, 2, ... ..., т реализуется первый случай, то систему (1) можно решить методом Гаусса с выбором главного элемента по столбцу, и, следовательно, бе1АФО. Если же бе1 А =О, то при некотором й реализуется второй случай. При этом дальнейшее исключение становится невозможным и программа должна выдать информацию о том, что определитель матрицы равен нулю. Зч Ьу $4.

Обращение матрицы Нахождение матрицы, обратной матрице А, эквивалентно решению матричного уравнения АХ=Е, (1) где Š— единичная матрица и Х вЂ” искомая квадратная матрица. Пусть А= [ао], Х= [хо]. Уравнение (1) можно записать в виде системы т' уравнений (2) '~ амхм=бп, 1,1=1,2,...,т, в з где бя=! прн 1=1 и бе — — 0 при!чь). Для дальнейшего важно заметить, что система (2) распадается на т независимых систем уравнений с одной и той же матрицей А, но с различными правыми частями. Эти системы имеют вид Ах"'=6"', 1=1, 2, ..., т, (3) где х"'= (ха, хзь ..., х;)', у вектора 6"> равна единице /-я компонента и равны нулю остальные компоненты. Например, для матрицы второго порядка система (2) распадается ня две независимые системы аыхм+ аыхм = 1, аыхм+ а,зхез = О, и азгхгг+ аззхзг — О азгхгз+ аззхзз = 1.

Для решения систем (3) используется метод Гаусса (обычный или с выбором главного элемента). Рассмотрим применение метода Гаусса без выбора главного элемента. Поскольку все системы (3) имеют одну и ту же матрицу А, достаточно один раз совершить прямой ход метода Гаусса, т. е. получить разложение А=(.с! и запомнить матрицы Ь и У. Для этого, как мы знаем (см. ф 1), требуется сделать т(т* — 1)/3 действий умножения и деления. Обратный ход осуществляется путем решения систем уравнений ЕФ'=6О', И1г'=(Ум,Ум,...,д 1)', (4) Ухн1=уц1, /=1,2,...,т, (5) с треугольными матрицами Е и (г'. Решение системы (5) при каждом 1 требует 0,5 т(т — 1) действий. Для решения системы (4) надо еще добавить т делений на диагональные элементы матрицы Л, так что здесь потребуется 0,5т(т+1) умножений и делений.

Всего при каждом 1 на обратный ход затрачивается 0,5(т — 1) т+ +0,5(т+1)т=тз действий, а для всех / требуется т* действий. Можно сократить число действий, принимая во внимание специальный вид правых частей системы (4). Запишем подробнее пер- ва вые 1 — 1 уравнений системы (4): („у„= О, (мум + 1ваум = О, (,,„д„+1,, у,)+... +1; ...у...=О. Учитывая невырожденность матрицы Е, отсюда получим до=ум=...=у~ о=о.

При этом оставшиеся уравнения системы (4) имеют вид 1ддд=1, (нд„+1,,„у,„,, + ... +1пд„=О, 1=1+1, 1+2, ..., т. Отсюда последовательно находятся неизвестные уч по формулам 'Я ),д уд = — =', 1=1+1,1+ 2,..., и, (6) 1и уп= Ипь (?) Подсчитаем число умножений и делений, необходимое для про- ведения вычислений по формулам (6). При фиксированном 1 для вычислений по формуле (6) требуется 1 деление и 1 — 1 умножений. Вычисления по формулам (6), (?) при фиксированном 1 потребуют +,~ ..+ (я — 1+2) (т — 1+1) 2 8 )+ъ действий. Наконец, решение указанным способом систем (4) при всех 1=1, 2,..., и потребует — „"~~~ (т — 1+2) (и — у+1) = — ~ч', й(й+1) = 2 2 6 /=1 й-1 действий.

Общее число действий умножения н деления, необходи- мое для обращения матрицы указанным способом, е (иР— !) иР (я — )) т (т+ 1) (т+ 2) 3 2 6 Тем самым обращение матрицы требует не намного больше времени, чем решение системы уравнений. 5 5.Метод квадратного корня 1. Факторизация эрмитовой матрицы. Метод предназначен для решения систем уравнений Ах=) (1) 99 с симметричной (в комплексном случае — эрмитовой) матрицей.

Он основан на разложении матрицы А в произведение А = 5*Р5, (2) где 5 — верхняя треугольная матрица с положительными элементами на главной диагонали, 5' — транспонированная к ней (или комплексно сопряженная) матрица, Р— диагональная матрица, на диагонали которой находятся числа, равные -!-1. Возможность представления (2) можно получить как следствие теоремы об (.У-разложении (см.

$2). Пусть все угловые миноры матрицы А отличны от нуля. Тогда справедливо разложение А=(.У, где (.— нижняя треугольная матрица, имеющая обратную, и У вЂ” верхняя треугольная с единичной диагональю. Представим матрицу (. в виде произведения (.=МК, где М вЂ” нижняя треугольная матрица с единичной главной диагональю и К вЂ” диагональная матрица, главная диагональ которой совпадает с главной диагональю матрицы (., т.е.