Метод Гаусса

 

Рассмотрим решение системы (3.2.1) mлинейных уравнений с nпеременными в общем виде.

Метод Гаусса – метод последовательного исключения переменных – заключается в том, что с помощью элементарных преобразований система уравнений приводится к равносильной системе ступенчатого (или треугольного) вида, из которой последовательно, начиная с последних (по номеру) переменных, находятся все остальные переменные.

Предположим, что в системе (3.2.1) коэффициент при переменной х₁ в первом уравнении а₁₁≠0 (если это не так, то перестановкой уравнений местами добьёмся того, чтобы а₁₁≠0 ).

Шаг 1. Умножая первое уравнение на подходящие числа и прибавляя полученные уравнения соответственно ко второму, третьему,…, m-му уравнению системы (3.2.1) , исключаем переменную х₁ из всех последующих уравнений, начиная со второго. В результате получаем систему

a₁₁х₁ + а₁₂х₂ + … + а_1nх_n = b₁

a₂₂⁽¹⁾ x₂ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾

- - - - - - - - - (3.2.6)

a_i2⁽¹⁾x₂ + … + a_in⁽¹⁾x_n = b_i⁽¹⁾

- - - - - - - - - - -

a_m2⁽¹⁾x₂ + … + a_mn⁽¹⁾x_n = b_m⁽¹⁾

 

где буквой с верхним индексом «(1)» обозначены новые коэффициенты, полученные после шага 1.

Рассмотрим, как вычисляются новые коэффициенты. Например, требуется исключить переменную х₁ из i-го уравнения (i =2, n). Выпишем 1-е и i-е уравнения системы (напомним, что а₁₁≠0)

a₁₁х₁ + а₁₂х₂ + … + a_1jx_j + … + a_1nx_n = b₁

- - - - - - - - - - - - - - -

a_ix₁ + a_i2x₂ + … +a_ijx_j + … + a_inx_n = b_i

- - - - - - - - - - - - - - - -

 

Назовем 1-е уравнение разрешающим,а коэффициент а₁₁ - разрешаю­щимкоэффициентом.

Умножим 1-е уравнение системы на такое «удобное» число λ, чтобы после этого, прибавив 1-е уравнение к i-му уравнению, переменная х₁ в i-ом уравнении не содержалась. При этом само 1-е уравнение сохраняется в системе на своем месте.

Итак,

a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + … + a_ijx_j +… +a_inx_n = b₁

- - - - - - - - - - - - - - - - - - - - - - - - - (3.2.7)

(λa₁₁+a_i1)x₁ + (λa₁₂+a_i2)x₂ +…+ (λa_1j+a_ij)x_j +…+ (λa1_n+a_in)x_n = λb₁+b_i

- - - - - - - - - - - - - - - - - - - - - - - - -

 

Из (3.2.7) следует, что новые коэффициенты при x_j в i-ом уравнении имеют вид a'_ij = λa_1j+a_ij, j=1,n, чтобы x₁ не входило в i-ое уравнение, число λ должно быть таким, чтобы λa₁₁+a_i1=0, откуда λ= - . При таком значении λ

 

 

 

 

Для пересчета коэффициентов и свободного члена по формулам (3.2.8) удобно использовать «правило прямоугольника»:

a₁₁ a_1j a₁₁-разрешающий элемент

a_ij-разрешаемый (пересчитываемый) элемент

a_1j, a_i1­-сопутствующие элементы

a_i1 a_ij

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

Шаг 2.Временно 1-е уравнение исключаем. Если а ⁽¹⁾₂₂≠0 (всегда можно добиться), то второе уравнение выбираем в качестве разрешающего. Со 2-ым уравнением системы поступим так же, как и на 1-м шаге, исключаем из всех равнений, начиная с 3-го уравнения, переменную х₂.

 

Продолжая процесс последовательного исключения переменных х₃, х₄, …, х_r-1, после (r-1)-го шага получаем систему

 

a₁₁х₁ + а₁₂х₂ + … + a_1rx_r + a_1,r+1x_r+1 + … + a_1nx_n = b₁ ,

a⁽¹⁾₂₂x₂+…+a⁽¹⁾_2rx_r + a⁽¹⁾_2,r+1x_r+1 + … +a⁽¹⁾_2nx_n = b⁽¹⁾₂ ,

…………………………………………………..... (3.2.9)

a^(r-1)_rrx_r + a^(r-1)_r,r+1x_r+1 +…+a^(r-1)_rnx_n = b^(r-1)_r ,

……………………………………………

0=b^(r-1)_r+1 ,

……..

0=b^(r-1)_m

Число ноль в последних m – r уравнениях означает, что их левые частиимеют вид: 0*х₁ + 0*х₂ + … + 0*х_n. Если хотя бы одно из чисел b^(r-1)_r+1,… b^(r-1)_m не равно нулю, то соответствующее равенство противоречиво и система (3.2.9) несовместна.

Таким образом, для любой совместной системы числа b^(r-1)_r+1,… b^(r-1)_m в системе равны нулю. В этом случае последние m – r уравнений в системе (3.2.9) являются тождествами и их можно не принимать во внимание при решение системы (3.2.1). Очевидно, что после отбрасывания «лишних» уравнений возможны два случая: а) число уравнений системы (3.2.1) равно числу переменных, т.е. r = n (в этом случае система (3.2.9) имеет треугольный вид); б) r < n (в этом случае система (3.2.9) имеет ступенчатый вид).

Переход системы (3.2.1) к равносильной ей системе (3.2.9) называется 9прямым ходом метода Гаусса, а нахождение переменных из системы (3.2.9) – обратным ходом.

Преобразования Гаусса удобно проводить, осуществляя их не с самими уравнениями, а с матрицей их коэффициентов. Рассмотрим матрицу

a₁₁ а₁₂ … а_1n b₁

a₂₁ a₂₂ … a_2n b₂

(A│B) = …………….. … , (3.2.10)

a_m1 a_m2 … a_mn b_m

 

называемую расширенной матрицей системы (3.1), ибо в нее, кроме матрицы системы А, дополнительно включен столбец свободных членов матри-

цы В.

Системе (3.2.9) соответствует диагональная матрица. Значит, ее определитель не равен нулю. Это означает что ранг матрицы r=3. Система имеет единственное решение. Закончен прямой ход метода Гаусса.

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

Пример.Решить систему методом Гаусса.

х₁+2х₂+ 3х₃=6

2х₁+3х₂ -х₃=4

3х₁+х₂ - 4х₃=0

 

Выпишем расширенную матрицу системы

 

1 2 3 6

(А/В)= 2 3 -1 4

3 1 -4 0

Шаг 1.Исключим переменную х₁ из 2-го и 3-го уравнений, выбрав 1-е уравнение (строку) разрешающим и коэффициент а₁₁=1≠0 будем считать разрешаемым. Это означает, что после пересчета коэффициентов а_ij в новой (эквивалентной) матрице в 1-м столбце под разрешающим элементом будут стоять нули. Новая матрица будет иметь вид

1 2 3 6 1 2 3 6

0 -1 -7 -8 0 1 7 8

0 -5 -13 -18 0 5 13 18

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

1 2 3 6

0 1 7 8

0 0 22 22

 

Аналогично пересчитываем и свободный член.

На этом закончен 1-й шаг. Начинаем обратный ход.

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

 

 

22х₃ = 22 х₃ = 1

х₂ + 7х₃ = 8 х₂ = 8 – 7х₃ = 1

х₁ + 2х₂ + 3х₃ = 6 х₁ = 6 – 2х₂ – 3х₃

Решение системы: х₁=х₂=х₃=1