Линейни уравнения

Глава 5
Методи за решаване на системи
линейни уравнения
Много задачи от изчислителната математика се свеждат до ре-
шаване на система линейни алгебрични уравнения:
?
?
?
?
?
?
?
?
?
a11x1+a12x2+? ? ?+a1nxn=b1
a21x1+a22x2+? ? ?+a2nxn=b2
.
.
.
.
.
.
.
.
.
.
.
.
an1x1+an2x2+? ? ?+annxn=bn.
Горната система може да се запише като векторно равенство
Ax=b ,
къдетоA= (aij), b= (b1, b2, . . . , bn)
T
иx= (x1, x2, . . . , xn)
T
са съот-
ветно матрицата от коефициенти, векторът от свободни членове и
векторът от неизвестни. По-нататък ще предполагаме, чеAе нео-
собена матрица, т.е. детерминантата `и е различна от нула(|A| 6= 0).
§ 1. Точни (директни) методи за решаване на системи
линейни уравнения
Всяка една система линейни алгебрични уравнения еднозначно
е определена с матрицата
B=






a11a12? ? ?a1n
a21a22? ? ?a2n
.
.
.
.
.
.
.
.
.
.
.
.
an1an2? ? ?ann
?
?
?
?
?
?
?
?
?
?
b1
b2
.
.
.
bn






118

§ 1. Точни методи 119
нареченаразширена матрицана съответната система.
Един числен метод наричаметочен, когато при предположение,
че началните данни са дадени верни и междинните аритметични
операции са краен брой и се извършват точно, то полученото ре-
шение е точно.
1.1. Метод на Гаус
Един от най-използваните методи за решаване на системи ли-
нейни уравнения е методът на Гаус. Този метод притежава различ-
ни модификации и се използва обикновено в два режима – с избор
на главен елемент и без избор на главен елемент.
При метода на Гаус системата линейни уравнения се трансфор-
мира последователно, чрез елементарни преобразования, в екви-
валентни на нея системи до получаване на система с триъгълна
матрица.
Ще разгледаме самосхемата на Гаус без избор на главен еле-
мент, като за целта ще използваме разширената матрицаB. Към
матрицатаBсе добавя обикновено допълнителен, контролен стълб,
но тук ще го пропуснем за простота.
На първата стъпка, първият ред наBсе умножава последо-
вателно с−ai1/a11и се прибавя къмi-ти ред,i= 2,3, . . . , n. В
резултат се получава разширената матрица
B
(1)
=








a
11
a
12
? ? ?a
1n
0a
(1)
22
? ? ?a
(1)
2n
.
.
.
.
.
.
.
.
.
.
.
.
0a
(1)
n2
? ? ?a
(1)
nn
?
?
?
?
?
?
?
?
?
?
?
?
b
1
b
(1)
2
.
.
.
b
(1)
n








,
където
a
(1)
ij
=aij−
ai1
a11
a1j, i, j= 2,3, . . . , n ,
b
(1)
i
=bi−
ai1
a11
b1, i= 2,3, . . . , n .

120Глава 5. Методи за решаване на системи линейни уравнения
На втората стъпка, вторият ред наB
(1)
се умножава последо-
вателно с−a
(1)
i2
/a
(1)
22
и се прибавя къмi-ти ред,i= 3,4, . . . , n. Така
се получава матрицата
B
(2)
=











a
11
a
12
a
13
? ? ?a
1n
0a
(1)
22
a
(1)
23
? ? ?a
(1)
2n
0 0 a
(2)
33
? ? ?a
(2)
3n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 a
(2)
n3
? ? ?a
(2)
nn
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
b
1
b
(1)
2
b
(2)
3
.
.
.
b
(2)
n











,
където
a
(2)
ij
=a
(1)
ij
−
a
(1)
i2
a
(1)
22
a
(1)
2j
, i, j= 3,4, . . . , n ,
b
(2)
i
=b
(1)
i
−
a
(1)
i2
a
(1)
22
b
(1)
2
, i= 3,4, . . . , n .
Следn−1стъпки се получава разширената матрица
B
(n−1)
=














a
11
a
12
a
13
? ? ?a
1,n−1
a
1n
0a
(1)
22
a
(1)
23
? ? ?a
(1)
2,n−1
a
(1)
2n
0 0 a
(2)
33
? ? ?a
(2)
3,n−1
a
(2)
3n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 0 ? ? ?a
(n−2)
n−1,n−1
a
(n−2)
n−1,n
0 0 0 ? ? ?0 a
(n−1)
nn
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
b
1
b
(1)
2
b
(2)
3
.
.
.
b
(n−2)
3
b
(n−1)
n














.
Направените стъпки дотук се наричатправ ходна метода на
Гаус. Следваобратният ход– от матрицатаB
(n−1)
, която е разши-
рена матрица на еквивалентна система на дадената, се определят
неизвестнитеxi, като от последния ред се определяxn. След това

§ 1. Точни методи 121
от предпоследния ред се определяxn−1:
xn=
b
(n−1)
n
a
(n−1)
nn
;xn−1=
1
a
(n−2)
n−1,n−1
?
b
(n−2)
n−1
−a
(n−2)
n−1,n
xn
?
и така нататък. Накрая от първия ред се определяx1:
x1=
1
a11
(b1−a12x2−a13x3− ? ? ? −a1nxn).
Очевидно при прилагането на метода на Гаус без избор на гла-
вен елемент, елементитеa
(i−1)
i i
, които се получават на всяка стъпка,
е необходимо да са различни от нула. Тази разновидност на метода
се използва обикновено, когато изчисленията се правят на ръка,
докато на компютри се реализира методът с избор на главен еле-
мент.
Със следващия пример ще илюстрираме описания метод.
Пример 1.1.Да се решат точно, по метода на Гаус, системите:
а)
?
?
?
?
?
?
?
9x1−6x2−2x3= 10
−2x1+ 8x2−3x3= 0
−x1−4x2+ 6x3= 0 ;
б)
?
?
?
?
?
?
?
−x1−x2+ 6x3= 2
−x1+ 6x2−x3= 34
6x1−x2−x3= 12.
Решение: а)Разширената матрица на системата е
B=



9−6−2
−2 8−3
−1−4 6
?
?
?
?
?
?
?
10
0
0


.
По метода на Гаус на първата стъпка умножаваме първия ред
с2/9и прибавяме към втори ред, умножаваме първия ред с1/9и
прибавяме към трети ред. Така получаваме матрицата
B
(1)
=



9−6−2
0
20
3
−
31
9
0−
14
3
52
9
?
?
?
?
?
?
?
10
20
9
10
9


.

122Глава 5. Методи за решаване на системи линейни уравнения
Следва втората стъпка – умножаваме втория ред на матрицата
B
(1)
с
7
10
и прибавяме към трети ред, с което получаваме матрицата
B
(2)
=



9−6−2
0
20
3
−
31
9
0 0
101
30
?
?
?
?
?
?
?
10
20
9
8
3


,
която е разширена матрица на системата:
?
?
?
?
?
?
?
9x1−6x2−2x3= 10
20
3
x2−
31
9
x3=
20
9
101
30
x3=
8
3
.
Предходните две стъпки бяха от правия ход на метода на Гаус.
Предстои обратният ход, при който се определят стойноститена
неизвестните. От последното уравнение на системата получаваме
x3=
80
101
. Така получената стойност наx3заместваме във второто
уравнение, откъдето изразявамеx2:
x2=
3
20
?
20
9
+
31
9
x3
?
=
1
3
+
31
60
80
101
=
75
101
.
Накрая заместваме стойностите наx2иx3в първото уравнение,
откъдето пресмятаме
x1=
1
9
(10 + 6x2+ 2x3) =
1
9
?
10 + 6
75
101
+ 2
80
101
?
=
180
101
.
б)Разширената матрица на системата е
B=



−1−1 6
−1 6−1
6−1−1
?
?
?
?
?
?
?
2
34
12


.
Умножаваме първия ред наBпоследователно с−1и6и при-
бавяме съответно към втори и трети ред. Получаваме разширената

§ 1. Точни методи 123
матрица
B
(1)
=



−1−1 6
0 7−7
0−7 35
?
?
?
?
?
?
?
2
32
24


,
на която втория ред прибавяме към трети. Така получаваме
B
(2)
=



−1−1 6
0 7−7
0 0 28
?
?
?
?
?
?
?
2
32
56


.
От третия ред на матрицатаB
(2)
определямеx3=
56
28
= 2. От
втория ред имаме
7x2−7x3= 32,
където заместваме вече намерената стойност наx3и получаваме
x2=
1
7
(32 + 7x3) =
46
7
.
От първия ред наB
(2)
имаме−x1−x2+ 6x3= 2, откъдето
x1= 2 +x2−6x3=
24
7
.
Методът на Гаус е много удобен и за пресмятане на детерминан-
ти на матрици. Например детерминантите на матриците на систе-
мите от пример 1.1 съответно са:9.
20
3
.
101
30
= 202и(−1).7.28 =−196.
1.2. Метод на Гаус-Жордан
Методът на Гаус-Жордан е модификация на метода на Гаус, при
който в процеса на преобразованията вместо триъгълна матрица се
получава диагонална. Този метод също има два режима – с избор
на главен елемент и без избор. Ще опишем метода без избор на
главен елемент.
Първата стъпка съвпада с тази на метода на Гаус, т.е. от раз-
ширената матрицаBсе получава матрицатаB
(1)
.

124Глава 5. Методи за решаване на системи линейни уравнения
На втората стъпка, вторият ред наB
(1)
се умножава последо-
вателно с−a
(1)
i2
/a
(1)
22
и се прибавя къмi-ти ред,i= 3,4, . . . , n, както
при метода на Гаус. Освен това, същият втори ред се умножава
с−a12/a
(1)
22
и се прибавя към първи ред. В резултат се получава
матрицата
B
(2)
=











a110a
(1)
13
? ? ?a
(1)
1n
0a
(1)
22
a
(1)
23
? ? ?a
(1)
2n
0 0 a
(2)
33
? ? ?a
(2)
3n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 a
(2)
n3
? ? ?a
(2)
nn
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
b
(1)
1
b
(1)
2
b
(2)
3
.
.
.
b
(2)
n











,
където
a
(1)
1j
=a1j−
a12
a
(1)
22
a
(1)
2j
, j= 3, . . . , n ,
b
(1)
1
=b1−
a12
a
(1)
22
b
(1)
2
,
a
(2)
ij
=a
(1)
ij
−
a
(1)
i2
a
(1)
22
a
(1)
2j
, i, j= 3, . . . , n ,
b
(2)
i
=b
(1)
i
−
a
(1)
i2
a
(1)
22
b
(1)
2
, i= 3, . . . , n .
На третата стъпка, третият ред се умножава с
−
a
(1)
13
a
(2)
33
,−
a
(1)
23
a
(2)
33
,−
a
(2)
i3
a
(2)
33
и се прибавя съответно към първи, втори иi-ти ред,i= 4, . . . , n.

§ 1. Точни методи 125
Така се получава матрицата
B
(3)
=














a110 0 a
(2)
14
? ? ?a
(2)
1n
0a
(1)
22
0a
(2)
24
? ? ?a
(2)
2n
0 0 a
(2)
33
a
(2)
34
? ? ?a
(2)
3n
0 0 0 a
(3)
44
? ? ?a
(3)
3n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
0 0 0 a
(3)
n4
? ? ?a
(3)
nn
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
b
(2)
1
b
(2)
2
b
(2)
3
b
(3)
4
.
.
.
b
(3)
n














,
където
a
(2)
ij
=a
(1)
ij
−
a
(1)
i3
a
(2)
33
a
(2)
3j
, i= 1,2, j= 3, . . . , n ,
b
(2)
i
=b
(1)
i
−
a
(1)
i3
a
(2)
33
b
(2)
3
, i= 1,2,
a
(3)
ij
=a
(2)
ij
−
a
(2)
i2
a
(2)
33
a