Численные методы
(17)
так, що
.При
цьому систему
(16) можна записати
у вигляді
.
Матрицю (17) будемо називати елементарною трикутною матрицею, що відповідає першому кроку виключення методу Гаусса.
Перепишемо систему (16) у вигляді
,
, (18)
.
Здійснимо
другий крок
методу Гаусса,
тобто виключимо
невідому
з останнього
рівняння.
Тоді одержимо систему вигляду
,
, (19)
.
Можна переконатися,що перехід від (18) до (19) здійснюється завдяки множення системи (18) на елементарну трикутну матрицю
. (20)
Таким чином,після другого кроку виключення приходимо до системи
,
(21)
де матриці
і
означені згідно
(17), (20).
Нарешті, перемножаючи (21) на матрицю

одержимо систему
, (22)
матриця
якої
є верхньою
трикутною
матрицею з
одиничною
головною діагоналлю.
Звідки
виходить, зокрема,
що A=LU,
де
-нижня
трикутна матриця.
Таким
чином,
-розклад матриці
А
може бути одержаний
за допомогою
елементарних
трикутних
матриць: спочатку
будуються
матриці
та обчислюється
,
а потім відшукується
.Відзначимо,
що матриці
мають простий
вигляд
;
;
;
.
причому на діагоналі матриці містяться ведучі елементи методу виключення.
Запис методу Гаусса у вигляді (22) детально описує процес виключення.
Усе згадане раніш переноситься без винятку на системи рівнянь довільного порядку (2).
Процес виключення можна записати формулою
, (23)
де елементарна
нижня трикутна
матриця
на к-му
кроці виключення
має вигляд
.
Матриця
здійснює виключення
невідомого
з рівнянь з
номерами
к+1, к+2, ... ,m.
Матриці
існують і мають
вигляд
.
МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.
Основная идея метода. Может оказаться, что система
Ax=f (1)
имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. В этом случае обычный метод Гаусса оказывается непригодным, но может быть применен метод Гаусса с выбором главного элемента.
Основная
идея метода
состоит в том,
чтобы на очередном
шаге исключать
не следующее
по номеру
неизвестное,
а то
неизвестное,
коэффициент
при котором
является наибольшим
по модулю. Таким
образом, в качестве
ведущего элемента
здесь выбирается
главный,
т.е. наибольший
по модулю элемент.
Тем самым, если
,
то в процессе
вычислений
не будет происходить
деление на
нуль.
Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений
(2)
![]()
![]()
![]()
Предположим,
что
.
Тогда на первом
шаге будем
исключать
переменное
.
Такой прием
эквивалентен
тому, что система
(2) переписывается
в виде
(3)
![]()
и к (3) применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация переменных.
Применяется
также метод
Гаусса с выбором
главного элемента
по столбцу.
Предположим,
что
.
Перепишем
систему (2) в
виде
![]()
и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений.
Иногда применяется и метод Гаусса с выбором главного элемента по всей матрице, когда в качестве ведущего выбирается максимальный по модулю элемент среди всех элементов матрицы системы.
Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде
![]()
где
-элементарные
нижние треугольные
матрицы. Чтобы
получить аналогичную
запись метода
Гаусса с выбором
главного элемента,
необходимо
рассмотреть
матрицы перестановок.
ОПРЕДЕЛЕНИЕ 1. Матрицей перестановок Р называется квадратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице.
ОПРЕДЕЛЕНИЕ
2.
Элементарной
матрицей перестановок
называется
матрица, полученная
из единичной
матрицы перестановкой
к-й
и l-й
строк.
Например, элементарными матрицами перестановок третьего порядка являются матрицы
Можно отметить следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения .
Произведение двух (а следовательно, и любого числа) элементарных матриц перестановок является матрицей перестановок (не обязательно элементарной).
Для любой квадратной матрицы А матрица
отличается
от А
перестановкой
к-й
и
l-й
строк.Для любой квадратной матрицы А матрица
отличается
от А
перестановкой
к-го
и l-го
столбцов.
Применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу можно пояснить на следующем примере системы третьего порядка:
(4)
Система имеет вид (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)
получается
из