Численные методы
МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.
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) наряду с элементарными треугольными матрицами
могут
присутствовать элементарные матрицы перестановок .
PA=LU,
(17)
где L -нижняя треугольная матрица, имеющая обратную, P - матрица перестановок.
Для этого найдем матрицу
(18)
По свойству 2) матрица получается из матрицы перестановкой второй и
третьей строк,
Матрица согласно свойству 3)
получается из перестановкой второго и третьего
столбцов
т.е. -нижняя треугольная матрица, имеющая обратную.
Из (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) только перестановкой строк.
Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю.
Теорема доказана.