Файл: Маркова Вычислит методы алгебры Практикум.doc

Однако при вычислениях заранее неизвестно, все ли главные миноры матрицы А отличны от нуля. При этом может оказаться, что система (1) имеет единственное решение, несмотря на то, что какой-либо из главных миноров матрицы А равен нулю. Кроме того, фиксация ведущего элемента в случае его относительной малости может привести в процессе вычислений к сильному накоплению погрешностей. Избежать таких ситуаций позволяет метод Гаусса с выбором главного элемента.

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

На практике обычно используются следующие варианты метода Гаусса с выбором главного элемента [19]:

1) метод Гаусса с выбором главного элемента по строке. Ведущий элемент на k-ом шаге исключения выбирается как максимальный по модулю среди элементов k-ой строки. Это равносильно перенумерации переменных на каждом этапе исключения;

2) метод Гаусса с выбором главного элемента по столбцу. Ведущий элемент на k-ом шаге исключения выбирается как главный элемент k-ого столбца. Такой вариант метода Гаусса предусматривает перенумерацию уравнений на каждом этапе исключения;

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

Пример 1. Решить систему уравнений методом Гаусса с выбором главного элемента по столбцу.

Решение:

Прямой ход.

Максимальным по модулю среди элементов первого столбца является элемент второй строки . Переставим 1-е и 2-е уравнения, переместив, таким образом, выбранный элемент на место ведущего.

Проводим первый шаг исключения, как в методе Гаусса. Имеем

Максимальным по модулю среди элементов второго столбца является элемент третьей строки . Переставим 2-е и 3-е уравнения. Получим

Проводим второй шаг исключения. Имеем

Разделим третье уравнение на 6.002, получим

В результате применения обратного хода, имеем ,,.

Рассмотрим метод Гаусса с выбором главного элемента на основе факторизации.

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

Элементарной матрицей перестановок называется матрица, полученная из единичной матрицы перестановкойk-й и l-й строк.

Например, элементарными матрицами перестановок третьего порядка являются матрицы

, , .

Отметим следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения [19]:

Произведение двух (а следовательно, и любого числа) элементарных матриц перестановок является матрицей перестановок (не обязательно элементарной).
Для любой квадратной матрицы А матрица отличается отА перестановкой k-й и l-й строк.
Для любой квадратной матрицы А матрица отличается отА перестановкой k-го и l-го столбцов.

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

(3)

Матрица системы имеет вид

. (4)

Максимальный элемент первого столбца матрицы А находится во второй строке. Поэтому в системе (3) необходимо поменять местами первую и вторую строки и перейти к эквивалентной системе

(5)

Систему (5) можно записать в виде

, (6)

т.е. система (6) получается из системы (3) путем умножения на матрицу перестановок .

Далее, к системе (5) надо применить первый шаг обычного метода исключения Гаусса, для того чтобы привести матрицу системы к виду .

Этот шаг эквивалентен умножению матрицы системы (6) слева на элементарную нижнюю треугольную матрицу,

т.е. в нашем случае .

В результате от (6) перейдем к системе

. (7)

Имеем:

(8)

Из последних двух уравнений системы (8) необходимо исключить неизвестное х₂. Максимальным элементом второго столбца системы (8) является элемент третьей строки. Следовательно, в системе (8) необходимо поменять местами вторую и третью строки и тем самым перейти к эквивалентной системе (9)

(9)

которую можно записать в матричном виде как

. (10)

Таким образом, система (10) получена применением к системе (7) элементарной матрицы перестановок .

Далее, к системе (10) необходимо применить второй шаг исключения обычного метода Гаусса, для того чтобы привести матрицу системы к виду.

Этот шаг эквивалентен умножению матрицы системы (10) слева на элементарную нижнюю треугольную матрицу ,

т.е. для данного примера .

В результате получим систему

(11)

или

(12)

Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (12) уравнением

Что эквивалентно умножению (11) на матрицу ,

т.е в нашем случае .

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

. (13)

В результате получим систему

(14)

По построению матрица

(15)

является верхней треугольной матрицей с единичной главной диагональю.

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

Отличие метода Гаусса с выбором главного элемента по столбцу (строке, всей матрице) от обычного метода Гаусса состоит в том, что в качестве сомножителей в (15) наряду с элементарными треугольными матрицами L_k могут присутствовать элементарные матрицы перестановок Р_kl.

Метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к системе, полученной из исходной системы перестановкой уравнений

РАХ = Рf. (16)

Справедливо разложение [19]

РА = LU, (17)

где L – нижняя треугольная матрица с отличными от нуля диагональными элементами и U – верхняя треугольная матрица с единичной главной диагональю.

Следует подчеркнуть, что в методе Гаусса с выбором главного элемента по столбцу (строке, всей матрице) матрица Р не задается заранее, а строится в процессе исключения.

Пример 2. Описать алгоритм метода Гаусса с выбором главного элемента по столбцу на основе факторизации.

При описании алгоритма использовать объекты и методы классов «SquareMatrix», «Vector», «AugmentMatrix» и «SwapMatrix».

При реализации метода эффективнее использовать расширенную матрицу системы и проводить необходимые преобразования над ней. Приведем возможное описание класса «AugmentMatrix» (Расширенная матрица) на языке программирования С++.

/* Класс «AugmentMatrix»*/

class AugmentMatrix : public AbstractMatrix{

/* Массив элементов матрицы*/

double **elements;

/* Количество столбцов в матрице. Количество строк матрицы задавали ранее в родительском классе «AbstractMatrix» */

int СolCount;

public:

/* Конструктор класса – расширенная матрица, состоящая из квадратной матрицы и вектора */

AugmentMatrix(SquareMatrix A, Vector f);

/* Конструктор класса – расширенная матрица, состоящая из двух квадратных матриц */

AugmentMatrix(SquareMatrix A, SquareMatrix B);

/* Получение элемента по индексу*/