МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.
1. Основная идея метода. Может оказаться, что система
Ax=f(1)
имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. В этом случае обычный метод Гаусса оказывается непригодным, но может быть применен метод Гаусса с выбором главного элемента.
Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а тонеизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь выбирается главный, т.е. наибольший по модулю элемент. Тем самым, если , то в процессе вычислений не будет происходить деление на нуль.
Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений
(2) Предположим, что . Тогда на первом шаге будем исключать переменное . Такой прием эквивалентен тому, что система (2) переписывается в виде (3)и к (3) применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация переменных.
Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что
. Перепишем систему (2) ввидеи к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений.
Иногда применяется и метод Гаусса с выбором главногоэлемента повсей матрице, когда в качестве ведущего выбирается максимальный по модулю элемент среди всех элементов матрицы системы.
2. Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде
где
-элементарные нижние треугольные матрицы. Чтобы получить аналогичную запись метода Гаусса с выбором главного элемента, необходимо рассмотреть матрицы перестановок.ОПРЕДЕЛЕНИЕ 1.Матрицей перестановок Р называется квадратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице.
ОПРЕДЕЛЕНИЕ 2.Элементарной матрицей перестановок
называется матрица, полученная из единичной матрицы перестановкой к-й и l-й строк.Например, элементарными матрицами перестановок третьего порядка являются матрицы
Можно отметить следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения.
1) Произведение двух (а следовательно, и любого числа) элементарных матриц перестановок является матрицей перестановок (не обязательно элементарной).
2) Для любой квадратной матрицы А матрица
отличается от А перестановкой к-й иl-é ñòðîê.3) Для любой квадратной матрицы А матрица
отличается от А перестановкой к-го и 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) получается из перестановкой второго и третьего столбцовт.е.
-нижняя треугольная матрица, имеющая обратную.