Метод Гаусса-Жордана_методичка

(0.1)

(0.2)

(0.3)

(1.1)

(1.2)

(1.3)

Таблица I⁽¹⁾ с первым столбцом свободных членов соответствует системе уравнений, эквивалентной системе (9), а с вторым столбцом свободных членов - системе уравнений, эквивалентной системе (10). Для системы (9) последнее уравнение имеет вид

0 x₁ + 0 x₂ + 0 x₃ + 0 x₄ = 1,

что показывает несовместность системы (9).

Для системы (10) последнее уравнение имеет вид

0 x₁ + 0 x₂ + 0 x₃ + 0 x₄ = 0.

Отсюда следует, что его можно отбросить, и что система (10) эквивалентна системе из 2 – х уравнений с 4 – мя неизвестными, представляемой строками (1.1), (1.2) и вторым столбцом свободных членов в таблице I⁽¹⁾. Мы можем продолжать решать систему (10), используя следующую таблицу I⁽¹⁾

I(1)	1	-3/2	3/2	5/2	-1/2
	0	17	-13	-3	7

(1.1)

(1.2)

или

	x1	x2	x3	x4	b
I(0)	2	-3	3	5	-1
	3	4	-2	6	2
	-4	6	-6	-10	2
I(1)	1	-3/2	3/2	5/2	-1/2
	0	17	-13	-3	7

(0.1)

(0.2)

(0.3)

(1.1)

(1.2)

В таблице I⁽¹⁾ можно выбрать в качестве ведущего любой ненулевой элемент, стоящий во второй строке и в любом, кроме первого, столбце. Выберем в качестве ведущего в таблице I⁽¹⁾ элемент (-3), стоящий на пересечении 4 - ого столбца и 2 – ой строки. Тогда ведущая строка – вторая, ведущий столбец- четвертый.

Итерация 2. Преобразуем таблицу I⁽¹⁾ в новую таблицу I⁽²⁾, в которой четвертый столбец (ведущий) будет единичным. Для этого преобразуем первую строку таблицы I⁽¹⁾ так, чтобы вместо 5/2 стоял 0. Для этого нужно из строки (1.1) вычесть (поэлементно) ведущую строку (1.2), умноженную на (-5/6). Получим

1

38/3

-28/3

0

16/3

(2.1)

Все элементы ведущей строки (1.2) делим на ведущий элемент (т.е. в нашем конкретном случае - на число (-3)) и полученную новую строку записываем на ее место (т.е. на место (2.2)) в таблице I⁽²⁾.

Таблица I⁽²⁾ будет иметь вид (две последние строки, выделенные курсивом)

	x1	x2	x3	x4	b
I(0)	2	-3	3	5	-1
	3	4	-2	6	2
	-4	6	-6	-10	2
I(1)	1	-3/2	3/2	5/2	-1/2
	0	17	-13	-3	7
I(2)	1	38/3	-28/3	0	16/3
	0	-17/3	13/3	1	-7/3

(0.1)

(0.2)

(0.3)

(1.1)

(1.2)

(2.1)

(2.2)

Обе строки уже были ведущими, поэтому мы не можем в таблице I⁽²⁾ выбрать ведущий элемент. Переходим к Заключительному этапу.

Заключительный этап. Все строки были ведущими, поэтому система, определяемая таблицей I⁽²⁾, и, следовательно, система (10) разрешима. При этом переменные x₁ и x₄ – базисные, а x₂ и x₃ – свободные. Запишем систему линейных алгебраических уравнений, соответ­ствующую последней таблице I⁽²⁾.

x₁ + (38/3) x₂ - (28/3) x₃= 16/3

x₄ - (17/3) x₂ + (13/3) x₃ = - 7/3 (11)

Из (11) можно однозначным образом выразить базисные переменные через свободные и правую часть. На свободные переменные при этом нет никаких ограничений, т.е. они могут принимать любые значения. Таким образом, множеством решений системы (11) и, следовательно, системы (10) является следующее множество X^b,

X^b = { x = (x₁, x₂, x₃, x₄) : x₁ = 16/3 - (38/3) x₂ + (28/3) x₃, x₄ = - 7/3 + (17/3) x₂

- (13/3) x₃, x₂ и x₃ – любые.}

Примеры 1 и 2 проиллюстрировали работу метода Гаусса – Жордана и все возможные способы остановки метода. Повторим основные выводы, которые можно сделать из изложенного.

1. Метод остановится через конечное число итераций r. При этом выяснится, является система совместной или несовместной.

2. Если система совместна, то число базисных переменных равно числу итераций r, а число свободных переменных – (n – r). Все базисные переменные однозначно выражаются через свободные переменные и соответствующие свободные члены.

3. Если система совместна и общее решение содержит хотя бы одну свободную переменную, то число решений бесконечно. Если же свободных переменных нет (n = r), то решение единственно.

4. Базисные переменные на каждой итерации можно выбирать различными способами, поэтому запись общего решения может быть разной. Однако, само множество решений одно и то же.

Вернемся к анализу систем уравнений (1) и (1⁰). Если в системах (1) и (1⁰) все соответствующие (с одинаковыми номерами) коэффициенты при переменных совпадают, то системы (1) и (1⁰) называются соответствующими. Множества решений систем (1) и (1⁰) обозначаем X^b и X⁰. Система (1) совместна, если X^b ≠ .

Теорема 3. Если в однородной системе уравнений (1⁰) n > m, то система (1⁰) имеет бесконечное число решений.

Доказательство. Однородная система всегда совместна (набор = (,,…,), где = 0 при всех j = 1,…,n, очевидно, является её решением), т.е. X⁰ ≠ . Если решать ее методом Гаусса – Жордана, то он остановится через r итераций и r ≤ min (m,n) = m < n. Тогда число свободных переменных есть n – r ≥ n – m > 0. Отсюда следует, что система имеет бесконечное число решений. Теорема доказана.

Теорема 4. Пусть y = (y₁, y₂, … , y_n) и z = (z₁, z₂, … , z_n) – решения однородной системы (1⁰), т.е. y X⁰, z X⁰. Тогда

1. x* = y + z = (y₁ + z₁, y₂ + z₂, … , y_n + z_n) X⁰,

2. x = y = (y₁, y₂, … , y_n) X⁰.

Доказательство. 1) Так как y X⁰, z X⁰, то

= 0, i = 1,…,m, = 0, i = 1,…,m. (12)

Проверим, является ли x* решением (1⁰). Для этого рассмотрим . В силу (12)

= = + = 0, т.е. x* X⁰.

2) Так как = = 0, то x = y X⁰. Теорема доказана.

Рассмотрим теперь соответствующие друг другу системы (1) и (1⁰). Пусть система (1) совместна, т.е. X^b ≠ . Пусть = (,,…,) – некоторое фиксированное частное решение системы (1), т.е. = b_i при всех i = 1,…,m.

Теорема 5. Пусть система (1) совместна и = (,,…,) – некоторое её фиксированное частное решение. Тогда

1) произвольное решение x = (x₁, x₂, … , x_n) является суммой (почленной) этого фиксированного решения и некоторого решения z = (z₁, z₂, … , z_n) соответствующей однородной системы;

2) если z = (z₁, z₂, … , z_n) – произвольное решение однородной системы (1⁰), то x = + z = ( + z₁, + z₂,…, + z_n) – решение соответствующей неоднородной системы (1).

Доказательство. 1) Так как X^b и x X^b,то

= b_i , = b_i при всех i = 1,…,m. (13)

Построим набор z = (z₁, z₂, … , z_n) следующим образом:

z_j = - x_j, j = 1, … , n. (14)

Покажем, что z – решение соответствующей однородной системы. Действительно, в силу (14) и затем (13)

= = - = b_i - b_i = 0.

Так как это верно для любого i = 1,…,m, то набор z, определенный в (14), является решением системы (1⁰).

2) Пусть z = (z₁, z₂, … , z_n) X⁰, т.е.

= 0 при всех i = 1,…,m. (15)

Положим

x_j = + z_j, j = 1, … , n. (16)

Покажем, что x = (x₁, …, x_n) – решение системы (1). Из (16), (13) и (15) следует

= = + = b_i + 0 = b_i при всех i, т.е. x X^b. Теорема доказана.

Теорема 5 утверждает, что для того, чтобы найти все решения системы (1), достаточно найти одно её решение и все решения соответствующей однородной системы (1⁰).

Это всё, что мы пока можем сказать о системе из m линейных уравнений с n переменными. Будем возвращаться к анализу таких систем во всех следующих темах.

15