Численные методы

Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений (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) матрица Матрица перестановкой второго и третьего столбцов т.е. Из (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) только перестановкой строк.