Описание метода Гаусса

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

Ax=b, (1.1)

где – вектор неизвестных; – вектор свободных членов; , – невырожденная матрица размерами .

В силу невырожденности матрицы A для однородной системы уравнений с вектором правых частей имеем единственное тривиальное решение . Для неоднородной системы имеем единственное решение , где A^-1 – матрица, обратная A.

В курсе высшей математики решение СЛАУ (1.1) обычно выражают по формулам Крамера в виде отношений определителей. Для решения СЛАУ больших порядков эти формулы непригодны, т.к. требуют вычисления (n+1) определителей, а вычисление каждого определителя требует числа арифметических действий порядка n!. В силу того, что n! чрезвычайно быстро растет с увеличением n, решение СЛАУ, например, порядка 100 по формулам Крамера не может быть получено за приемлемое время ни на одной из существующих ЭВМ. На практике требуется решать СЛАУ порядка n=10³ и выше. Другая причина неприменимости формул Крамера на ЭВМ – катастрофический рост ошибок округления, называемый численной неустойчивостью. Алгоритм метода исключения неизвестных был изобретен в 3 веке до нашей эры, хотя и носит имя Гаусса. Идея алгоритма состоит в приведении СЛАУ к эквивалентной ей системе с треугольной матрицей (прямой ход исключения), а затем к нахождению неизвестных последовательными подстановками (обратный ход). Данный метод требует числа арифметических операций порядка . Он используется для решения СЛАУ с . Объединим матрицу А и вектор b в расширенную матрицу размерами n ´ (n +1), которая содержит всю известную информацию о системе (1.1).

.

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

Введем обозначение для i -й строки матрицы

.

C матрицей можно обращаться так же, как с исходной системой (1.1), например, осуществлять элементарные преобразования. В качестве последних будем использовать перестановки строк, прибавление к элементам данной строки элементов какой-либо другой строки, умноженных на одно и то же число. Найдем ненулевой элемент в первом столбце матрицы . Такой элемент найдется всегда ибо, в противном случае, весь первый столбец состоит из нулей и матрица – вырожденная. Пусть , тогда поменяем местами строки номера r и 1. Если , то, естественно, перестановка не требуется. Затем вычтем из каждой строки номера i, первую строку, умноженную на число , где

.

В результате все элементы i -ой строки изменят свои значения и эта строка принимает следующий вид:

.

В итоге матрица принимает вид

. (1.2)

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

Применение этого алгоритма j раз приводит к матрице

.

В матрице полученные нули располагаются в столбцах с номерами от 1 до j ниже диагонали. Эти нули сохраняются во время следующих шагов алгоритма.

В результате применения алгоритма n раз система (1.1), в конечном счете, преобразуется в

Rx=C, (1.3)

где R – верхняя (правая) треугольная матрица, т.е.

. (1.4)

Значения неизвестных можно вычислить из (1.4) по формулам

,

, . (1.5)

Процесс приведения системы (1.1) к треугольному виду (1.3) называется прямым ходом, а нахождение неизвестных по формулам (1.5) называется обратным ходом.

Произведем подсчет числа арифметических операций в методе Гаусса. Число арифметических операций, необходимое для реализации прямого хода в методе Гаусса для решения систем уравнений порядка n, равно

. (1.6)

При обратном ходе

. (1.7)

Из формул (1.6) и (1.7) получаем оценку общего числа арифметических действий

.

Если имеется p систем вида (1.1) с одинаковыми матрицами A и разными правыми частями b₁, b₂, …, b_p, то целесообразно прямой ход осуществлять для всех систем одновременно, для чего следует вместо одной правой части, задаваемой вектором-столбцом, производить операции над p правыми частями (матрицей порядка ). Количество арифметических операций, необходимое для реализации прямого хода метода Гаусса с учетом (1.6) и (1.7), есть

.

Количество арифметических операций, необходимое для реализации p обратных ходов (для p систем) методом Гаусса, есть , откуда следует, что общее количество арифметических операций, необходимое для реализации p систем с разными правыми частями, равно

.