Лин.Алгебра_metod_Gaussa-Zhordana

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

Начальный этап. Сначала выпишем систему уравнений (6) в более удобной форме - в виде таблицы I⁽⁰⁾.

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

(0.1)

(0.2)

(0.3)

Первая строка таблицы I⁽⁰⁾ соответствует первому уравнению система (6), (будем ее, как и первое уравнение в (6), нумеровать (0.1)), вторая строка - второму уравнению системы (6) (будем ее нумеровать (0.2)), третья строка - третьему уравнению системы (6) (будем ее нумеровать (0.3)).

Первый столбец таблицы образуют коэффициенты системы (6) при неизвестной x₁, второй столбец - коэффициенты системы (6) при неизвестной x₂, аналогично поясняются третий и четвертый столбцы таблицы I⁽⁰⁾. Пятый столбец (b) таблицы составляют правые части уравнений (свободные члены) системы (6).

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

Основной этап. Известны таблица I⁽⁰⁾, ведущий элемент 2, стоящий на пересечении первой строки и первого столбца, ведущая строка – первая, ведущий столбец - первый.

Итерация 1. Подробно опишем преобразования таблицы I⁽⁰⁾ в новую таблицу I⁽¹⁾, в которой первый столбец – единичный с 1 на месте ведущего элемента. Записывать новую таблицу будем под таблицей I⁽⁰⁾.

Сначала опишем преобразование, в результате которого элемент, расположенный непосредственно под ведущим элементом и равный 3, перейдет в нулевой элемент. Для этого нужно из строки (0.2) вычесть (поэлементно) ведущую строку (0.1), умноженную на 3/2. Тогда строка (0.2) заменится на строку

0

17/2

- 13/2

- 3/2

7/2

Поскольку в данном случае все элементы второй строки можно умножить на число 2 и ничего с точки зрения множества решений не изменится, то более удобно совершить еще одно элементарное преобразование (умножить все элементы строки на 2) и в таблицу I⁽¹⁾ следует поместить в качестве второй такую строку

0

17

-13

-3

7

(1.2)

Очевидно, такое преобразование таблицы I⁽⁰⁾ соответствует элементарным преобразованиям системы (6), в результате которых система (6) превращается в эквивалентную систему, описываемую уравнениями (0.1), (1.2) и (0.3). Итак, в результате преобразования второй строки таблицы I⁽⁰⁾ мы получили новую вторую строку (вторую строку новой таблицы I⁽¹⁾), в которой в ведущем столбце (в нашем случае в первом столбце) вместо числа 3 стоит число 0.

Преобразуем третью строку таблицы I⁽⁰⁾ так, чтобы вместо 5 стоял 0. Для этого нужно из строки (0.3) вычесть (поэлементно) ведущую строку (0.1), умноженную на 5/2. Получим

0

7

-3

-5

9

(1.3)

Из трех строк таблицы I⁽⁰⁾ непреобразованной осталась только ведущая (первая) строка. Все элементы ведущей строки (0.1) делим на ведущий элемент (т.е. в нашем конкретном случае - на число 2) и полученную новую строку записываем на ее место (т.е. на место (1.1)) в таблице I⁽¹⁾.

1

-3/2

3/2

5/2

-1/2

(1.1)

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

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

(0.1)

(0.2)

(0.3)

(1.1)

(1.2)

(1.3)

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

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

Прежде чем переходить к следующей (второй) итерации, сделаем ряд важных замечаний, которые можно повторять дословно или с необходимыми корректировками после остальных итераций:

1. Итерация имеет вполне определенный (свой) ведущий элемент и, следовательно, определенные (свои) ведущие столбец и строку. Рабочей таблицей первой итерации была таблица I⁽⁰⁾, итоговой таблицей первой итерации - таблица I⁽¹⁾.

2. В результате выполнения итерации ведущий столбец превра­щается в единичный (на месте ведущего элемента появляется единица (она выделена полужирным шрифтом), а на местах остальных элементов веду­щего столбца - нули, тем самым в результате итерации мы исклю­чили неизвестную из всех уравнений системы кроме одного. Посколь­ку на каждой итерации полностью исключается своя неизвестная (переменная), становится понятным название метода Гаусса-Жордана как метода последовательно полного исключения неизвестных.

3. Таблица I⁽¹⁾ соответствует системе уравнений, эквивалентной исходной системе (6), которой соответствует таблица I⁽⁰⁾, т.к. преобразования, которым мы подвергали строки таблицы I⁽⁰⁾, представляют собой элементарные преобразования исходной системы (6).

4. Наиболее трудоемкую часть итерации составляют преоб­разования табличных строк.

5. Первую строку таблицы I⁽¹⁾ на число 2 умножать нельзя, т.к. на месте элемента, который был ведущим, должна стоять единица .

Итерация 2. Опишем преобразования таблицы I⁽¹⁾ в новую таблицу I⁽²⁾, в которой третий столбец (ведущий) будет единичным. Записывать новую таблицу будем под таблицей I⁽¹⁾.

Далее, как и на предыдущей (первой) итерации, будем подвер­гать все строки элементарным преобразованиям.

Сначала переведем в нулевой элемент 3/2 ведущего столбца таблицы I⁽¹⁾. Для этого ведущую строку (1.3) умножим на 1/2 и прибавим к строке (1.1). Получим первую строку (2.1) новой таблицы I⁽²⁾.

1

2

0

0

4

(2.1)

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

0

-40/3

0

56/3

-32

В данном случае естественно все элементы этой строки умножить на 3/8 и в таблицу I⁽²⁾ поместить в качестве второй следующую строку

0

-5

0

7

-12

(2.2)

Из трех строк таблицы I⁽¹⁾ непреобразованной осталась только ведущая (третья) строка. Все элементы ведущей строки (1.3) делим на ведущий элемент (т.е. в нашем конкретном случае - на число -3) и полученную новую строку записываем на ее место (т.е. на место (2.3)) в таблице I⁽²⁾.

0

-7/3

1

5/3

-3

(2.3)

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

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

(0.1)

(0.2)

(0.3)

(1.1)

(1.2)

(1.3)

(2.1)

(2.2)

(2.3)

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

Итерация 3. Преобразуем четвертый столбец (ведущий) в единичный и получим новую таблицу I⁽³⁾. Записываем новую таблицу под таблицей I⁽²⁾.

В первой строке уже стоит 0 в четвертом столбце. Поэтому строку (2.1), не меняя, переносим в таблицу I⁽³⁾ как (3.1). С помощью элементарного преобразования переведем теперь в нулевой элемент 5/3 ведущего столбца таблицы I⁽²⁾. Для этого ведущую строку (2.2) умножим на 5/21 и прибавим к строке (2.3). Получим третью строку (3.3) новой таблицы I⁽³⁾:

0

-8/7

1

0

-1/7

(3.3)

Все элементы ведущей строки (2.2) делим на ведущий элемент (т.е. в нашем конкретном случае - на число 7) и полученную новую строку

0

-5/7

0

1

-12/7

(3.2)

записываем на ее место (т.е. на место (3.2)) в таблице I⁽³⁾.

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

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

(0.1)

(0.2)

(0.3)

(1.1)

(1.2)

(3.3)

(2.1)

(2.2)

(2.3)

(3.1)

(3.2)

(3.3)

Теперь проверяем, можем ли мы выбрать в I⁽³⁾ новый ведущий элемент – ненулевой элемент, стоящий на пересечении строки и столбца, которые еще не были ведущими. В нашей ситуации в таблице I⁽³⁾ уже нельзя выбрать новый ведущий элемент, т.к. в ней всего три строки, и все они уже были ведущими на предыдущих итерациях. Следовательно, таблица I⁽³⁾ (и третья итерация) является последней (конечной). Переходим к Заключительному этапу.

Заключительный этап. В таблице I⁽³⁾ имеется три еди­ничных столбца, каждый из которых на одной из итераций был веду­щим. Соответствующие переменные (в нашем случае это переменные x₁ , x_3, x₄) являются базисными, а ос­тальные переменные (в нашем случае это переменная x₂) - свобод­ные.

Запишем систему линейных алгебраических уравнений, соответ­ствующую последней таблице I⁽³⁾.

x₁ + 2 x₂ = 4

(-5/7) x₂ + x₄ =-12/7 (7)

(-8/7) x₂ + x₃ = - 1/7.

Система (7) эквивалентна системе (6), т.е. имеет то же самое множество решений. Выразим базисные переменные через свободную. С учетом того, что свободная переменная может принимать любое значение, получим

x₁ = 4 - 2 x₂, x₃ = -1/7 + (8/7) x₂, x₄ = -12/7 + (5/7) x₂, x₂ - любое. (8)

Любой набор x = (x₁, x₂, x₃, x₄), удовлетворяющий (8), представляет собой решение системы (7) и, следовательно, эквивалентной ей исходной системы (6). Множество решений X^b = { x = (x₁, x₂, x₃, x₄) : x₁ = 4 - 2x₂, x₃ = -1/7 + (8/7)x₂, x₄ = -12/7 + (5/7 x₂, x₂ – любое}.

Придавая свободной переменной всевозможные значения, будем из набора (8) получать различные частные решения системы (6). Например, полагая x₂ = 0, получим частное решение (4, 0, - 1/7, - 12/7). Общее решение (8) системы (6) содержит (описывает единой формулой) все ее частные решения.

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

Пример 2. Решить две следующие системы, которые отличаются одна от другой только правыми частями

2 x₁ – 3 x₂ + 3 x₃ + 5 x₄ = -1,

3 x₁ + 4 x₂ - 2 x₃ + 6 x₄ = 2, (9)

4 x₁ + 6 x₂ - 6 x₃ - 10 x₄ = 3

и

2 x₁ – 3 x₂ + 3 x₃ + 5 x₄ = -1,

3 x₁ + 4 x₂ - 2 x₃ + 6 x₄ = 2, (10)

4 x₁ + 6 x₂ - 6 x₃ - 10 x₄ = 2.

В приводимом ниже решении подробные пояснения даются только в тех случаях, которые еще не встречались при разборе предыдущего примера 1.

Начальный этап. Перепишем две системы в виде таблицы I⁽⁰⁾, в которой будут фигурировать два столбца правых частей b⁽⁹⁾ и b⁽¹⁰⁾ (а не один, как в преды­дущем примере).

	x1	x2	x3	x4	b(9)	b(10)
I(0)	2	-3	3	5	-1	-1
	3	4	-2	6	2	2
	-4	6	-6	-10	3	2

(0.1)

(0.2)

(0.3)

Выберем, как и в примере 1, в качестве ведущего элемент 2, стоящий на пересечении 1-ой строки и 1 - го столбца. Тогда ведущая строка – первая, ведущий столбец - первый. Перейдем к основному этапу.

Основной этап. Известны таблица I⁽⁰⁾, ведущий элемент 2, стоящий на пересечении первой строки и первого столбца, ведущая строка – первая, ведущий столбец - первый.

Итерация 1. Построим новую таблицу I⁽¹⁾, в которой первый столбец – единичный с 1 на месте ведущего элемента. Записывать новую таблицу будем под таблицей I⁽⁰⁾. Очевидно, что первая и вторая строка в ней совпадают с соответствующими строками в таблице I⁽¹⁾ примера 1. Для того, чтобы получить 0 на месте (-4) в третьей строке, умножим строку (0.1) на 2 и прибавим (почленно) к строке (0.3). Таблица I⁽¹⁾ будет иметь вид (три последние строки, выделенные курсивом)

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