Минюк С.А., Ровба Е.А. Высшая математика
Подождите немного. Документ загружается.
5 1
Лекция 9
Исследование систем линейных уравнений.
Метод Гаусса
Сформулирована теорема о совместности систем
m линейных уравнений с n неизвестными, рассмотрен
метод Гаусса решения и исследования таких систем.
1
0
. Системы линейных уравнений и их исследование.
Рассмотрим систему m линейных уравнений с n неизвестными:
=+++
=+++
=+++
,
,
,
2211
22222121
11212111
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
%
%%%%%%%%%
%
%
(1)
где
njmia
ij
,1,,1; ==
– коэффициенты системы;
njx
j
,1, =
– неизвес-
тные;
mib
j
,1, =
– свободные члены.
Другие формы записи системы (1):
=
mnmnmm
n
n
b
b
b
x
x
x
aaa
aaa
aaa
""
%
%%%%
%
%
2
1
2
1
21
22221
11211
– матричная форма; (2)
bxA
!
!
=
– операторная форма, (3)
где
()
n
xxx
,,col
1
…=
!
– столбец неизвестных,
()
m
bbb
,,
1
…=
col
!
– стол-
бец свободных членов,
…
………
…
=
mnm
n
aa
aa
A
1
111
– матрица системы (1);
∑
=
==
n
j
ijij
mibxa
1
,1,
– тензорная форма. (4)
Как и в Л.8, совокупность чисел (x
1
; x
2
; x
3
;...; x
n
) или
n
x
x
x
"
2
1
–
52
решение системы (1) ((2), (3), (4)), если она обращает все ее уравнения
в верные равенства.
Система (1) называется совместной, если она имеет хотя бы одно
решение, и несовместной, если она не имеет ни одного решения.
Система (1) называется однородной, если все свободные члены рав-
ны нулю. Операторная форма записи однородной системы имеет вид:
0
=
xA
!
, (5)
где под 0 понимаем нулевой вектор
0
!
.
Расширенной матрицей системы (1) называется матрица В, состоя-
щая из матрицы системы, дополненной столбцом свободных членов, т.е.
=
mmn
n
n
mm
b
b
b
a
a
a
aa
aa
aa
B
%%
%
%%%
%
%
2
1
2
1
21
2221
1211
. (6)
Теорема Кронекера-Капелли.
Система (1) совместна, если ранг матрицы А (r
A
) равен рангу
матрицы В (r
B
), и несовместна, если r
B
>r
A
.
Пример 1. Исследовать на совместность систему:
=−−
=+
.222
,1
yx
yx
(7)
Решение.
.
2
1
4
1
0
1
0
1
2
1
2
1
2
1
AB
B
A
rr
r
r
B
>⇒
=
=
⇒
⇒
−−−
=
Итак, система (7) несовместна.
Пример 2. Исследовать на совместность систему:
−=−−
=+
.222
,1
yx
yx
Решение.
.
1
1
0
1
0
1
0
1
2
1
2
1
2
1
AB
B
A
rr
r
r
B
=⇒
=
=
⇒
⇒
−−−
=
Система (8) совместна.
53
Следствия.
1) Пусть
0det, ≠=∆= Anm
. Тогда r
A
= r
B
= n, т.е. система (1)
совместна, и ее решение можно найти методами, изложенными в Л.8.
2) Пусть
0=b
!
. Тогда r
A
= r
B
, т.е. однородная система (5) всегда
совместна.
2
0
. Метод Гаусса. Наиболее распространенным точным мето-
дом решения систем (1) является метод Гаусса. Суть метода со стоит в
том, что посредством элементарных преобразований система (1) приво-
дится к т реугольному или трапециедальному виду, из которого все реше-
ния системы получаются непосредственно.
К элементарным преобразованиям относятся следующие:
1) перестановка любых двух уравнений системы; 2) умножение любо-
го уравнения системы на отличное от нуля число; 3) вычеркивание
уравнения, все коэффициенты которого равны нулю; 4) вычитание из
любого уравнения системы любого другого, умноженного на отлич-
ное от нуля число.
Любое элементарное преобразование приводит к системе вида
(1), равносильной данной.
Рассмотрим систему вида (1), где коэффициент a
11
≠0 . Если бы
было a
11
= 0, то на первое место в системе (1) поставили бы уравнение,
в котором коэффициент при x
1
отличен от нуля. Пусть далее в i-ом
уравнении a
i1
≠0. Умножим обе части первого уравнения на
−
11
1
a
a
i
и
сложим его с i-ым уравнением. В результате получим уравнение
()()()
+−+−+−
311331121121121111111
xaaaaxaaaaxaaaa
iiiiii
()
11111111
...
iininin
abbaxaaaa
−=−++
,
где коэффициент при x
1
равен нулю.
Преобразуем таким образом все уравнения системы, в которых
a
i1
≠0
(
)
mi ,2
=
и, переобозначая cоответствующие коэффициенты, полу-
чим систему
′
=
′
++
′
′
=
′
+
′
′
=+++
mnmnm
nn
nn
bxaxa
bxaxa
bxaxaxa
%
%%%%%%%%%
%
%
22
12222
11212111
,
,
,
)1(
′
в которой рамкой выделена так называемая остаточная часть системы.
54
Преобразование системы (1) в систему
()
1
′
выполнено с помо-
щью ее первого уравнения, называемого разрешающим на данном
шаге. Исключалась переменная x
1
, называемая разрешающей, коэф-
фициент a
11
при ней называется разрешающим, столбец коэффициен-
тов
n
a
a
a
2
21
11
"
при разрешающей переменной – разрешающим столбцом.
Если в системе
()
1
′
встретится уравнение вида
++⋅+⋅ %
32
00
xx
sn
bx
′
=⋅+0
, где
0≠
′
s
b
, то система (1) несовместна. Если этого не
произойдет, то, предполагая, что
0
22
≠
′
a
, из всех уравнений остаточ-
ной части системы
()
1
′
, кроме первого, исключим аналогично преды-
дущему неизвестную x
2
.
Продолжая процесс преобразования остаточных частей получа-
ющихся систем, придем к одному из двух случаев:
1) либо в ходе преобразований получаем уравнение вида
bxxx
nkk
=+++
+
000
1
%
, где b≠0, и тогда система (1) несовместна;
2) либо приходим к системе без остаточной части:
=+…+
…………………………………
′′
=
′′
+…+
′′
+
′′
′
=
′
+…+
′
+
′
=+…++
,
,
,
,
33434333
22323222
11212111
rnrnrrr
nn
nn
nn
cxbxb
bxaxaxa
bxaxaxa
bxaxaxa
)1(
′′
где
rr
baaa
...,,,,
332211
′′′
отличны от нуля. Возможно уменьшение чис-
ла уравнений по сравнению с исходной системой (r ≤ m) . Это связано
с тем, что в процессе преобразований вычеркиваются уравнения вида
0000 =⋅++⋅+⋅
+
njij
xxx
%
.
Процесс преобразования системы (1) к системе
()
1
′′
называют
прямым ходом метода Гаусса.
Если в системе
()
nr
=
′′
1
, то она имеет треугольный вид. Из после-
днего уравнения b
nn
x
n
= c
n
находим x
n
, из предпоследнего – x
n–1
и т.д. и,
наконец, из первого – x
1
и, тем самым, – единственное решение системы
(1). Описанный процесс называют обратным ходом метода Гаусса.
55
Если r< n, то в результате обратного хода r неизвестных можно
выразить линейно через остальные (n – r) – неизвестных. Эти r
неизвестных называют базисными, а остальные (n – r) свободными. В
результате получим общее решение системы в виде:
+…++=
………………………………
+…++=
+…++=
++
++
++
.
,
,
11,0
211,2202
111,1101
nrnrrrrr
nnrr
nnrr
xcxccx
xcxccx
xcxccx
(8)
Совокупность базисных неизвестных назовем базисом системы не-
известных. Общее решение (8) записано относительно базиса (x
1
, x
2
, ..., x
r
).
Ясно, что его можно записать относительно и других базисов, которых
может быть не более C
n
r
(число сочетаний из n по r).
Чтобы получить как ое-нибудь частное решение системы (1), нужно
придать свободным неизвестным некоторые числовые значения. Ясно,
что в случае r < n система (1) имеет бесконечное множество решений.
Замечание 1. На практике элементарным преобразованиям подвергают
не систему уравнений, а ее расширенную матрицу В. Применительно к матрич-
ной записи процедура гауссовских исключений формализуется следующим об-
разом. Первый шаг (исключение неизвестной x
1
) прямого хода выполняется с
разрешающим элементом a
11
, второй шаг (исключение x
2
) – с элементом
22
a
′′
и
т.д., где разрешающими являются диагональные элементы матрицы. Пересчет
элементов матрицы выполняется по следующим правилам: 1) элементы разре-
шающей строки и всех вышерасположенных строк остаются неизменными; 2)
элементы разрешающего столбца, расположенные ниже разрешающего элемен-
та, обращаются в нули;
3) все прочие элементы
матрицы вычисляются по
правилу прямоугольника,
преобразованный элемент
равен разности произведе-
ний э лементов главной и
побочной диагоналей
(рис. 1).
Замечание 2. Из
метода Гаусса вытекает
доказательство теоремы
Кронекера-Капелли.
Рис. 1
56
Пример 3. Решить систему:
=++
−=+−
=+−
.134
,132
,52
321
31
321
xxx
xx
xxx
Решение. Последовательно получаем следующие матрицы:
[]
[]
−−
−
−
⇒
−
−
−
⇒
−
−
−
=
38
9
5
38
5
1
00
40
21
4
9
5
2
5
1
60
40
21
1
1
5
3
3
1
4
0
1
2
21
B
.
По последней матрице записываем систему уравнений, равно-
сильную данной:
−=−
=+−
=+−
.3838
,954
,52
3
32
321
x
xx
xxx
Начиная снизу вверх, последовательно находим: x
3
= 1,
–4x
2
+5⋅1 =9⇒x
2
=–1, x
1
–2 (–1)+1 =5⇒x
1
= 2. Итак, (2;–1;1) – един-
ственное решение исходной системы.
! Задания для самостоятельной работы
1. Решить методом Гаусса системы:
а)
=+++
=+−+
=−++
=+++
;1254185
,1895
,3253
,5372
4321
4321
4321
4321
xxxx
xxxx
xxxx
xxxx
б)
=++
=+−
=+−
=++
.0417
,0453
,032
,023
321
321
321
321
xxx
xxx
xxx
xxx
2. Исследовать на совместность системы:
а)
=−+−
=−−
=−+−
=−+−
;1835
,652
,7323
,8234
4321
421
4321
4321
xxxx
xxx
xxxx
xxxx
б)
=−++
=−++
=+−+
=+−+
.37932
,32364
,389128
,132
4321
4321
4321
4321
xxxx
xxxx
xxxx
xxxx
57
Лекция 10
Метод полного исключения. Нахождение
базисных и опорных решений систем
линейных уравнений
Излагается метод полного исключения для решения сис-
тем линейных уравнений, приводятся алгоритмы нахож-
дения базисных и опорных решений таких систем.
1
0
. Метод полного исключения. Для решения ряда задач
достаточно выполнения операций прямого хода. При решении систем
линейных уравнений в Л.9 выполнялись и прямой, и обратный ходы,
в результате которых в расширенной матрице выделялась диагональ-
ная подматрица и цель достигалась.
Оказывается, что диагональную подматрицу можно выделить в
результате прямого хода, если использовать следующий алгоритм.
Первый шаг. Соответствует исключению неизвестной x
1
и выпол-
няется с разрешающим элементом a
11
≠0 по правилам прямого хода.
Общий шаг. Соответствует последовательному исключению не-
известных x
2
, x
3
,... и выполняется по следующим правилам:
1) назначается разрешающий элемент, им будет коэффициент
при исключаемой неизвестной;
2) элементы разрешающей строки остаются неизменными;
3) все элементы разрешающего столбца, кроме разрешающего
элемента, заменяются нулями и остаются таковыми до конца преоб-
разований;
4) все прочие элементы матрицы пересчитываются по правилу
прямоугольника.
Пример 1. Методом полного исключения решить систему урав-
нений:
=++
=+++
=−++
=−++
.2255
,132
,123
,132
321
4321
4321
4321
xxx
xxxx
xxxx
xxxx
Решение. Используем алгоритм полного исключения и после-
довательно получаем следующие матрицы:
58
[]
[]
⇒
−
−
−
−−
−
⇒
−
−
−
−
−−
−−
−−
⇒
−
−
=
2
2
2
0
10
10
2
0
1200
1200
840
404
3
1
2
1
5
3
2
1
1350
510
840
321
2
1
1
1
0
1
1
1
255
132
123
321
B
[]
−
−
⇒
−
−
−
⇒
1
2
1
5
14
5
600
0120
006
1
1
0
5
1
0
600
420
101
.
По последней матрице записываем общее решение системы урав-
нений:
434241
6
5
6
1
,
6
7
6
1
,
6
5
6
1
xxxxxx +=−=+=
где x
4
– любое веще-
ственное число.
2
0
. Нахождение базисных решений системы
линейных уравнений. Совместная система линейных алгебраи-
ческих уравнений называется неопределенной, если она имеет более
одного решения. Важную роль в приложениях, в частности, в линей-
ном программировании играют базисные решения такой системы урав-
нений. Запишем общее решение системы (Л. 9.1) в виде (Л. 9.9):
+++=
+++=
+++=
++
++
++
nrnrrrrr
nnrr
nnrr
xcxccx
xcxccx
xcxccx
%
%%%%%%%%%%%%%
%
%
11,0
211,2202
111,1101
,
,
. (1)
Базисное решение получается из решения (1), если свободным
неизвестным придать нулевые значения, т.е. положить
x
r+1
= x
r+2
= ... = x
n
= 0. Тогда базисные неизвестные будут равны соот-
ветствующим свободным членам, т.е. x
1
= c
10
, x
2
= c
20
, ...,
x
r
= c
r 0
.
Полученное базисное решение (c
10
; c
20
; ..., c
r0
; 0; ...; 0) соответствует
базису (x
1
, ..., x
r
). Если общее решение записать в другом базисе, то
получим другое базисное решение. Поскольку из системы n неизвест-
ных можно образовать не более C
n
r
базисов, то и базисных решений
у системы (Л. 9.1) может быть не более C
n
r
.
Пример 2. Найти все базисные решения системы:
59
=+
=−
=+
.72
,732
,143
32
31
21
xx
xx
xx
(2)
Решение. В результате прямого хода расширенная матрица дан-
ной системы приводится к виду:
⇒
−=
7
7
14
1
3
0
20
02
31
321
xxx
B
(3)
[]
⇒
−−−⇒
−−−⇒
7
14
1
0
20
31
0
21
14
0
3
0
00
60
31
7
21
14
1
3
0
20
60
31
321
321321
xxx
xxxxxx
,
которой соответствует система двух уравнений с тремя неизвестны-
ми. Так что в общем решении системы две базисные неизвестные
линейно выражаются через одну свободную. Возможные свободные
неизвестные x
1
; x
2
или x
3
.
Пусть x
1
= 0. Тогда матрица (3) приобретает вид
7
14
1
0
2
3
3
2
xx
,
из которой следует
3
7
7
3
14
2,
3
14
332
−=⇒=+⋅= xxx
.
Таким образом, в базисе (x
2
, x
3
) базисное решение имеет вид
−
3
7
;
3
14
;0
.
Пусть теперь x
2
=0 . Тогда матрица (3) запишется в форме
7
14
1
0
0
1
31
xx
,
и, значит, x
1
= 14, x
3
=7 , а базисное решение имеет вид (14; 0; 7) .
60
При x
3
=0 матрица (3) имеет вид
7
14
2
3
0
1
21
xx
.
Отсюда
2
7
3
2
7
14,
2
7
12
=⋅−==
xx
. Базисное решение
0;
2
7
;
2
7
. Итак, базисные решения следующие:
()
−
0;
2
7
;
2
7
,7;0;14,
3
7
;
3
14
;0
.
3
0
. Нахождение опорных решений. В приложениях,
особенно в математическом программировании, важную роль игра-
ют базисные решения, в которых базисные неизвестные принимают
неотрицательные значения. Такие решения называют опорными. Что-
бы получить опорное решение неопределенной системы линейных урав-
нений, необходимо с самого начала гауссовых исключений выбирать
разрешающие элементы по определенному правилу.
Во-первых, без ограничения общности рассуждений можно считать,
что все элементы b
i
столбца свободных членов исходной расширенной
матрицы В системы (Л. 9.1) неотрицательны, ибо если это не так, то обе
части соответствующего уравнения нужно умножить на –1.
Опишем правила выбора разрешающих элементов:
1) если в разрешающем столбце есть положительные и отрица-
тельные элементы, то в качестве разрешающего элемента выбирает-
ся такой положительный элемент, для которого отношение свободно-
го члена строки к этому элементу будет наименьшим из всех отношений
свободных членов к соответствующим положительным элементам разре-
шающего столбца;
2) если в разрешающем столбце только неположительные элемен-
ты, то в качестве разрешающего выбирается такой отрицательный эле-
мент, для которого абсолютная величина отрицательного отношения
свободного члена строки к этому элементу будет наибольшей из всех
абсолютных величин отрицательных отношений свободных членов к
соответствующим отрицательным элементам разрешающего столбца.
Дальше определяем те базисные решения, которые являются и
опорными.