Метод гаусса с выбором главного элемента




Скачать 92.03 Kb.
НазваниеМетод гаусса с выбором главного элемента
Дата публикации16.03.2013
Размер92.03 Kb.
ТипДокументы
vbibl.ru > Математика > Документы
МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.


  1. Основная идея метода. Может оказаться, что система

Ax=f (1)

имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. В этом случае обычный метод Гаусса оказывается непригодным, но может быть применен метод Гаусса с выбором главного элемента.

Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь выбирается главный, т.е. наибольший по модулю элемент. Тем самым, если , то в процессе вычислений не будет происходить деление на нуль.

Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений

(2)



Предположим, что . Тогда на первом шаге будем исключать переменное . Такой прием эквивалентен тому, что си­стема (2) переписывается в виде

(3)



и к (3) применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения про­водится соответствующая перенумерация переменных.

Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что . Перепишем систему (2) в виде




и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений.

Иногда применяется и метод Гаусса с выбором главного элемента по всей матрице, когда в качестве ведущего выбирается максималь­ный по модулю элемент среди всех элементов матрицы системы.

  1. Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде



где -элементарные нижние треугольные матрицы. Чтобы получить аналогичную запись метода Гаусса с выбором главного элемента, необходимо рассмотреть матрицы перестановок.

ОПРЕДЕЛЕНИЕ 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) получается из перестановкой второго и третьего столбцов



т.е. -нижняя треугольная матрица, имеющая обратную.

Из (18), учитывая равенство , получим

(19)

Отсюда и из (16) видно, что



где обозначено . Поскольку Р-матрица перестановок и L-нижняя треугольная матрица, свойство (17) доказано. Оно означает, что метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к мат­рице РА, т.е. к системе, полученной из исходной системы перестанов­кой некоторых уравнений.

  1. ^ Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (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) только перестановкой строк. Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю.

Теорема доказана.

Добавить документ в свой блог или на сайт

Похожие:

Метод гаусса с выбором главного элемента iconРобоча програма по дисципліні Чисельні методи
Численные методы решения систем линейных алгебраических уравнений. Правило Крамера, метод обращения матрицы, метод Гаусса

Метод гаусса с выбором главного элемента icon1. Прямой ход Гаусса Обратный ход Гаусса
Чем больше норма обратной матрицы а-1, тем на меньшую точность можно расчитывать

Метод гаусса с выбором главного элемента iconВсеобщие законы бытия и философский метод
Однако для всех значений элемента обще то, что элемент вещи есть ее первооснова

Метод гаусса с выбором главного элемента iconПроверка условий Гаусса-Маркова
Для того чтобы регрессионный анализ, основанный на обычном мнк, давал наилучшие результаты, случайный член должен удовлетворять четырём...

Метод гаусса с выбором главного элемента iconЗадача о назначении Эпсилон-метод Венгерский метод Задачи нелинейного...
Зпр в условиях определенности, когда альтернатива всегда приводит к какому-нибудь конкретному исходу

Метод гаусса с выбором главного элемента iconКак я читали этот школьная учебники
Резерфорда голландский юрист Ван дер Брук выяснил, что заряд ядра атома, как раз равен порядковому номеру элемента в таблице. Таким...

Метод гаусса с выбором главного элемента iconДолжностная инструкция главного (ведущего) специалиста общие положения
Главный (ведущий) специалист находится в непосредственном подчинении главного бухгалтера и заместителя главного бухгалтера

Метод гаусса с выбором главного элемента iconЭлемента в архитектуре пк (рис. 5)
Процессор современного персонального компьютера (Central Processor Unit, cpu) представляет собой небольшую интегральную микросхему,...

Метод гаусса с выбором главного элемента iconКурс: 4 Тип: курсовая работа Прибыль и ее роль в рыночной экономике Содержание
Метод прямого счета, аналитический метод и метод совмещенного расчета

Метод гаусса с выбором главного элемента iconВопросы к зачету по курсу
Понятия статистической совокупности и единицы (элемента) совокупности. Понятие признака элемента совокупности. Понятия статистического...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
vbibl.ru
Главная страница