Из (18), учитывая равенство
, получим (19)Отсюда и из (16) видно, что
где обозначено
. Поскольку Р-матрица перестановок и L-нижняя треугольная матрица, свойство (17) доказано. Оно означает, что метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к матрице РА, т.е. к системе, полученной из исходной системы перестановкой некоторых уравнений.3. Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (1).
А именно, метод Гаусса с выбором главного элемента по столбцу можно записать в виде
(20)где
- элементарные матрицы перестановок такие, что и -элементарные нижние треугольные матрицы.Отсюда, используя соотношения перестановочности, аналогичные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к системе
PAx=Pf, (21)
где Р - некоторая матрица перестановок.
Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме.
ТЕОРЕМА 1. Если
то существует матрица перестано-вок Р такая, что матрица РА имеет отличные от нуля угловые ми-
норы.
Доказательство в п.4.
СЛЕДСТВИЕ.Если
то существует матрица престана-вок Р такая, что справедливо разложение
РА=LU, (22)
где L-нижняя треугольная матрица с отличными от нуля диагональными элементами и U- верхняя треугольная матрица с единичной главной диагональю. В этом случае для решения системы (1) можно применять метод Гаусса с выбором главного элемента.
4. Доказательство теоремы 1. Докажем теорему индукцией по числу m -порядку матрицы А.
Пусть m=2, т.е.
Если
то утверждение теоремы выполняется при Р=Е, где Е - единичная матрица второго порядка. Если , то , т.к. При этом у матрицывсе угловые миноры отличны от нуля.
Пусть утверждение теоремы верно для любых квадратных матриц порядка m-1. Покажем, что оно верно и .для матриц порядка m. Разобьем матрицу А порядка m на блоки
где
Достаточно рассмотреть два случая :
и . В первом случае по предположению индукции существует матрица перестановок порядка m-1 такая, что имеет отличные от нуля угловые миноры. Тогда для матрицы перестановокимеем
причем
. Тем самым все угловые миноры матрицы РА отличны от нуля.Рассмотрим второй случай, когда
. Т.к. , найдется хотя бы один отличный от нуля минор порядка m-1 матрицы А, полученный вычеркиванием последнего столбца и какой-либо строки. Пусть, например,где
.Переставляя в матрице А строки с номерами l и m,получим матрицу
, у которой угловой минор порядка m-1 имеет види отличается от (23) только перестановкой строк. Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю.
Теорема доказана.
ВЫЧИСЛЕНИЕ ОПРЕДЕЛИТЕЛЯ МЕТОДОМ ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.
Одновременно с решением системы линейных алгебраических уравнений
можно вычислить определитель матрицы А.
Пусть в процессе исключения найдено распожение
т.е. построены матрицы L èU . Тогда
и, таким образом, произведение диагональных елементов матрицы L (ведущих, главных елементов метода исключения) равно определителю матрицы РА. Поскольку матрицы РА и А отличаются только перестановкой строк, определитель матрицы РА может отличаться от определителей матрицы А только знаком.
А именно,
Таким образом, для вычисления определителя необходимо знать, сколько перестановок было осуществлено в процессе сключения.
Если матрица А выроджена, то при использовании метод Гаусса с выбором главного элемента по столбцу на некотором шаге исключения К все элементы которого столбца, находящиеся ниже главной диагонали и на ней, окажутся равными нулю.При этом дальнейшее исключение становится невозможным и программа должна выдать информацию о том, что определитель матрицы равен нулю.
ОБРАЩЕНИЕ МАТРИЦ.
Нахождение матрицы, обратной матрице А , еквивалентно решению матричного уравнения
(1)где Е - единичная матрица, X - искомая квадратная матрица.
Уравнение (1) можно записать в виде системы
уравнений (2)где
Можно заметить, что система (2) распадается на m независимых систем уравнений с одной и той же матрицей А , но с различными правыми частями. Эти системы имеют
вид ( фиксируем j ) :
(3)где
у вектора - столбца равна единице j-та компонента и равны нулю остальные компоненты.Например, для матрицы второго порядка система (2) распадается на две независимые системы:
Äëÿ ðåøåíèÿ систем (3) используется метод Гаусса ( обычный или с выбором главного элемента).
Рассмотрим применение метода Гаусса без выбора главного элемента. Поскольку все системы (3) имеют одну и ту же матрицу А , достаточно один раз совершить прямой ход метода Гаусса, т.е. получить разложение A=LU и запомнить матрицы L i U .
Обратный ход осуществляется путем решения систем уравнений
с треугольными матрицами L è U.
При осуществлении обратного хода можно сократить число действий, принимая во внимание специальный вид правых частей системы (4).
Запишем подробнее первые j-1 уравнений системы (4):
Учитывая невырожденность матрицы L ( т.е.
отсюда получаем
При этом оставшиеся уравнения системы (4) имеют вид
Отсюда последовательно находятся неизвестные
по формулам: