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

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

Одним из самых распространенных методов решения систем линейных уравнений является метод Гаусса. Этот метод (который также называют методом последовательного исключения неизвестных) известен в различных вариантах уже более 2000 лет.

Описание алгоритма

Рассмотрим алгоритм на примере системы 4-х уравнений с 4-мя неизвестными.

a₁₁x₁+a₁₂ x₂+a₁₃x₃+a₁₄x₄=a_15,
a₂₁x₁+a₂₂ x₂+a₂₃ x₃+a₂₄x₄=a_25,
a₃₁x₁+a₃₂ x₂+a₃₃x₃+a₃₄x₄=a_35, (1)
a₄₁x₁+a₄₂ x₂+a₄₃x₃+a₄₄ x₄=a_45,
Пусть a₁₁ 0 (ведущий элемент). Разделив коэффициенты 1-го уравнения системы на a₁₁, получим:
x₁+b₁₂ x₂+b₁₃x₃+b₁₄x₄=b_15, (2)


(j>1).

Пользуясь уравнением (2), легко исключить из системы (1) неизвестную x₁. Для этого достаточно из 2-го уравнения системы (1) вычесть уравнение (2), умноженное на a₂₁, а из 3-го уравнения системы (1) вычесть уравнение (2), умноженное на a₃₁ и т. д. В результате получим систему из трёх уравнений:

a ⁽¹⁾₂₂x₂+a⁽¹⁾₂₃x₃+a⁽¹⁾₂₄x₄=a⁽¹⁾_25,
a⁽¹⁾₃₂x₂+a⁽¹⁾₃₃x₃+a⁽¹⁾₃₄x₄=a⁽¹⁾_35,
a⁽¹⁾₄₂x₂+a⁽¹⁾₄₃x₃+a⁽¹⁾₄₄x₄=a⁽¹⁾_45, (1’)
где коэффициенты a⁽¹⁾_ij вычисляются по формуле
a⁽¹⁾_ij = a_ij - a_i1b_1j (i, j 2).
Далее, разделив коэффициенты первого уравнения системы (1’) на ведущий элемент a⁽¹⁾₂₂, получим уравнение
x₂+b⁽¹⁾₂₃x₃+b⁽¹⁾₂₄x₄=b⁽¹⁾₂₅ (2’)
где


(j > 2).

Исключая теперь х₂ таким же способом, каким мы исключили x₁, придем к следующей системе уравнений:

a ⁽²⁾₃₃x₃+a⁽²⁾₃₄x₄=a⁽²⁾₃₅
a⁽²⁾₄₃x₃+a⁽²⁾₄₄x₄=a⁽²⁾₄₅ (1’’)
a⁽²⁾_ij = a⁽¹⁾_ij - a_i2b⁽¹⁾_2j (i, j 3).
Затем разделим коэффициенты первого уравнения системы (1’’) на “ведущий элемент” a⁽²⁾₃₃ и получим:
x₃+b⁽²⁾₃₄x₄=b⁽²⁾₃₅, (2’’)
где


(j > 3).

Исключив аналогичным путём x₃ из системы (1’’)_, будем иметь:

a⁽³⁾₄₄x₄=a⁽³⁾₄₅
где a⁽³⁾_ij = a⁽²⁾_ij - a_i3b⁽²⁾_3j (i, j 4).
Отсюда

x₄ = (2’’’)

Остальныe неизвестные последовательно находятся из уравнений (2’’), (2’) и (2).
x₃ = b⁽²⁾₃₅ - b⁽²⁾₃₄x_4,
x₂ = b⁽¹⁾₂₅ - b⁽¹⁾₂₃x₃ - b⁽¹⁾₂₄x_4,
x₁ = b₁₅ - b₁₂x₂ - b₁₃x₃ - b₁₄x_4.
Таким образом, процесс решения линейной системы по методу Гаусса сводится к построению эквивалентной системы (2), (2’), (2’’), (2’’’), имеющей треугольную матрицу.
Вычисления удобно помещать в таблицу.

Условие применимости метода

Необходимым и достаточным условием применимости метода является неравенство нулю всех «ведущих элементов» (на диагонали полученной матрицы не должно быть нулевых элементов).

Прямой и обратный ход, построение схемы единственного деления

• 
  Прямым ходом называется процесс нахождения коэффициентов b^(j-1)_ij треугольной системы.
  
• 
  Обратным ходом называется процесс получения значений неизвестных.
  

Прямой ход начинается с выписывания коэффициентов системы, включая свободные члены (раздел А). Последняя строка раздела А схемы представляет собой результат деления первой строки раздела на «ведущий элемент» a_11. Элементы a⁽¹⁾_ij (i, j 2) следующего раздела схемы А₁ равны соответствующим элементам a_ij предшествующего раздела без произведений их «проекций» на ряды раздела А, содержащие элемент 1 (т.е. на первый столбец и на последнюю строку).
Последняя строка раздела А₁ находится путем деления первой строки раздела на ведущий элемент a⁽¹⁾_22. Аналогично строятся другие разделы. Прямой ход заканчивается, когда мы дойдем до раздела, состоящего из одной строки, не считая преобразованной (раздел А).
При обратном ходе используются лишь строки разделов Ai, содержащие единицы (отмеченные строки), начиная с последней. Элемент из раздела А₃, стоящий в столбце свободных членов отмеченной строки раздела, дает значение х4. Далее, все остальные неизвестные хi (i= 3, 2, 1) шаг за шагом находятся с помощью вычитания из свободного члена отмеченной строки суммы произведений её коэффициентов на соответствующие значения ранее найденных неизвестных. Значения неизвестных последовательно выписываются в последний раздел В. Расставленные там единицы помогают находить для хi соответствующие коэффициенты в отмеченных строках.