Материалы сайта
Это интересно
Численные методы
МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА. 1. Основная идея метода. Может оказаться, что система Ax=f (1) имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. В этом случае обычный метод Гаусса оказывается непригодным, но может быть применен метод Гаусса с выбором главного элемента. Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь выбирается главный, т.е. наибольший по модулю элемент. Тем самым, если [pic], то в процессе вычислений не будет происходить деление на нуль. Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений [pic] (2) [pic] [pic][pic][pic]Предположим, что [pic]. Тогда на первом шаге будем исключать переменное [pic]. Такой прием эквивалентен тому, что система (2) переписывается в виде [pic] (3) [pic] и к (3) применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация переменных. Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что [pic]. Перепишем систему (2) в виде [pic] [pic] и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений. Иногда применяется и метод Гаусса с выбором главного элемента по всей матрице, когда в качестве ведущего выбирается максимальный по модулю элемент среди всех элементов матрицы системы. Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде [pic] [pic] где [pic]-элементарные нижние треугольные матрицы. Чтобы получить аналогичную запись метода Гаусса с выбором главного элемента, необходимо рассмотреть матрицы перестановок. ОПРЕДЕЛЕНИЕ 1. Матрицей перестановок Р называется квадратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице. ОПРЕДЕЛЕНИЕ 2. Элементарной матрицей перестановок [pic]называется матрица, полученная из единичной матрицы перестановкой [pic]к-й и l-й строк. Например, элементарными матрицами перестановок третьего порядка являются матрицы [pic] Можно отметить следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения . Произведение двух (а следовательно, и любого числа) элементарных матриц перестановок является матрицей перестановок (не обязательно элементарной). Для любой квадратной матрицы А матрица [pic]отличается от А перестановкой к-й и l-й строк. Для любой квадратной матрицы А матрица [pic]отличается от А перестановкой к-го и l-го столбцов. Применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу можно пояснить на следующем примере системы третьего порядка: [pic] (4) Система имеет вид (1), где [pic] (5) Максимальный элемент первого столбца матрицы А находится во второй строке. Поэтому надо поменять местами вторую и первую строки и перейти к эквивалентной системе [pic] (6) Систему (6) можно записать в виде [pic] (7) т.е. она получается из системы (4) путем умножения на матрицу перестановок [pic] Далее, к системе (6) надо применить первый шаг обычного метода исключения Гаусса. Этот шаг эквивалентен умножению системы (7) на элементарную нижнюю треугольную матрицу [pic] В результате от системы (7) перейдем к эквивалентной системе [pic] (8) или в развернутом виде [pic] (9) Из последних двух уравнений системы (9) надо теперь исключить переменное [pic]. Поскольку максимальным элементом первого столбца укороченной системы [pic] (10) является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе [pic] (11) которую можно записать в матричном виде как [pic]. (12) Таким образом система (12) получена из (8) применением элемен-тарной матрицы перестановок [pic] Далее к системе (11) надо применить второй шаг исключения обычного метода Гаусса. Это эквивалентно умножению системы (11) на элементарную нижнюю треугольную матрицу [pic] В результате получим систему [pic] (13) или [pic] (14) Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (14) уравнением [pic] что эквивалентно умножению (13) на элементарную нижнюю треугольную матрицу [pic] Таким образом, для рассмотренного примера процесс исключения Гаусса с выбором главного элемента по столбцу записывается в виде [pic] (15) По построению матрица [pic] (16) является верхней треугольной матрицей с единичной главной диагональю. Отличие от обычного метода Гаусса состоит в том, что в качестве сомножителей в (16) наряду с элементарными треугольными матрицами [pic]могут присутствовать элементарные матрицы перестановок [pic]. Покажем еще, что из (16) следует разложение PA=LU, (17) где L -нижняя треугольная матрица, имеющая обратную, P - матрица перестановок. Для этого найдем матрицу [pic] (18) По свойству 2) матрица [pic]получается из матрицы [pic]перестановкой второй и третьей строк, [pic] Матрица [pic]согласно свойству 3) получается из [pic] перестановкой второго и третьего столбцов [pic] т.е. [pic]-нижняя треугольная матрица, имеющая обратную. Из (18), учитывая равенство [pic], получим [pic] (19) Отсюда и из (16) видно, что [pic] где обозначено [pic]. Поскольку Р-матрица перестановок и L-нижняя треугольная матрица, свойство (17) доказано. Оно означает, что метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к матрице РА, т.е. к системе, полученной из исходной системы перестановкой некоторых уравнений. Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (1). А именно, метод Гаусса с выбором главного элемента по столбцу можно записать в виде [pic] (20) где [pic]- элементарные матрицы перестановок такие, что [pic] и [pic]-элементарные нижние треугольные матрицы. Отсюда, используя соотношения перестановочности, аналогичные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к системе PAx=Pf, (21) где Р - некоторая матрица перестановок. Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме. ТЕОРЕМА 1. Если [pic]то существует матрица перестано- вок Р такая, что матрица РА имеет отличные от нуля угловые ми- норы. Доказательство в п.4. СЛЕДСТВИЕ. Если [pic]то существует матрица престана- вок Р такая, что справедливо разложение РА=LU, (22) где L- нижняя треугольная матрица с отличными от нуля диагональными элементами и U- верхняя треугольная матрица с единичной главной диагональю. В этом случае для решения системы (1) можно применять метод Гаусса с выбором главного элемента. 4. Доказательство теоремы 1. Докажем теорему индукцией по числу m -порядку матрицы А. Пусть m=2, т.е. [pic] Если [pic] то утверждение теоремы выполняется при Р=Е, где Е - единичная матрица второго порядка. Если [pic], то [pic], т.к. [pic]При этом у матрицы [pic] все угловые миноры отличны от нуля. Пусть утверждение теоремы верно для любых квадратных матриц порядка m- 1. Покажем, что оно верно и .для матриц порядка m. Разобьем матрицу А порядка m на блоки [pic] где [pic][pic] [pic] Достаточно рассмотреть два случая :[pic] и [pic]. В первом случае по предположению индукции существует матрица перестановок [pic]порядка m-1 такая, что [pic]имеет отличные от нуля угловые миноры. Тогда для матрицы перестановок [pic] имеем [pic] причем [pic]. Тем самым все угловые миноры матрицы РА отличны от нуля. Рассмотрим второй случай, когда[pic] . Т.к.[pic] , найдется хотя бы один отличный от нуля минор порядка m-1 матрицы А, полученный вычеркиванием последнего столбца и какой-либо строки. Пусть, например, [pic] где [pic]. Переставляя в матрице А строки с номерами l и m, получим матрицу [pic], у которой угловой минор порядка m-1 имеет вид [pic] и отличается от (23) только перестановкой строк. Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю. Теорема доказана.
1 2 3 4 5 6 7 8 9 10 11 12 13 14