Tomasz Kowalski
Wykłady z matematyki dla studentów kierunków ekonomicznych
Wykład 5
METODA GAUSSA - JORDANA
1.
Ogólne układy równań liniowych.
Niech dany będzie układ równań liniowych:
.
...
..
..........
..........
..........
..........
,
...
,
...
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
m
n
mn
m
m
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
Dwa
układy równań nazywamy równoważnymi, jeżeli każde rozwiązanie jednego z nich jest
rozwiązaniem drugiego i na odwrót.
Następujące tzw. operacje elementarne przekształcają dany układ w równoważny układ równań:
1. Pomnożenie obu stron dowolnego równania przez liczbę różną od zera.
2. Zamiana miejscami dwóch dowolnych równań układu.
3. Pomnożenie wybranego równania przez dowolną liczbę i dodanie stronami do innego równania.
4. Zmiana numeracji (kolejności występowania) niewiadomych.
11
12
1
1
21
22
2
2
*
1
2
n
n
m
m
mn
n
a
a
a
b
a
a
a
b
A
a
a
a
b
Uwaga.
Powyższe operacje wykonywane na równaniach danego
układu można zastąpić odpowiednimi operacjami
wykonywanymi na współczynnikach zapisanych w postaci tzw.
macierzy rozszerzonej
oznaczanej przez
(przedstawionej
obok) - macierzy powstałej z macierzy układu A przez dodanie
kolumny wyrazów wolnych.
A
*
Twierdzenie.
Wykonując na macierzy rozszerzonej
skończoną ilość operacji typu:
A
*
1. pomnożenie wybranego wiersza przez liczbę różną od zera,
2. zamiana miejscami dwóch wierszy,
3. dodanie do innego wiersza wybranego wiersza pomnożonego przez dowolną liczbę,
4. przestawienie kolumn (z wyjątkiem kolumny wyrazów wolnych)
macierz można doprowadzić do postaci:
możliwie największa
macierz jednostkowa
0
0
0
0
0
0
0
0
0
0
1
0
0
1
/
/
1
/
/
2
/
1
/
/
1
,
/
2
/
1
,
2
/
1
/
1
,
1
0
0
1
0
0
m
r
r
rn
r
r
n
r
r
n
r
b
b
b
b
b
a
a
a
a
a
a
macierz zerowa
zwanej postacią kanoniczną lub bazową.
Wykład 5. Metoda Gaussa-Jordana
2
2. Metoda Gaussa - Jordana
Jedną z metod sprowadzenia macierzy do postaci kanonicznej jest metoda Gaussa-Jordana.
Realizowana jest ona w następujący sposób:
Krok 1.
Przekształcamy pierwszą kolumnę macierzy do postaci
.
0
0
1
W tym celu
- na miejsce pierwszego wiersza przestawiamy (ewentualnie) taki wiersz, aby element
był różny
od zera,
11
a
- pierwszy wiersz pomnożony przez liczbę
11
1
a
zapisujemy jako pierwszy wiersz nowej macierzy,
- do pozostałych wierszy dodajemy kolejno pierwszy wiersz pomnożony przez odpowiednie liczby
( pamiętając o celu tych przekształceń ).
Krok k.
Przekształcamy k-tą kolumnę macierzy do postaci
( jedynka w k-tym wierszu ).
0
1
0
Operacje, które należy wykonać:
- jeżeli
, to na miejsce k-tego wiersza przestawiamy jeden z następnych wierszy albo na
miejsce k-tej kolumny przestawiamy jedną z następnych kolumn tak, aby po tej ewentualnej
operacji element
a
był różny od zera. (Jeżeli operacja ta jest niewykonalna, to macierz jest już
sprowadzona do postaci kanonicznej),
0
kk
a
kk
- mnożymy k-ty wiersz przez liczbę
kk
a
1
i zapisujemy jako wiersz k-ty nowej macierzy,
- do pozostałych wierszy kolejno dodajemy k-ty wiersz pomnożony przez odpowiednie liczby.
Metodę realizujemy dopóki
m
k
n
k
i
oraz operacje składające się na krok k są wykonalne.
Z
powyższego twierdzenia wynika, że układ równań liniowych
.
...
..
..........
..........
..........
..........
,
...
,
...
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
m
n
mn
m
m
n
n
n
n
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
można za pomocą operacji elementarnych sprowadzić do układu
,
0
..
..........
,
0
,
...
..........
..........
..........
..........
..........
,
...
...
,
...
...
/
/
1
/
/
1
/
1
,
/
2
/
2
1
/
1
,
2
2
/
1
/
1
1
/
1
,
1
1
n
r
r
n
rn
r
r
r
r
n
n
r
r
n
n
r
r
b
b
b
x
a
x
a
x
b
x
a
x
a
x
b
x
a
x
a
x
(kreski nad niewiadomymi oznaczają możliwość zmiany numeracji).
Wykład 5. Metoda Gaussa-Jordana
3
Otrzymany
układ jest równoważny wyjściowemu. Postać tego układu pozwala na przeprowadzenie
dyskusji rozwiązalności, a w przypadku istnienia rozwiązań umożliwia wyznaczenie ich w prosty
sposób.
Przy sprowadzaniu macierzy rozszerzonej układu do postaci kanonicznej możliwe są dwa
przypadki:
1. Po wykonaniu pewnej liczby operacji na macierzy
w jednym z wierszy wszystkie elementy,
z wyjątkiem ostatniego ( wyrazu wolnego ) są równe zeru. Macierz jest wówczas macierzą układu
sprzecznego, gdyż jedno z równań układu ma postać:
A
*
0
,
0
...
0
0
2
1
b
b
x
x
x
n
.
2. Macierz daje się sprowadzić do postaci kanonicznej, przy czym
0
...
/
/
2
/
1
n
r
r
b
b
b
,
tzn w ostatnich
m r
wierszach macierzy występują wyłącznie zera.
a) Gdy
n
r
, to postacią kanoniczną macierzy
A
*
jest
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
/
/
2
/
1
r
b
b
b
Macierzy tej odpowiada układ równań ( po pominięciu równań tożsamościowych ):
/
/
2
2
/
1
1
.........
,
,
n
n
b
x
b
x
b
x
Rozwiązaniem układu jest dokładnie jedna n-ka liczb
/
/
2
2
/
1
1
,
...
,
,
n
n
b
x
b
x
b
x
.
b) Gdy
n
r
, to postacią kanoniczną macierzy
jest:
A
*
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
1
/
/
2
/
1
/
/
1
,
/
2
/
1
,
2
/
1
/
1
,
1
r
rn
r
r
n
r
n
r
b
b
b
a
a
a
a
a
a
I
r
O
m-r
Oznacza to, że wyjściowy układ równań jest równoważny ( po pominięciu równań tożsamościowych )
układowi:
/
/
1
/
1
,
/
1
/
1
1
/
1
,
1
1
...
..........
..........
..........
..........
,
...
r
n
rn
r
r
r
r
n
n
r
r
b
x
a
x
a
x
b
x
a
x
a
x
Wykład 5. Metoda Gaussa-Jordana
4
Jest to układ, w którym liczba niewiadomych jest o
n r
większa niż liczba równań.
Oczywistą rzeczą jest więc założyć, że
n r
zmiennych przyjmuje dowolne wartości ( zmienne te
nazwiemy zmiennymi swobodnymi lub niebazowymi ), a pozostałe r zmiennych przyjmuje wartości ,
które dają się wyznaczyć w oparciu o r równań (zmienne te nazwiemy zmiennymi zależnymi lub
bazowymi
).
W metodzie Gaussa zmiennymi swobodnymi są końcowe n r
zmienne, za które przyjmujemy
dowolne parametry. Przenosząc na drugą stronę równań układu wyrażenia zawierające zmienne
swobodne wyznaczamy zmienne bazowe.
Rozwiązanie (ogólne) układu przyjmie wtedy postać:
.
...
..........
,
,
...
..........
..........
..........
..........
,
...
1
1
/
1
/
1
,
/
/
1
1
/
1
,
1
/
1
1
r
n
n
r
r
n
rn
r
r
r
r
r
n
n
r
x
x
a
a
b
x
a
a
b
x
gdzie
r
n
...,
,
,
2
1
oznaczają dowolne liczby rzeczywiste.
Jeżeli za
r
n
...,
,
,
2
1
przyjąć określone liczby, to otrzymamy tzw. rozwiązanie szczególne.
W przypadku, gdy przyjmiemy liczby wszystkie równe zeru, to otrzymamy tzw. rozwiązanie bazowe.
Wszystkie przypadki zademonstrujemy na przykładach.
Przykład 1.
Rozwiązać układ równań:
1
2
3
1
2
3
1
2
3
2
1,
2
5
0
7
4
13
5
x
x
x
x
x
x
x
x
x
,
.
Rozwiązanie. Macierzą rozszerzoną tego układu jest macierz:
*
1 1
2
1
2 1
5
0
7 4
13
5
A
Pierwszy wiersz - „roboczy”
Wiersz „roboczy” poddamy operacjom, po których pierwsza kolumna nowej macierzy zostanie
przekształcona w pierwszą kolumnę macierzy jednostkowej. W tym celu wystarczy:
- pozostawić pierszy wiersz bez zmian (bo jedynka jest „na swoim miejscu”),
- pomnożyć pierwszy wiersz najpierw przez ( )
2
, a potem przez ( )
7
i dodać kolejno do drugiego
i trzeciego wiersza (w efekcie, pozostałe elementy pierwszej kolumny zostaną „wyzerowane”).
Otrzymamy
macierz:
1
1
2
1
0
1
9
2
0
3
27
2
Drugi wiersz - „roboczy”
Teraz drugi wiersz
- dodamy do pierwszego wiersza,
- pomnożymy przez
i wpiszemy jako wiersz drugi,
( 1)
- pomnożymy przez ( 3)
i dodamy do wiersza trzeciego.
W wyniku tych operacji otrzymamy macierz, w której druga kolumna jest kolumną macierzy
jednostkowej:
Wykład 5. Metoda Gaussa-Jordana
5
1
1 0
7
0 1
9
2
0 0
0
4
4
To jest największa podmacierz jednostkowa
wygenerowana w macierzy A
Otrzymana macierz to postać bazowa (kanoniczna) macierzy A. Jest to macierz układu
sprzecznego, bowiem trzecie równanie tego układu ma postać:
Macierz zerowa
1
2
3
0
0
0
x
x
x
.
Uwaga.
Badany układ równań jest układem sprzecznym, jeżeli na pewnym etapie przekształcania
jego macierzy ma miejsce jeden z przypadków:
1. Jeden z wierszy macierzy A został przekształcony w wiersz zerowy, ale wyraz wolny w tym
wierszu nie jest zerem (jak w przykładzie wyżej ).
2. W macierzy A dwa wiersze są proporcjonalne; proporcjonalność nie przenosi się jednak na
wyrazy wolne w tych wierszach ( po wykonaniu następnej serii operacji wiersz ten przyjąłby
postać opisaną wyżej ).
Przykład 2.
Rozwiązać układ równań:
3
0
2
3
2
1,
2
4
x y
z
x y z
x y
z
x
y z
,
,
Rozwiązanie. Macierzą rozszerzoną tego układu jest
*
2 1
1 3
1 1
2 1
1 2
1 4
A
1 1
3 0
.
Oznaczając przez W
kolejne wiersze tej macierzy, a w następnych przypadkach
wiersze ostatnio otrzymanej macierzy, operacje wykonywane na macierzach można zapisać w postaci:
4
3
2
1
,
,
,
W
W
W
1
1
3
1
4
1
1
0
0
1
5
3
0
0
1
1
0
1
2
4
W
W
W
W
W
1
2
2W
W
3
na miejsce pierwszego wiersza wpisano wiersz
pierwszy
pierwszy wiersz pomnożony przez –2 dodano do wiersza
drugiego
pierwszy wiersz pomnożony przez –1 dodano najpierw
do wiersza trzeciego, a następnie czwartego
2
1
2
4
1 0
2
3
0 1
5
3
1
1
0 0
7
7
W
W
W
W
W
2
3
0 0
W
,
3
1
3
2
3
3
4
2
1
5
2
1
7
0
W
W
W
W
W
W
W
1 0 0
0 1 0
0 0 1
0 0 0
.
Wyjściowy układ równań jest zatem równoważny układowi:
1
,
2
,
1
z
y
x
Przykład 3.
Rozwiązać układ równań:
1
2
3
4
1
2
3
4
1
2
3
4
2
2
2
3
2
0
4
7
4
4
x
x
x
x
x
x
x
x
x
x
x
x
,
,
.
Wykład 5. Metoda Gaussa-Jordana
6
Rozwiązanie. Macierzą rozszerzoną tego układu jest
*
1
2 1
1
2
2
3 2
1 0
4
7 4
1
4
A
.
Postępując podobnie jak w powyższym przykładzie otrzymujemy kolejno:
1
1
2
1
3
1
2 1
1
2
2
0
1
0
3
4
0
1
0
3
W
W
W
W
W
4
4
10
,
2
1
2
2
3
2
1 0 1
7
0 1 0
3
4
0 0 0
0
0
W
W
W
W
W
Wyjściowy układ jest (po pominięciu równania tożsamościowego) równoważny układowi
1
3
4
2
4
.
7
10
3
4
x
x
x
x
x
,
Przyjmując jako zmienne bazowe:
oraz zmienne swobodne:
x x
1
2
,
4
3
, x
x
otrzymujemy
rozwiązanie ogólne układu:
1
2
3
4
10
7 ,
4 3 ,
,
,
x
x
R
x
x
.
Uwaga.
Przyjmując w powyższym rozwiązaniu 0,
0
1,
otrzymamy rozwiązanie
bazowe:
Przyjmując
1
2
3
4
10,
4,
0,
0.
x
x
x
x
2
3,
1
otrzymamy rozwiązanie
szczególne:
, gdy
1
2
3
23,
10,
1,
x
x
x
4
2
x
otrzymamy kolejne rozwiązanie
szczególne:
, itd.
1
2
3
4
0,
1,
3,
1
x
x
x
x
Przykład 4.
Rozwiązać układ równań:
1
2
3
4
1
2
3
4
1
2
3
4
2
2
2
5
2
0,
3
3
3
4
x
x
x
x
x
x
x
x
x
x
x
x
,
.
Rozwiązanie. Macierzą rozszerzoną tego układu jest
*
1 2
1 1
2
2 5
2
1
0
1 3
3
3
4
A
.
Postępując podobnie jak w powyższym przykładzie otrzymujemy kolejno:
1
1
2
1
3
1 2
1
1
2
2
0 1
4
3
0 1
4
4
6
W
W
W
W
W
4
,
2
1
2
2
3
2
1 0
9
7
0 1
4
3
4
0 0
0
1
2
W
W
W
W
W
10
W otrzymanej macierzy
. Tym samym dalsza "rozbudowa" macierzy jednostkowej
w sposób demonstrowany wyżej nie jest możliwa. Jeżeli jednak zamienić kolumnę trzecią z czwartą,
to proces można będzie kontynuować. Przestawienie kolumn związane jest ze zmianą kolejności
występowania niewiadomych w równaniach, które odpowiadają macierzy. Fakt ten ("nienaturalne"
występowanie niewiadomych) odnotowywać będziemy w podobnych przypadkach wypisując nad
kolumnami zmienne, którym odpowiadają te kolumny.
0
33
a
1
2
4
3
1 0
7
9 10
0 1
3
4
4
0 0
1
0
2
x
x
x
x
,
1
2
4
3
2
1
3
2
3
7
1 0 0
9
3
0 1 0
4
0 0 1
0
2
x x x
x
W
W
W W
W
4
2
.
Otrzymana macierz jest macierzą układu:
Wykład 5. Metoda Gaussa-Jordana
7
1
3
2
3
4
,
9
4
4
2
2.
x
x
x
x
x
,
.
Przyjmując jako zmienne bazowe
oraz jako zmienną swobodną
4
2
1
,
,
x
x
x
3
x
otrzymujemy
rozwiązanie ogólne
1
2
4
3
4 9
2 4
2.
x
x
x
,
.
,
,
R
x
.
Przykład 5.
Rozwiązać układ równań:
1
2
3
4
1
2
3
4
1
2
3
4
2
0
2
3
2
0
4
7
4
0
x
x
x
x
x
x
x
x
x
x
x
x
,
,
Rozwiązanie. Układ ten ma nieskończenie wiele rozwiązań, w tym rozwiązanie zerowe, bowiem
łatwo zauważyć, że stosując metodę Gaussa można otrzymać macierz bazową co najwyżej stopnia 3,
a tym samym co najmniej jedna zmienna jest swobodna.
Poniżej przedstawiamy rozwiązanie układu metodą Gaussa.
Macierzą rozszerzoną tego układu jest:
*
1
2 1
1
0
2
3 2
1 0
4
7 4
1
0
A
.
Dokonując odpowiednich przekształceń otrzymujemy kolejno:
1
1
2
1
3
1
2 2
2
0
2
0
1
0
3
4
0
1
0
3
W
W
W
W
W
0
0
2
1
2
2
3
2
1 0 2
4
0 1 0
3 0
0 0 0
0
0
W
W
W
W
W
,
0
Wyjściowy układ jest więc (po pominięciu równania tożsamościowego) równoważny układowi
1
3
4
2
4
2
4
0
3
0
x
x
x
x
x
,
.
Przyjmując za zmienne swobodne:
4
3
, x
x
1
2
3
4
2
4
3 ,
,
.
x
x
(i traktując jako zmienne bazowe
)
otrzymujemy rozwiązanie ogólne układu:
2
1
, x
x
,
,
.
R
x
x
.