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

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

Ах = b,

(3.1)

где х = (х₁, х₂, … х_n)^Т – вектор неизвестных;

b = (b₁, b₂, … b_n)^Т – вектор свободных членов;

А = , i,j = 1,2,…,n – невырожденная матрица размерами n ´ n.

В силу невырожденности матрицы А (det A ¹ 0) для однородной системы уравнений с вектором правых частей b = (0, 0,…,0)^T имеем единственное тривиальное решение х=(0,0,…,0)^T. Для неоднородной системы имеем единственное решение х = А^-1b, где А^-1 – матрица, обратная А.

Алгоритм метода исключения неизвестных был изобретен в 3 веке до нашей эры, хотя и носит имя Гаусса. Идея алгоритма состоит в приведении СЛАУ к эквивалентной ей системе с треугольной матрицей (прямой ход исключения), а затем к нахождению неизвестных последовательными подстановками (обратный ход). Данный метод требует числа арифметических операций порядка 2/3 n³. Он используется для решения СЛАУ с n ~ 10²-10⁴.

Объединим матрицу А и вектор b в расширенную матрицу.

размерами n ´ (n+1), которая содержит всю известную информацию о системе (3.1).

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

Введем обозначение

а_i = (a_i1, a_i2, … a_in, b_i).

C матрицей А⁽⁰⁾ можно обращаться так же, как с исходной системой (3.1), например, осуществлять элементарные преобразования. В качестве последних будем использовать перестановки строк, прибавление к элементам данной строки элементов какой-либо другой строки, умноженных на одно и то же число.

Найдем ненулевой элемент в первом столбце матрицы А⁽⁰⁾. Такой элемент найдется всегда ибо, в противном случае, весь первый столбец состоит из нулей и матрица А – вырожденная. Пусть а_r1 ¹ 0, тогда поменяем местами строки номера r и 1. Если r = 1, то, естественно, перестановка не требуется. Затем вычтем из каждой строки номера i, i = 2, …, n первую строку, умноженную на число f_i, где

.

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

(3.2)

Здесь мы предполагаем, что хотя перестановка строк и могла состояться, однако нумерация элементов матрицы А⁽⁰⁾ осталась прежней. Введем обозначения

(3.3)

С учетом введенных обозначений (3.2) и (3.3) матрица А⁽⁰⁾ преобразуется к матрице А⁽¹⁾ и станет равной

.

(3.4)

Тот же алгоритм может быть применен на второмшаге к (n-1) ´ n матрице, которая получается из А⁽¹⁾, если убрать в ней первую строку и первый столбец. Применение этого алгоритма j раз приводит к матрице А^(j)

В матрице А^(j) полученные нули располагаются в столбцах с номерами от 1 до j ниже диагонали. Эти нули сохраняются во время следующих шагов алгоритма. В результате применения алгоритма n раз система (3.1), в конечном счете, преобразуется в систему вида

R x = C

(3.5)

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

.

(3.6)

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

xn = cn / rnn, .

(3.7)

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

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

.

(3.8)

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

QII = n(n – 1) = n2 – n.

(3.9)

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

.

Если имеется р систем вида (3.1) с одинаковыми матрицами А и разными правыми частями ,то целесообразно прямой ход осуществлять для всех систем одновременно, для чего следует вместо одной правой части, задаваемой вектором-столбцом, производить операции над р правыми частями (матрицей порядка n´p). Количество арифметических операций, необходимое для реализации прямого метода Гаусса с учетом (3.8) и (3.9), есть

.

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

.