Układ równań liniowych
a
11
x
1
+ a
11
x
2
+...+ a
1n
x
n
= b
1
a
21
x
1
+ a
22
x
2
+...+ a
2n
x
n
= b
2
....................
a
n1
x
1
+ a
n2
x
2
+...+ a
nn
x
n
= b
n
=
⋅
⋅
⋅
n
n
nn
n
n
n
n
b
b
b
x
x
x
a
a
a
a
a
a
a
a
a
.
.
......
..........
..........
2
1
2
1
2
1
2
22
21
1
12
11
Zakładamy , ze znamy macierz współczynników a
ij
oraz wektor b
1
. Poszukujemy wektora
wartości x
i
.
Dopuszczamy operacje elementarne .
a) Pomnożenie wiersza przez stałą
b) Podzielenie wiersza przez stałą
c) Dodanie do pewnego wiersza innego wiersza
d) Objęcie od pewnego wiersza innego wiersza
e) Zamiana wierszy miejscami
Dopuszczalne są także operacje kombinowane , z których szczególnie ważne jest objęcie od
pewnego wiersza innego wiersza przemnożonego przez stałą (czyli (a)+(b)).
Metoda eliminacji Gaussa .
Przykład [Fogiel]
2x
1
+ 4x
2
+ 2x
3
= 16
W
1
(0)
2x
1
– x
2
– 2x
3
= -6
W
2
(0)
4x
1
+ x
2
– 2x
3
= 0
W
3
(0)
Eliminacja zmiennych .
2x
1
+ 4x
2
+ 2x
3
= 16
W
1
(1)
= W
1
(0)
-5x
2
-4x
3
= -22
W
2
(1)
= W
2
(0)
– W
1
(0)
-7x
2
– 6x
3
= -32
W
3
(1)
= W
3
(0)
– 2 W
1
(0)
2x
1
+ 4x
2
+ 2x
3
= 16
W
1
(2)
= W
1
(1)
-5x
2
-4x
3
= -22
W
2
(2)
= W
2
(1)
5
6
5
2
3
−
=
− x
W
3
(2)
= W
3
(1)
-
5
7
W
2
(1)
Postępowanie odwrotne .
x
3
=
5
2
5
6
−
−
x
⇒
3
=3
x
2
=
5
1
−
(-22 + 4 *3)
x
⇒
2
= 2
x
1
=
2
1
(16 –
3 -
2)
x
⋅
2
⋅
4
⇒
1
= 1
Ogólne
.
=
)
0
(
)
0
(
)
0
(
2
)
0
(
1
2
1
)
0
(
)
0
(
)
0
(
2
)
0
(
1
)
0
(
)
0
(
3
)
0
(
2
)
0
(
1
)
0
(
2
)
0
(
2
)
0
(
22
)
0
(
21
)
0
(
)
0
(
1
)
0
(
12
)
0
(
11
n
k
n
k
nn
nk
n
n
kn
k
k
k
n
k
in
k
b
b
b
b
x
x
x
x
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
I. “Eliminacja
zmiennych.
=
)
1
(
)
1
(
)
1
(
2
)
1
(
1
2
1
)
1
(
)
1
(
)
1
(
2
)
1
(
)
1
(
3
)
1
(
2
)
1
(
2
)
1
(
2
)
1
(
22
)
1
(
)
1
(
1
)
1
(
12
)
0
(
11
0
0
0
n
k
n
k
nn
nk
n
kn
k
k
n
k
in
k
b
b
b
b
x
x
x
x
a
a
a
a
a
a
a
a
a
a
a
a
a
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
)
0
(
1
)
0
(
11
)
0
(
1
)
0
(
1
)
1
(
1
)
0
(
1
)
0
(
11
)
0
(
1
)
0
(
)
1
(
)
0
(
1
)
0
(
11
)
0
(
21
)
0
(
2
)
1
(
2
)
0
(
1
)
1
(
1
W
a
a
W
W
W
a
a
W
W
W
a
a
W
W
W
W
n
k
k
k
⋅
−
=
⋅
−
=
⋅
−
=
=
L
L
=
)
(
)
(
)
(
2
)
(
1
2
1
)
(
)
(
)
(
3
)
(
2
)
(
2
)
(
22
)
(
)
(
1
)
(
12
)
(
11
0
0
0
0
0
0
k
n
k
k
k
k
n
k
k
nn
k
kn
k
k
k
n
k
k
k
k
in
k
k
k
k
b
b
b
b
x
x
x
x
a
a
a
a
a
a
a
a
a
a
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
)
1
(
1
)
1
(
)
1
(
)
(
)
(
)
1
(
)
(
)
1
(
2
)
(
2
)
1
(
1
)
(
1
−
−
−
−
−
−
−
⋅
−
=
=
=
=
k
k
kk
k
nk
k
n
k
n
k
k
k
k
k
k
k
k
W
a
a
W
W
W
W
W
W
W
W
L
L
Ostatecznie po (n-1) krokach otrzymujemy .
=
−
−
−
−
−
−
−
−
−
−
)
1
(
)
1
(
)
1
(
2
)
1
(
1
2
1
)
1
(
)
1
(
)
1
(
)
1
(
2
)
1
(
2
)
1
(
22
)
1
(
)
1
(
1
)
1
(
12
)
1
(
11
0
0
0
0
0
0
n
k
n
k
n
nn
n
kn
n
kk
n
n
n
k
n
n
in
n
k
n
n
b
b
b
b
x
x
x
x
a
a
a
a
a
a
a
a
a
a
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
L
II. “Postępowanie odwrotne“ .
(1)
)
1
(
)
1
(
−
−
=
n
nn
n
n
n
a
b
x
∑
+
=
−
−
−
⋅
−
=
+
−
n
p
r
r
n
pr
n
p
n
pp
p
x
a
b
a
x
p
n
1
)
1
(
)
1
(
)
1
(
]
[
1
)
1
(
(n)
∑
=
−
−
−
⋅
−
=
n
r
r
n
r
n
n
x
a
b
a
x
2
)
1
(
1
)
1
(
1
)
1
(
11
1
]
[
1
Zapis skrócony .
Dane : macierz współczynników
n
j
n
i
a
ij
,
,
1
,
,
,
1
,
)
0
(
K
K
=
=
wektor
współczynników
n
i
b
i
,
,
1
,
)
0
(
K
=
Poszukujemy rozwiązania postaci wektora x
i
, i=1 , ... , n .
I.
Etap “eliminacja zmiennych”
k-ty krok , gdzie k=1, ... ,n-1
=
=
−
−
)
1
(
)
(
)
1
(
)
(
k
i
k
i
k
ij
k
ij
b
b
a
a
n
j
k
i
,
,
1
,
,
1
K
L
=
=
uwaga
(*)
⋅
−
=
⋅
−
=
−
−
−
−
−
−
−
−
)
1
(
)
1
(
)
1
(
)
1
(
)
(
)
1
(
)
1
(
)
1
(
)
1
(
)
(
k
k
k
kk
k
ik
k
i
k
i
k
kj
k
kk
k
ik
k
ij
k
ij
b
a
a
b
b
a
a
a
a
a
n
j
n
k
i
,
,
1
,
,
1
K
K
=
+
=
uwaga(**)
II. Etap
“postępowanie odwrotne”
)
1
(
)
1
(
−
−
=
n
nn
n
n
n
a
b
x
krok
pierwszy
∑
+
=
−
−
−
−
=
n
p
r
r
n
pr
n
p
n
pp
p
x
a
b
a
x
1
)
1
(
)
1
(
)
1
(
]
[
1
n
-1 pozostałych kroków
p=n
-1,...,1
Komentarz :
(*) Jeśli w programie wykonujemy modyfikację wg. Etapu “eliminacji zmiennych” używając
tylko jednej macierzy A , wówczas operacji przypisania (*) nie trzeba w ogóle wykonywać.
(**) Obejmując wiersze od siebie , można ograniczyć nie tylko do
.gdyż w
pozostałych przypadkach są to operacje typu “0-0” (wystarczy też tylko
j>k , ale wówczas
macierzy górno-trójkątnej już nie dostajemy)
k
j
≥
Metoda Gaussa “skaluje” się jak
N
3
(N liczba równań)
Uwagi !
Załóżmy , że otrzymaliśmy macierz a w następującej formie (po (1) kroku operacji )
−
=
4
10
6
8
7
0
1
0
0
4
3
2
3
2
1
x
x
x
Algorytmu wyżej opisanego nie można stosować , gdyż na przekątnej mamy 0 . Można go
jednak stosować , jeśli zamienimy wiersze 2 i 3 (dotyczyć to może także wartości wektora B)
Częściowy wybór elementu podstawowego polega na wyszukiwaniu przed każdym krokiem
eliminacji zmiennych największego co do modułu elementu
w ciągu elementów
dla wszystkich kroków .
)
1
(
−
k
)
1
(
k
−
rk
a
)
,
,
1
,
(
n
k
k
i
a
ik
K
+
=
Po ustaleniu numeru
r równania , w którym ten element występuje , wiersz o numerze r
zamieniony jest miejscem z wierszem o numerze
k .
Stosując metody eliminacji Gaussa można także obliczać macierz odwrotną
A
-1
.
−
−
−
−
−
−
−
=
−
−
−
−
−
−
−
−
−
−
−
−
−
−
1
0
0
0
1
0
0
0
1
44
42
41
24
22
21
14
12
11
44
42
41
24
22
21
14
12
11
x
x
x
x
x
x
x
x
x
a
a
a
a
a
a
a
a
a
potęgowanie względem macierzy
A podczas eliminacji zmiennych jest identyczne jak podczas
szukania pojedynczego wektora wartości
x
i
.
Jednak operacje na wektorze wartości
b
i
należy teraz zastąpić operacjami na macierzy
b
ij
.
Rozwiązanie cząstkowe układu równań liniowych metodą Gaussa .
=
+
+
+
−
=
−
+
+
−
=
+
+
+
−
=
−
+
−
10
4
3
1
1
8
1
1
2
2
2
0
1
1
1
8
1
2
1
1
4
3
2
1
4
3
2
1
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
rozwiązanie
2
2
3
7
4
3
2
1
=
=
=
−
=
x
x
x
x
=
+
+
+
=
+
−
+
=
+
−
+
−
=
−
+
−
18
5
1
2
0
8
1
3
4
0
6
1
1
2
0
8
1
2
1
1
4
3
2
1
4
3
2
1
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
)
0
(
1
)
0
(
4
)
1
(
4
)
0
(
1
)
0
(
3
)
1
(
3
)
0
(
1
)
0
(
2
)
1
(
2
)
0
(
1
)
1
(
1
2
W
W
W
W
W
W
W
W
W
W
W
−
=
−
=
−
=
=
=
+
+
+
−
=
−
−
+
=
+
−
+
−
=
−
+
−
12
4
2
0
0
4
1
1
0
0
6
1
1
2
0
8
1
2
1
1
4
3
2
1
4
3
2
1
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
)
1
(
2
)
1
(
4
)
2
(
4
)
1
(
2
)
1
(
3
)
2
(
3
)
1
(
2
)
2
(
2
)
1
(
1
)
2
(
1
2
W
W
W
W
W
W
W
W
W
W
−
=
−
=
=
=
=
+
+
+
−
=
−
−
+
=
+
−
+
−
=
−
+
−
4
2
0
0
0
4
1
1
0
0
6
1
1
2
0
8
1
2
1
1
4
3
2
1
4
3
2
1
4
3
2
1
4
3
2
1
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
( )
)
2
(
3
)
2
(
4
)
3
(
4
)
2
(
3
)
3
(
3
)
2
(
2
)
3
(
2
)
2
(
1
)
3
(
1
2
W
W
W
W
W
W
W
W
W
−
−
=
=
=
=
Postępowanie odwrotne :
(1) 2x
4
=4
x
4
=2
(2) -1
x
3
-1
x
4
=-4
x
3
=-(-4
x+1x
4
)
x
3
=-(-4+2)=2
(3) 2
x
2
-1
x
3
+ 1
x
4
=6
3
)
2
2
6
(
)
1
1
6
(
2
1
2
4
3
2
1
2
=
−
+
=
−
+
=
x
x
x
x
(4)
8
1
2
1
1
4
3
2
1
−
=
−
+
−
x
x
x
x
7
2
4
3
8
1
2
1
8
1
4
3
2
1
−
=
+
−
+
−
=
+
−
+
−
=
x
x
x
x
x
[Burden]
(po modyfikacji)
Przykład różnej dokładności w wynikowej dla różnych algorytmów :
ZADANIE
[Fogiel]
Rozwiązać układ równań
600
200
200
801
400
=
+
=
+
y
x
y
x
Stosując arytmetykę zmienno pozycyjną z trzema cyframi znaczącymi (stosując zaokrąglenia
błędów).
Porównać otrzymane rozwiązanie z rozwiązaniem dokładnym .
x=1 , y=2
Metoda pierwsza
1)
/
801
400
=
+
y
x
)
200
(
−
⋅
600
200
200
=
+
y
x
2)
pozostawiamy trzy cyfry zn.
160200
80000
200
−
=
−
−
y
x
600
200
200
=
+
y
x
160000
80000
200
−
=
−
−
y
x
dodajemy
stronami
600
200
200
=
+
y
x
3)
pozostawiamy
trzy
cyfry
zn
159000
79800
−
=
−
y
159000
7900
−
=
−
y
99
.
1
=
y
1,992
159000 : 79800
79800
792000
718200
738000
718200
198000
159600
38400
4)
00
,
5
796
801
801
99
,
1
400
=
−
=
=
⋅
+
x
x
x
Otrzymujemy ostatecznie : x=5,00 , y=1,99
(fatalnie !)
Metoda druga
1)
po zamianie wierszy dzielimy przez (-200)
600
200
200
=
+
y
x
801
400
=
+
y
x
2)
3
−
=
−
−
y
x
801
400
=
+
y
x
dodajemy stronami
3)
798
399
=
y
00
,
2
=
y
4)
600
400
200
=
+
x
100
200
200
=
=
x
x
Ostatecznie dostajemy : x=1,00 , y=2,00
(b.dobrze
!)
Metoda pierwsza w teorii rozwiązywania układów równań liniowych nazywana jest metodą
eliminacji Gaussa , metoda druga to metoda eliminacji Gaussa z częściowym wyborem
elementu podstawowego.
Metoda rozkładu
L-U :
Dokonuje się rozkładu pierwotnej macierzy A:
A
U
L
=
⋅
gdzie L jest macierzą dolno-trójkątną , a U jest macierzą górno-trójkątną .
=
L
elementy niezerowe tylko na dolnej diagonali i powyżej
=
V
elementy niezerowe tylko górnej diagonali i powyżej
czyli (L U)X=B
Znając
rozwiązujemy najpierw układ
U
L ,
B
Y
L
=
⋅
A następnie
UX=Y ,
Metoda faktoryzacji
LU jest trudniejsza do programowania niż met. eliminacji Gaussa , ale
efektywniejsza w różnych zastosowaniach .
Metoda eliminacji Jordana w uogólnieniu :
=
)
0
(
)
0
(
2
)
0
(
1
2
1
)
0
(
)
0
(
2
)
0
(
1
)
0
(
2
)
0
(
22
)
0
(
21
)
0
(
1
)
0
(
12
)
0
(
11
n
n
nn
n
n
n
n
b
b
b
x
x
x
a
a
a
a
a
a
a
a
a
L
L
L
L
L
L
L
L
L
1)
A:
)
0
(
11
)
0
(
1
)
1
(
1
)
0
(
11
)
0
(
1
)
1
(
1
,
,
1
a
b
b
n
j
a
a
a
j
j
=
=
=
K
B:
⋅
−
=
⋅
−
=
)
1
(
1
)
0
(
1
)
0
(
)
1
(
)
1
(
1
)
0
(
1
)
0
(
)
1
(
b
a
b
b
a
a
a
a
i
i
i
j
i
il
ij
n
j
n
i
,
,
1
,
,
2
K
K
=
=
2)
A:
)
1
(
)
1
(
)
1
(
)
1
(
)
1
(
)
(
,
,
−
−
−
−
=
=
=
k
kk
n
n
n
k
kk
k
kj
k
kj
a
b
b
n
k
j
a
a
a
K
B:
⋅
−
=
⋅
−
=
−
−
−
−
)
(
)
1
(
)
1
(
)
(
)
(
)
1
(
)
1
(
)
(
n
k
k
ik
k
i
k
i
k
kj
k
ik
k
ij
k
ij
b
a
b
b
a
a
a
a
n
j
n
k
k
i
,
,
1
,
1
,
1
,
,
1
K
K
=
+
−
−
3)
)
1
(
)
1
(
)
(
)
1
(
)
1
(
)
(
:
−
−
−
−
=
=
n
nn
n
n
n
n
n
nn
n
nj
n
nj
a
b
b
a
a
a
A
⋅
−
=
⋅
−
=
−
−
−
)
(
)
1
(
)
1
(
)
(
)
(
)
(
)
1
(
)
(
:
n
n
n
in
n
i
n
i
n
nj
n
in
n
ij
n
ij
b
a
b
b
a
a
a
a
B
n
j
n
i
,
,
1
1
,
,
1
K
K
=
−
=
po k-krokach:
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
k-kroków w formie “0-1”
po n-krokach :
)
(n
i
i
b
x
=
Częściowy wybór elementu podstawowego przeprowadzamy w metodzie Gaussa tj. w k-tym
kroku porównujemy elementy w k-tej kolumnie , ale w wierszach k+1,...,n