Метод Гаусса. Методом Гаусса называют точный метод решения невырожденной системы линейных уравнений, состоящий в том

Методом Гаусса называют точный метод решения невырожденной системы линейных уравнений, состоящий в том, что последовательным исключением неизвестных систему

, ,

приводят к эквивалентной системе с верхней треугольной матрицей

решение которой находят по рекуррентным формулам

, , .

Существует много вариантов этого метода. Рассмотрим схему единственного деления. Она эффективна, когда максимальные по модулю коэффициенты уравнений находятся на главной диагонали матрицы. Это положительно определенные матрицы и матрицы, обладающие свойством диагонального преобладания:

.

Пусть исходная система имеет вид

(1)

Предположим, что , и разделим обе части первого уравнения системы на . В результате получим

, (2)

где , , . С помощью уравнения (2) исключим во всех уравнениях системы (1), начиная со второго, слагаемые, содержащие . Для этого умножаем обе части уравнения (2) последовательно на и вычитаем соответственно из второго, третьего,...., -го уравнения системы (1). В результате получаем систему, порядок которой на единицу меньше порядка исходной системы:

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

(3)

которая эквивалентна системе (1) и легко решается. Найденное из последнего уравнения подставляют в предпоследнее уравнение и находят , затем , и т.д. до , которое находят из первого уравнения системы, когда уже известны .

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

На рис.4.1 и 4.2 представлены алгоритмы прямого хода и обратного хода при решении системы.

Рис.4.1 – прямой ход алгоритма решения системы линейных

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

выбором ведущего коэффициента по столбцу

Рис.4.2 – обратный ход алгоритма решения системы линейных

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

выбором ведущего коэффициента по столбцу

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

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

В схеме полного выбора (выбор главного элемента по всей матрице) допускается нарушение естественного порядка исключения неизвестных. На первом шаге среди определяют максимальный по модулю элемент . Первое уравнение системы и уравнение с номером меняют местами. Далее исключают неизвестное из всех уравнений, кроме первого. На -м шаге среди при неизвестных в уравнениях с номерами выбирают максимальный по модулю коэффициент . Затем -е уравнение и уравнение, содержащее , меняют местами и исключают из уравнений с номерами . На этапе обратного хода неизвестные вычисляют в следующем порядке: .

Другой вариант метода Гаусса приводит к системе с обратной матрицей коэффициентов. Если , то можно разрешить первое из уравнений системы (1) относительно и подставить это выражение в остальные уравнения. В результате получим систему

(4)

где , , , , . На следующем шаге при условии, что , исключают переменную из правых частей уравнений. Если возможно выполнить таких шагов, то возникает система , т.е. выполнено обращение исходной матрицы .

Если на -м шаге матрицу коэффициентов представить в виде блоков

,

То блок размера определяет матрицу, обратную соответствующему блоку матрицы, в то время как есть матрица, обратная соответствующему блоку матрицы. Все это достаточно просто установить, если положить в первых уравнениях (1) и соответственно в последних уравнениях (4).