Численные методы
Система имеет вид (1), где
(5)
Максимальный элемент первого столбца матрицы А находится во второй строке. Поэтому надо поменять местами вторую и первую строки и перейти к эквивалентной системе
(6)
Систему (6) можно записать в виде
(7)
т.е. она получается из системы (4) путем умножения на матрицу
перестановок
Далее, к системе (6) надо применить первый шаг обычного метода исключения Гаусса. Этот шаг эквивалентен умножению системы (7) на элементарную нижнюю треугольную матрицу

В результате от системы (7) перейдем к эквивалентной системе
(8)
или в развернутом виде
(9)
Из последних
двух уравнений
системы (9) надо
теперь исключить
переменное
.
Поскольку
максимальным
элементом
первого столбца
укороченной
системы
(10)
является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе
(11)
которую можно записать в матричном виде как
.
(12)
Таким образом система (12) получена из (8) применением элемен-тарной матрицы перестановок

Далее к системе (11) надо применить второй шаг исключения обычного метода Гаусса. Это эквивалентно умножению системы (11) на элементарную нижнюю треугольную матрицу

В результате получим систему
(13)
или
(14)
Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (14) уравнением

что эквивалентно умножению (13) на элементарную нижнюю треугольную матрицу

Таким образом, для рассмотренного примера процесс исключения Гаусса с выбором главного элемента по столбцу записывается в
виде
(15)
По построению матрица
(16)
является верхней треугольной матрицей с единичной главной диагональю.
Отличие
от обычного
метода Гаусса
состоит в том,
что в качестве
сомножителей
в (16) наряду с
элементарными
треугольными
матрицами
могут
присутствовать
элементарные
матрицы перестановок
.
Покажем еще, что из (16) следует разложение
PA=LU, (17)
где L -нижняя треугольная матрица, имеющая обратную, P - матрица перестановок.
Для этого найдем матрицу
(18)
По свойству
2) матрица
получается
из матрицы
перестановкой
второй и третьей
строк,
Матрица
согласно
свойству 3)
получается
из
перестановкой
второго и третьего
столбцов

т.е.
-нижняя
треугольная
матрица, имеющая
обратную.
Из (18), учитывая
равенство
,
получим
(19)
Отсюда и из (16) видно, что
![]()
где обозначено
.
Поскольку
Р-матрица
перестановок
и L-нижняя
треугольная
матрица, свойство
(17) доказано. Оно
означает, что
метод Гаусса
с выбором главного
элемента по
столбцу эквивалентен
обычному методу
Гаусса, примененному
к матрице РА,
т.е. к системе,
полученной
из исходной
системы перестановкой
некоторых
уравнений.
Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (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) только перестановкой строк. Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю.
Теорема доказана.