kurs_lekcii_mo_matematicheskomu_analizu / Лекции Кисляков
.pdf1.2. Решение линейных уравнений. |
11 |
1.2Решение линейных уравнений.
Мы покажем как решать любую систему линейных уравнений над произвольным полем, используя алгоритм Гаусса-Жордана. Снача- ла определим некоторые понятия.
Определение 1.2.1 (Ступенчатая форма) Матрица имеет ступенчатую форму, åñëè
(i)все нулевые строки (если они есть) находятся в нижней части матрицы и
(ii)если две соседние строки ненулевые, вторая строка начинается с большего числа нулей чем первая (двигаясь слева направо).
Например, матрица
20 |
1 |
0 |
03 |
60 0 1 07
67
40 0 0 05
0 0 0 0
имеет ступенчатую форму, в то время как другая матрица
20 |
1 |
0 |
03 |
60 1 0 07
67
40 0 0 05
0 0 0 0
не имеет ступенчатой формы.
Нулевая матрица любого размера всегда имеет ступенчатую фор-
ìó.
Определение 1.2.2 (Привед¼нная ступенчатая форма) Матрица имеет привед¼нную ступенчатую форму åñëè
12 |
Глава 1. Линейные уравнения |
1.она имеет ступенчатую форму,
2.ведущий (первый слева, ненулевой) элемент в каждой ненулевой строке равен 1,
3.все другие элементы столбца, в котором ведущий элемент равен 1, равны нулю.
Например, матрицы
|
|
|
20 |
1 |
2 |
0 |
0 |
23 |
1 |
0 |
|
0 |
0 |
0 |
1 |
0 |
3 |
0 |
1 |
è |
0 0 0 |
0 |
1 |
4 |
||
|
|
|
60 |
0 |
0 |
0 |
0 |
07 |
|
|
|
6 |
|
|
|
|
7 |
|
|
|
4 |
|
|
|
|
5 |
имеют привед¼нную ступенчатую форму, в то время как матрицы
20 |
1 |
03 |
è |
20 |
1 |
03 |
1 |
0 |
0 |
|
1 |
2 |
0 |
40 |
0 |
25 |
|
40 |
0 |
05 |
не имеют привед¼нной ступенчатой формы, но имеют ступенчатую форму.
Нулевая матрица любого размера всегда имеет привед¼нную ступенчатую форму.
Примечание. Если матрица имеет привед¼нную ступенчатую форму, то номера столбцов, в которых находятся ведущие элементы равные 1, удобно обозначить через c1; c2; : : : ; cr; а оставшиеся столб-
цы пронумеруем как cr+1; : : : ; cn, здесь r есть число ненулевых строк. Например, для 4 6 матрицы привед¼нной выше, мы имеем
r = 3; c1 = 2; c2 = 4; c3 = 5; c4 = 1; c5 = 3; c6 = 6.
Следующие действия используются для преобразования систем линейных уравнений и не изменяют их решений.
Определение 1.2.3 (Элементарные действия над строками)
Òðè òèïà элементарных действий над строками матрицы могут быть представлены в виде матриц:
1.2. Решение линейных уравнений. |
13 |
1.Перестановка двух строк:
Ri $ Rj переставляет строки i и j.
2.Умножение строки на ненулевой скаляр: Ri ! tRi умножает строку i на ненулевой скаляр t.
3.Кратное прибавление одной строки к другой строке: Rj ! Rj + tRi прибавляет t раз строку i к строке j.
Определение 1.2.4 (Построчная эквивалентность) Матрица
A строчно эквивалентна матрице B, если B получается из A с помощью последовательности элементарных действий над строками.
Пример 1.2.1 Перемещаясь слева направо,
|
A = |
22 1 |
13 |
R2 ! R2 + 2R3 |
24 |
1 |
53 |
|||||||||
|
|
|
1 |
2 |
0 |
5 |
|
|
|
|
24 |
1 |
|
2 |
0 |
5 |
|
|
|
4 |
1 |
2 |
0 |
|
|
|
1 |
4 |
0 |
2 |
|||
|
|
|
1 |
1 |
2 |
|
23 |
|
|
|
21 |
1 |
|
|||
R2 |
$ |
R3 |
21 |
1 |
R1 |
! |
2R1 |
1 |
23 |
= B. |
||||||
|
|
|
44 |
1 |
55 |
|
|
44 |
1 |
55 |
|
|||||
Таким образом, A строчно эквивалентна |
B. Ясно, что B также |
|||||||||||||||
строчно эквивалентна A, в этом можно убедиться выполнив обрат-
ные действия над строками R1 ! 12 R1; R2 $ R3; R2 ! R2 2R3 матрицы B.
Нетрудно доказать утверждение: если A и B есть строчно эк-
вивалентные расширенные матрицы двух систем линейных уравнений, тогда две системы имеют одно множество решений, то есть решение одной системы является решением другой. Например, системы с расширенными матрицами A и B из рассмотренного выше
примера, имеют вид, соответственно
8 2x++2y = 1 |
è |
8 2 x+ 4y = 2 |
|||||
< |
x |
|
y = 0 |
|
< |
x |
y = 0 |
x |
|
y = 2 |
|
4x |
y = 5 |
||
: |
|
|
|
: |
|
|
|
и у этих систем в точности одно решение.
14 |
Глава 1. Линейные уравнения |
1.3Алгоритм Гаусса-Жордана
Теперь мы опишем АЛГОРИТМ ГАУССА-ЖОРДАНА. Это процесс, который начинается с данной матрицы A и производит мат-
рицу B, которая имеет привед¼нную ступенчатую форму и строчно эквивалентна A. Если A есть раширенная матрица системы линейных уравнений, то B будет значительно более простой матрицей чем A из которой явно видно совместна или несовместна соответ-
ствующая система и, фактически, может быть отсчитано полное решение системы.
ØÀÃ 1.
Двигаясь слева направо найд¼м первый ненулевой столбец и присвоим ему номер c1), затем выберем ненулевой элемент в этом столбце. Меняя местами строки, если это необходимо, обеспечим, чтобы первый элемент выбранного столбца был ненулевым. Умно- жаем первую строку на обратный a1c1 элемент, тем самым обра- ùàåì a1c1 в 1. Для каждого ненулевого элемента aic1 ; i > 1,(если они есть) в столбце c1, прибавляем aic1 раз первую строку к i-òîé строке, тем самым обеспечиваем, чтобы все элементы в столбце c1, не считая первого, были равны нулю.
ØÀÃ 2.
Если матрица, полученная на Шаге 1 имеет вторую,..., m-тую
строки нулевые, то эта матрица имеет привед¼нную ступенчатую форму. В другом случае, предположим, что первый столбец, который содержит ненулевой элемент в строках ниже первой, есть столбец c2. Тогда c1 < c2. Переставляя строки ниже первой, если
это необходимо, обеспечим, чтобы элемент a2c2 был ненулевой. За- тем обращаем a2c2 в 1 и, прибавляя подходящее число раз вторую строку к оставшимся, к тем где это необходимо, обеспечим, чтобы все оставшиеся элементы в столбце c2 были нулевые.
Процесс повторяется и, очевидно, закончится после r шагов, или
потому что мы пройд¼м все строки, или потому что мы пройд¼м все ненулевые столбцы. В общем случае, окончательная матрица будет
1.3. Алгоритм Гаусса-Жордана |
15 |
иметь привед¼нную ступенчатую форму и r ненулевых строк, с ве-
дущими элементами равными 1 в столбцах c1; : : : ; cr, соответствен- íî.
Пример 1.3.1 |
22 |
2 |
2 |
|
53 |
R1 |
$ R2 |
20 |
0 |
4 |
03 |
|
||||||||
|
|
|
|
|
0 |
0 |
4 |
|
0 |
|
|
|
|
|
|
2 |
2 |
2 |
5 |
|
|
|
|
1 1 |
4 |
1 5 |
|
|
5 |
|
|
|
|
|
41 1 |
1 |
55 |
|
|||
R1 ! 2 R1 |
|
|
|
5 |
5 |
1 |
|
5 |
|
|
|
|
|
|
5 |
5 |
1 |
5 |
|
|
|
20 0 4 03 |
R3 ! R3 5R1 |
20 0 4 |
015 3 |
||||||||||||||||
|
1 |
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
2 |
|
|
|
|
45 5 1 55 |
R2 |
! |
|
|
|
|
|
40 0 4 2 5 |
|||||||||
4 R2 |
20 0 1 |
|
5 |
3 |
f R3 |
|
R3 |
|
4R2 |
|
|
|
15 |
3 |
||||||
|
0 |
|
! |
|
20 0 4 0 |
|||||||||||||||
1 |
1 1 |
1 |
|
2 |
|
R1 |
|
|
R1 |
+ R2 |
|
1 1 0 |
2 |
5 |
||||||
|
4 |
|
|
|
1 15 0 |
25 |
|
|
! |
|
|
|
|
|
4 1 |
1 0 |
0 |
|||
|
0 0 |
4 |
|
15 |
|
|
|
|
|
|
|
|
0 |
0 4 |
15 |
|
||||
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
20 |
|
2 |
|
R3 |
! |
152 R3 |
20 0 1 03 |
|
R1 |
! |
R1 |
|
25 R3 |
0 1 03 |
|
|||||||||
|
|
|
40 0 0 15 |
|
|
|
|
|
|
40 |
0 0 15 |
|
||||||||
Последняя матрица имеет привед¼нную ступенчатую форму.
Замечание 1.3.1 Возможно показать, что данная матрица над произвольным полем строчно эквивалентна в точности одной матрице, которая имеет привед¼нную ступенчатую форму.
Диаграмма для алгоритма Гаусса-Жордана представлена на рис. ??.
16 |
Глава 1. Линейные уравнения |
1.4Систематическое решение линейных систем.
Предположим, что система m линейных уравнений с n неизвестными x1; : : : ; xn имеет расширенную матрицу A. И B это матрица, которая имеет привед¼нную ступенчатую форму и получена из A с помощью алгоритма Гаусса-Жордана. Тогда A строчно эквивалентна матрице B и обе матрицы имеют размер m n. Предположим, что B имеет r ненулевых строк и что ведущий элемент 1 в i-той строке находится в столбце с номером ci, для 1 i r. Тогда
1 c1 < c2 < < cr n + 1:
А также предположим, что оставшиеся столбцы имеют номера cr+1; ; cn+1, ãäå
1 cr+1 < cr+2 < < cn n + 1:
Случай 1: cr = n+1. Система несовместна. Последняя ненулевая строка матрицы B есть [0; 0; ; 1] и соответствующее уравнение выглядит так
0x1 + 0x2 + + 0xn = 1;
и не имеет решений. Следовательно, первоначальная система тоже не имеет решений.
Случай 2: cr n. Система уравнений, соответствующая ненулевым строкам B совместна. Сначала заметим, что выполняется неравенство r n.
Если r = n; тогда c1 = 1; c2 = 2; ; cn = n è
1.4. Систематическое решение линейных систем. |
17 |
||||
20 |
1 |
|
0 |
d23 |
|
1 |
0 |
|
0 |
d1 |
|
6 |
|
|
|
7 |
|
67
B = |
60. |
0 |
1 d. 7 |
: |
|
6 |
|
7 |
|
|
6 |
|
7 |
|
6n7
60 |
0 |
|
0 |
0 7 |
|
6 |
|
|
|
0. |
7 |
60. |
0 |
|
0 |
7 |
|
4 |
|
|
|
|
5 |
В этом случае мы имеем единственное решение x1 = d1; x2 = d2; ; xn = dn.
Если r < n, тогда имеется более одного решения (бесконечное
множество, если поле бесконечное). Для того чтобы получить все решения, мы полагаем, что неизвестные xc1 ; ; xcr есть зависимые неизвестные и используем r уравнений, соответствующих ненуле-
вым строкам B для того, чтобы выразить эти неизвестные через
оставшиеся, независимые неизвестные xcr+1 ; : : : ; xcn , которые могут принимать произвольные значения:
xc1 = b1n+1 b1cr+1 xcr+1 b1cn xcn
.
xcr = brn+1 brcr+1 xcr+1 brcn xcn :
В частности, если взять xcr+1 = 0; : : : ; xcn 1 = 0 è xcn = 0; 1 соответственно, то мы получим не меньше двух решений.
Пример 1.4.1 Решить систему
x + y |
= |
0 |
x y |
= |
1 |
4x + 2y |
= |
1: |
Решение. Расширенная матрица системы есть
A = |
21 |
1 |
13 |
|
1 |
1 |
0 |
|
44 |
2 |
15 |
18 |
|
|
Глава 1. Линейные уравнения |
|||
она строчно эвивалентна матрице |
|
|
|
|
|
|
B = |
20 |
1 |
1 |
3 |
: |
|
21 |
|
|||||
|
1 |
0 |
2 |
|
|
|
|
40 |
|
5 |
|
|
|
|
0 |
0 |
|
|
||
Мы получили единственное решение x = 21 ; y = 21 |
. (Здесь n = |
|||||
2; r = 2; c1 = 1; c2 = 2: А также cr = c2 = 2 < 3 = n + 1 è r = n:)
Пример 1.4.2 Решить систему
2x1 + 2x2 2x3 |
= 5 |
|
7x1 + 7x2 + x3 |
= |
10 |
5x1 + 5x2 x3 |
= |
5: |
Решение. Расширенная матрица есть
|
2 |
2 |
2 |
5 |
3 |
|
2 |
5 |
|||
A |
7 |
7 |
1 |
10 |
|
|
= 45 |
5 |
1 |
5 |
она строчно эквивалентна
B = |
20 |
0 |
1 |
03 |
: |
|
1 |
1 |
0 |
0 |
|
|
40 |
0 |
0 |
15 |
|
Мы получили несовместность первоначальной системы. (Здесь n = 3; r = 3; c1 = 1; c2 = 3: А также cr = c3 = 4 = n + 1:)
Пример 1.4.3 Решить систему
x1 x2 + x3 |
= |
1 |
: |
x1 + x2 x3 |
= |
2 |
|
Решение. Расширенная матрица данной системы есть
1.4. Систематическое решение линейных систем. |
19 |
||||||
|
|
1 |
|
|
|
|
|
A = |
1 |
1 |
|
1 |
|
||
|
1 |
1 |
|
1 |
|
2 |
|
она эквивалентна матрице |
|
|
|
|
|
|
|
B = |
0 1 |
1 |
3 |
: |
|
||
21 |
|
||||||
|
1 |
0 |
|
0 |
2 |
|
|
|
|
|
|
|
|
|
|
Полное решение системы: x1 = 32 ; x2 = 12 + x3; ãäå x3 произволь- на. (Здесь n = 3; r = 2; c1 = 1; c2 = 2: А также cr = c2 = 2 < 4 =
n + 1 è r < n:
Пример 1.4.4 Решить систему
6x3 + 2x4 4x5 8x6 |
= 8 |
|
3x3 + x4 2x5 4x6 |
= 4 |
|
2x1 3x2 + x3 + 4x4 7x5 + x6 |
= |
2 |
6x1 9x2 + 11x4 19x5 + 3x6 |
= |
1: |
Пример 1.4.5 Расширенная матрица системы:
A = |
20 0 |
3 1 |
2 |
4 |
43 |
||||
|
|
0 |
0 |
|
6 |
2 |
4 |
8 |
8 |
|
66 |
9 |
0 |
11 |
19 |
3 |
17 |
||
|
6 |
|
|
|
|
|
|
|
7 |
|
4 |
2 |
3 |
1 |
4 |
7 |
1 |
2 |
|
|
|
|
|
|
|
|
|
5 |
|
она строчно эквивалентна матрице
1 |
|
3 |
0 |
11 |
19 |
0 |
1 |
|
||
B = 20 0 |
1 |
3 |
|
3 |
0 |
|
|
3: |
||
13 |
||||||||||
|
|
2 |
|
1 |
|
2 |
|
5 |
|
|
60 |
|
|
6 |
|
6 |
|
24 |
7 |
||
0 |
0 |
0 |
0 |
0 |
0 |
|||||
6 |
0 |
0 |
0 |
0 |
1 |
|
|
7 |
||
0 |
4 |
5 |
||||||||
4 |
|
|
|
|
|
|
|
|
|
|
Полное решение:
x1 |
= |
1 |
+ 23 x2 |
116 x4 + 196 x5; |
|||
24 |
|||||||
|
|
5 |
|
1 |
|
2 |
|
x3 |
= |
1 |
3 x4 |
+ 3 x5; |
|||
3 |
|
|
|||||
x6 |
= |
4 ; |
|
|
|
||
20 Глава 1. Линейные уравнения
ãäå x2; x4; x5 произвольны. (Здесь n = 6; r = 3; c1 = 1; c2 = 3; c3 = 6; cr = c3 = 6 < 7 = n + 1; r < n:)
Пример 1.4.6 Найти рациональное число t для которого следую-
щая система совместна и решить эту систему для этого значения параметра t.
x + y |
= |
2 |
x y |
= |
0 |
3x y |
= |
t: |
Решение. Расширенная матрица системы есть
21 |
1 |
23 |
A = 41 |
1 |
05 |
3 |
1 |
t |
она строчно эквивалентна более простой матрице
23
1 |
1 |
2 |
|
0 |
1 |
1 |
: |
B = 40 |
0 |
t 25 |
|
Следовательно, если t 6= 2, то система несовместна. Если t = 2, то система совместна и
B = |
20 |
1 |
13 20 |
1 |
13 |
|
|
1 |
1 |
2 |
1 |
0 |
1 |
|
40 |
0 |
05 ! 40 |
0 |
05 |
|
Получаем решения x = 1; y = 1.
Пример 1.4.7 Для каких рациональных чисел a и b следующая система (i) не имеет решений, (ii) имеет единственное решение, (iii) имеет бесконечное множество решений?
x 2y + 3z |
= |
4 |
2x 3y + az |
= |
5 |
3x 4y + 5z |
= |
b: |