МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.
1. Основная идея метода. Может оказаться, что система
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) получается из перестановкой
второго и третьего столбцов
т.е. -нижняя треугольная матрица, имеющая обратную.
Из (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) только перестановкой строк. Следовательно, этот минор
не равен нулю и мы приходим к рассмотренному выше случаю.
Теорема доказана.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
