Метод Гаусса

Метод Гаусса.

Метод Гаусса решения системы (1.1) - это метод последовательного исключения неизвестных. Алгоритм исключения состоит из последовательности шагов.

Шаг 1: Исключим неизвестную x₁ из всех уравнений системы (1.1) кроме первого.

Пусть a₁₁≠ 0. Тогда из первого уравнения в (1.1) получаем:
x₁ = [b₁ - (a₁₂x₂ + ... + a_1nx_n )]/a₁₁. Подставляя это выражение для x₁ во все остальные уравнения, получим эквивалентную систему:

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁
a₂₂⁽¹⁾x₂ + ... + a_2n⁽¹⁾x_n = b₂⁽¹⁾
...
a_n2⁽¹⁾x₂ + ... + a_nn⁽¹⁾x_n = b_n⁽¹⁾ (1.5)
где верхний индекс у коэффициента a_ij выражает факт его изменения на соответствующем шаге. Нетрудно подсчитать, что

a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁ a₂₂⁽¹⁾x₂ + ... + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ... a_n2⁽¹⁾x₂ + ... + a_nn⁽¹⁾x_n = b_n⁽¹⁾	(1.5)

a_ij⁽¹⁾ = a_ij - [a_i1 a_1j ]/a₁₁ , 2 ≤ i, j ≤ n
b_i⁽¹⁾ = b_i - [a_i1 b₁ ]/a₁₁ , 2 ≤ i ≤ n

Шаг 2: Исключим неизвестную x₂ из всех уравнений системы (1.5), кроме первого и второго, при условии a₂₂⁽¹⁾≠ 0 и получим соответствующую эквивалентную систему:

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... + a_1nx_n = b₁
a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + ... + a_2n⁽¹⁾x_n = b₂⁽¹⁾
a₃₃⁽²⁾x₃ + ... + a_3n⁽²⁾x_n = b₃⁽²⁾
...
a_n3⁽²⁾x₃ + ... + a_nn⁽²⁾x_n = b_n⁽²⁾

Продолжая этот процесс исключения при условии, что a_ii^(i-1)≠ 0, i=1,...,n после (n-1)-ого шага исключения получим следующую эквивалентную систему уравнений, имеющую треугольный вид (то есть матрица системы является треугольной):

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... + a_1nx_n = b₁
a₂₂⁽¹⁾x₂ + ... + a_2n⁽¹⁾x_n = b₂⁽¹⁾
...
a_nn^(n-1)x_n = b_n^(n-1) (1.6)
где

a_ij^(k) = a_ij^(k-1) - [a_ik^(k-1) a_kj^(k-1)] / a_kk^(k-1)
b_i^(k) = b_i^(k-1) - [a_ik^(k-1) b_k^(k-1)] / a_kk^(k-1)
k = 1, ..., n-1; i,j = k+1, ..., n; (1.7)
причем a_ij⁽⁰⁾ ≡ a_ij , b_i⁽⁰⁾ ≡ b_i.

Шаги 1, ..., n образуют прямой ход исключения (прямой ход метода Гаусса).

Из системы (1.6) очевидным образом вычисляются все компоненты решения x:

x_n = b_n^(n-1) / a_nn^(n-1)
x_i = [b_i^(i-1) - ∑ ⁿ_j=i+1 a_ij^(i-1)x_j] /a_ii^(i-1), i = n-1, ..., 1 (1.8)
Формулы (1.8) образуют обратный ход исключения (обратный ход метода Гаусса).

В целом формулы (1.7)-(1.8) дают вычислительный алгоритм для решения СЛАУ методом Гаусса на ЭВМ.

ЗАМЕЧАНИЕ 1.1 Элементы a_ii^(i-1) на которые производится деление в методе Гаусса, называются ведущими элементами исключения. В приведенном алгоритме предполагается, что a_ii^(i-1) ≠ 0, i=1, ..., n-1. Существуют критерии, гарантирующие выполнение этих неравенств. С другой стороны существуют модификации метода Гаусса, в которых путем перестановок строк или столбцов добиваются автоматического выполнения этих неравенств [1, 9].