Metody Numeryczne, semestr letni 2013/2014
Wykład 13: Warianty metody eliminacji Gaussa
Operacje elementarne na wierszach macierzy:
" Pomnożenie i-tego wiersza macierzy A przez niezerowy skalar ą. Przy tej operacji nie
zmieniamy wierszy o numerach różnych od i, zaś każdy wyraz i-tego wiersza mnożymy
przez Ä…. OperacjÄ™ tÄ™ oznaczamy symbolem Ä… · wi.
" Zamiana miejscami i-tego wiersza macierzy A z wierszem j-tym (i = j) macierzy A. Przy

tej operacji nie zmieniamy wierszy o numerach różnych od i oraz j. Operację tę oznaczamy
symbolem wi "! wj.
" Dodanie do j-tego wiersza macierzy A i-tego (i = j) wiersza tej macierzy pomnożonego

przez dowolny skalar ą. Przy tej operacji nie zmieniamy wierszy o numerach różnych od
j, natomiast wiersz j-ty przybiera postać następującą:
aj1 + Ä… · ai1, aj2 + Ä… · ai2, . . . , ajn + Ä… · ain.
OperacjÄ™ tÄ™ oznaczamy symbolem wj + Ä… · wi.
Definicja 1 Układem m równań liniowych o n niewiadomych x1, x2, . . ., xn o współ-
czynnikach z ciała K nazywamy układ równań postaci:
Å„Å‚
a11x1 + a12x2 + . . . + a1nxn = b1
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
a21x1 + a22x2 + . . . + a2nxn = b2
, (1)
ôÅ‚
. . . . . . . . . . . . . . . . . . . . . . . .
ôÅ‚
ôÅ‚
ół
am1x1 + am2x2 + . . . + amnxn = bm
gdzie współczynniki aij (i = 1, . . . , m; j = 1, . . . , n) oraz elementy bi (i = 1, . . . , m) należą do
ciała K.
Układ ten nazywamy jednorodnym, gdy b1 = b2 = . . . = bm = 0.
Definicja 2 Macierzą współczynników układu (1) nazywamy macierz:
îÅ‚ Å‚Å‚
a11 a12 . . . a1n
ïÅ‚
a21 a22 . . . a2n śł
ïÅ‚ śł
ïÅ‚ śł
A = ,
. . .
ïÅ‚ . śł
. . . .
.
ðÅ‚ . . . ûÅ‚
am1 am2 . . . amn
zaś macierzą uzupełnioną układu (1) nazywamy macierz:
îÅ‚ Å‚Å‚
a11 a12 . . . a1n b1
ïÅ‚
a21 a22 . . . a2n b2 śł
ïÅ‚ śł
ïÅ‚ śł
Au = .
. . . .
ïÅ‚ . śł
. . . . .
.
ðÅ‚ . . . . ûÅ‚
am1 am2 . . . amn bm
Podstawowa postać algorytmu Gaussa
Metoda eliminacji Gaussa jest jedną z metod pozwalających na rozwiązywanie układów m równań
1
liniowych z n niewiadomymi, za pomocą operacji elementarnych. W dalszych rozważaniach
skoncentrujemy się na układach n równań z n niewiadomymi x1, x2, ..., xn postaci:
a11x1 + a12x2 + a13x3 + . . . + a1nxn = b1
a21x1 + a22x2 + a23x3 + . . . + a2nxn = b2
. .
. .
. . (2)
an1x1 + an2x2 + an3x3 + . . . + annxn = bn,
gdzie
aij- współczynniki przy niewiadomych xi, aij " R; i, j = 1, ..., n;
bi- wyrazy wolne, bi " R; i = 1, ..., n.
W postaci podstawowej algorytmu zakładamy, że a(i-1) = 0 dla i = 1, 2, ..., n, co ogranicza

ii
ilość układów możliwych do rozwiązania tą metodą bez żadnych modyfikacji. Jednak ten wa-
runek nie jest zawsze zagwarantowany. W przypadku, gdy a(i-1) = 0 dla pewnego i = 1, 2, ..., n
ii
należy dokonać zamiany wierszy (równań) w kolejnych krokach eliminacji tak, aby a(i-1) = 0.

ii
Możemy również dokonać zamiany kolumn, ale to zmieni porządek niewiadomych.
Opis metody
W poniższych rozważaniach przyjmiemy następującą konwencję zapisu współczynników układu (2):
" a(0) = aij dla i, j = 1, 2, ...n.
ij
" a(k) - współczynniki macierzy A układu (2) w k-tym kroku pierwszego etapu eliminacji
ij
Gaussa, gdzie k = 1, 2, ..., n - 1; i, j = 1, 2, ..., n.
" b(k) - wyrazy wolne układu (2) w k-tym kroku pierwszego etapu eliminacji Gaussa, przy
i
czym k = 1, 2, ..., n - 1; i = 1, 2, ..., n.
Etap pierwszy, zwany etapem eliminacji zmiennych, prowadzi do otrzymania trójkątnego
układu równań. Zakładamy, że wszystkie elementy a(i-1) = 0 (i = 1, ..., n). W pierwszym kroku,

ii
za pomocą pierwszego równania, eliminujemy niewiadomą x1 z pozostałych równań. W tym
ai1
celu pierwsze równanie układu podstawowego, pomnożone przez (i = 2, 3, ..., n) odejmujemy
a11
stronami od pozostałych równań. Otrzymujemy w ten sposób pierwszy układ zredukowany:
a(1)x1 + a(1)x2 + a(1)x3 + . . . + a(1)xn = b(1)
11 12 13 1n 1
a(1)x2 + a(1)x3 + . . . + a(1)xn = b(1)
22 23 2n 2
. .
. .
. . (3)
a(1)x2 + a(1)x3 + . . . + a(1)xn = b(1),
n2 n3 nn n
Nowe współczynniki a(1) są równe:
ij
a(1) = a(0), j = 1, 2, ..., n;
1j 1j
a(0)
i1
a(1) = a(0) - a(0), i, j = 2, 3, ..., n;
ij ij 1j
a(0)
11
a(1) = 0, i > j.
ij
2
W ten sposób wyeliminowaliśmy zmienną x1 ze wszystkich równań poza pierwszym.
W kolejnym kroku za pomocą drugiego równania zostaje wyeliminowana zmienna x2 z po-
a(1)
i2
zostałych n - 2 równań. W tym celu drugie równanie układu (3) pomnożone przez należy
a(1)
22
odjąć stronami od pozostałych i równań dla i = 3, 4, ..., n.
Otrzymujemy drugi układ zredukowany:
a(2)x1 + a(2)x2 + a(2)x3 + . . . + a(2)xn = b(2)
11 12 13 1n 1
a(2)x2 + a(2)x3 + . . . + a(2)xn = b(2)
22 23 2n 2
a(2)x3 + . . . + a(2)xn = b(2)
33 3n 3
.
.
. (4)
a(2)x3 + . . . + a(2)xn = b(2),
n3 nn n
gdzie
a(2) = a(1), j = 1, 2, ..., n;
1j 1j
a(2) = a(1), j = 2, 3, ..., n;
2j 2j
a(1)
i2
a(2) = a(1) - a(1) i, j = 3, 4, ..., n;
ij ij 2j
a(1)
22
a(2) = 0, i > j.
ij
W ten sposób wyeliminowaliśmy zmienną x2 ze wszystkich równań poza drugim.
Kontynuując te obliczenia, w n-1 kroku otrzymujemy ostatecznie układ równań, z macierzą
górną trójkątną
a(n-1)x1 + a(n-1)x2 + a(n-1)x3 + . . . + a(n-1)xn = b(n-1)
11 12 13 1n 1
a(n-1)x2 + a(n-1)x3 + . . . + a(n-1)xn = b(n-1)
22 23 2n 2
a(n-1)x3 + . . . + a(n-1)xn = b(n-1)
33 3n 3
.
.
. (5)
a(n-1)xn = b(n-1),
nn n
gdzie
a(n-1) = a(n-2), j = 1, 2, ..., n;
1j 1j
a(n-1) = a(n-2), j = 2, 3, ..., n;
2j 2j
. .
. .
. .
a(n-1) = a(n-2), j = n - 1, n;
n-1,j n-1,j
a(n-2)
n,n-1
a(n-1) = a(n-2) - a(n-2);
nn nn n-1,n
a(n-2)
n-1,n-1
a(n-1) = 0, i > j.
ij
W etapie drugim, zwanym postępowaniem odwrotnym, kolejne niewiadome wyliczamy ze
wzorów:
b(n-1)
n
xn = (6)
a(n-1)
nn
3
ëÅ‚ öÅ‚
n

1
íÅ‚
xi = b(n-1) - a(n-1)xjłł i = n, ..., 1. (7)
i ij
a(n-1)
j=i+1
ii
Zapis macierzowy
Zamiast prowadzić działania na równaniach możemy dokonać operacji na macierzy uzupeł-
nionej. Podstawowy układ równań (2) możemy zapisać następująco
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
a11 a12 a13 . . . a1n x1 b1
ïÅ‚
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
a21 a22 a23 . . . a2n śł ïÅ‚ x2 śł ïÅ‚ b2 śł
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚
a31 a32 a33 . . . a3n śł ïÅ‚ x3 śł = ïÅ‚ b3 śł
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł (8)
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
. . . . . .
.
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
. . . . . . .
.
. . . . . .
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
an1 an2 an3 . . . ann xn bn
lub w skrócie
Ax = b, (9)
gdzie
A = (aij)i,j=1,...,n - macierz n × n współczynników stojÄ…cych przy xi; i = 1, ..., n.
x - wektor niewiadomych xi; i = 1, 2, ..., n.
b = (bi)i=1,...,n - wektor n wyrazów wolnych.
Opis metody dla układu zapisanego w postaci macierzowej
Będziemy stosowali następujące oznaczenia:
" A(0) := A, b(0) := b;
" A(k) - macierz główna układu w k-tym kroku pierwszego kroku eliminacji Gaussa;
" b(k) - wektor wyrazów wolnych w k-tym kroku pierwszego kroku eliminacji Gaussa.
Na początku zapisujemy macierz uzupełnioną postaci
îÅ‚ Å‚Å‚
a11 a12 a13 . . . a1n b1
ïÅ‚
ïÅ‚ śł
a21 a22 a23 . . . a2n b2 śł
ïÅ‚ śł
ïÅ‚
a31 a32 a33 . . . a3n b3 śł .
(A|b) = ïÅ‚ śł (10)
ïÅ‚ śł
. . . . .
.
ïÅ‚ śł
. . . . . .
.
. . . . .
ðÅ‚ ûÅ‚
an1 an2 an3 . . . ann bn
Macierz (10) będziemy przekształcać w macierz trójkątną górną za pomocą operacji ele-
mentarnych na wierszach macierzy.
W pierwszym kroku zakładamy, że a(i-1) = 0, dla i = 1, 2, ..., n. Potem pierwszy wiersz

ii
ai1
macierzy (10) mnożymy przez , gdzie i = 1, 2, ..., n. Po czym odpowiednią jego wielokrotność
a11
odejmujemy od pozostałych wierszy. W ten sposób otrzymujemy macierz nowych elementów:
îÅ‚ Å‚Å‚
a(1) a(1) a(1) . . . a(1) b(1)
11 12 13 1n 1
ïÅ‚ śł
ïÅ‚ śł
0 a(1) a(1) . . . a(1) b(1)
ïÅ‚ 22 23 2n 2 śł
ïÅ‚ śł
ïÅ‚ śł
0 a(1) a(1) . . . a(1) b(1)
(A(1)|b(1)) = . (11)
32 33 3n 3
ïÅ‚ śł
ïÅ‚ śł
. . . . .
.
ïÅ‚ . . . . . . śł
.
. . . . .
ðÅ‚ ûÅ‚
0 a(1) a(1) . . . a(1) b(1)
n2 n3 nn n
4
W kroku następnym wyeliminujemy do zera elementy w drugiej kolumnie macierzy (11)
znajdujące się poniżej elementu a(1). W tym celu drugi wiersz macierzy (11) mnożymy przez
22
a(1)
i2
i odejmujemy od wierszy i-tych, przy czym i = 3, 4, ..., n. Po tych operacjach otrzymujemy
a(1)
22
macierz:
îÅ‚ Å‚Å‚
a(2) a(2) a(2) . . . a(2) b(2)
11 12 13 1n 1
ïÅ‚ śł
ïÅ‚ śł
0 0 a(2) . . . a(2) b(2)
ïÅ‚ 23 2n 2 śł
ïÅ‚ śł
ïÅ‚ śł
0 0 a(2) . . . a(2) b(2)
(A(2)|b(2)) = . (12)
33 3n 3
ïÅ‚ śł
ïÅ‚ śł
. . . . .
.
ïÅ‚ . . . . . . śł
.
. . . . .
ðÅ‚ ûÅ‚
0 0 a(2) . . . a(2) b(2)
n3 nn n
Kontynuując, w n - 1 kroku, otrzymujemy macierz trójkątną, która odpowiada układowi
równań (5)
îÅ‚ Å‚Å‚
a(n-1) a(n-1) a(n-1) . . . a(n-1) b(n-1)
11 12 13 1n 1
ïÅ‚ śł
ïÅ‚
0 a(n-1) a(n-1) . . . a(n-1) b(n-1) śł
ïÅ‚ śł
22 23 2n 2
ïÅ‚ śł
ïÅ‚ śł
(A(n-1)|b(n-1)) = 0 0 a(n-1) . . . a(n-1) b(n-1) . (13)
ïÅ‚ 33 3n 3 śł
ïÅ‚ śł
. . . . .
.
ïÅ‚ śł
. . . . . .
.
. . . . .
ðÅ‚ ûÅ‚
0 0 0 . . . a(n-1) b(n-1)
nn n
Przykład 1 Metodą eliminacji Gaussa rozwiązać układ równań liniowych nad ciałem R
6x1 - 2x2 + 2x3 + 4x4 = 0
12x1 - 8x2 + 4x3 + 10x4 = -10
3x1 - 13x2 + 3x3 + 3x4 = -39 (14)
-6x1 + 4x2 + 2x3 - 18x4 = -16.
RozwiÄ…zanie:
Etap pierwszy: Dla układu (14) macierz współczynników A i macierz uzupełniona Au są postaci
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
6 -2 2 4 6 -2 2 4 0
ïÅ‚ śł ïÅ‚ śł
12 -8 4 10 12 -8 4 10 -10
ïÅ‚ śł ïÅ‚ śł
A = ïÅ‚ śł ; Au = ïÅ‚ śł ·
ðÅ‚ -13 3 3 3
ûÅ‚ ðÅ‚ -13 3 3 -39
ûÅ‚
3
-6 4 2 -18 -6 4 2 -18 -16
1. W pierwszym kroku sprawdzamy ilość możliwych rozwiązań.
rz(A) = rz(Au) = 4.
Na mocy twierdzenia Kroneckera-Capellego układ posiada dokładnie jedno rozwiązanie.
Następnie za pomocą operacji elementarnych wyeliminujemy poszczególne zmienne z od-
powiednich równań.
2. Zmienna x1 zostanie wyeliminowana ze wszystkich równań poza pierwszym. W tym celu:
" od drugiego wiersza odejmujemy wiersz pierwszy pomnożony przez 2,
1
" od trzeciego wiersza odejmujemy wiersz pierwszy pomnożony przez ,
2
" do czwartego wiersza dodajemy wiersz pierwszy.
5
Otrzymujemy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
6 -2 2 4 0 6 -2 2 4 0
1
w2-2w1;w3- w1;
2
ïÅ‚ śł ïÅ‚ śł
w4+w1
12 -8 4 10 -10 0 -4 0 2 -10
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł a" ïÅ‚ śł .
ðÅ‚ -13 3 3 -39 0
ûÅ‚ ðÅ‚ -12 2 1 -39
ûÅ‚
3
-6 4 2 -18 -16 0 2 4 -14 -16
3. Zmienną x2 należy wyeliminować z trzeciego i czwartego równania. Aby to osiągnąć
" od wiersza trzeciego odejmujemy wiersz drugi pomnożony przez 3.
1
" do wiersza czwartego dodajemy wiersz drugi pomnożony przez .
2
Uzyskujemy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
6 -2 2 4 0 6 -2 2 4 0
1
ïÅ‚ śł ïÅ‚ śł
w3-3w2;w4+ w2
0 -4 0 2 -10 0 -4 0 2 -10
2
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł a" ïÅ‚ śł .
ðÅ‚ -12 2 1 -39 0 0 2 -5 -9
ûÅ‚ ðÅ‚ ûÅ‚
0
0 2 4 -14 -16 0 0 4 -13 -21
4. Aby zmienna x3 została usunięta z czwartego równania musimy
" od wiersza czwartego odjąć wiersz trzeci pomnożony przez 2.
Ostatecznie
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
6 -2 2 4 0 6 -2 2 4 0
ïÅ‚ śł ïÅ‚ śł
0 -4 0 2 -10 w4-2w3 -4 0 2 -10
0
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł a" ïÅ‚ śł . (15)
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
0 0 2 -5 -9 0 0 2 -5 -9
0 0 4 -13 -21 0 0 0 -3 -3
Dzięki tym operacjom otrzymujemy macierz trójkątną górną.
Etap drugi: Z czwartego równania układu (15) wyznaczamy zmienną x4:
-3x4 = -3,
x4 = 1.
Z równania trzeciego wyznaczamy zmienną x3:
2x3 - 5x4 = -9,
1
x3 = (5x4 - 9) = -2.
2
Postępując analogicznie obliczamy kolejno zmienną x2 i x1.
Z równania:
-4x2 + 2x4 = -10,
dostajemy
x2 = -1(-10 - 2x4) = 3.
4
Natomiast na podstawie:
6
6x1 - 2x2 + 2x3 + 4x4 = 0,
otrzymujemy
1
x1 = (2x2 - 2x3 - 4x4) = 1.
6
Redukcja Gaussa-Jordana
Redukcja Gaussa-Jordana jest odmianą eliminacji Gaussa. Różnica polega na tym, że redukcję
k-tej zmiennej przeprowadza się w całej k-tej kolumnie. W wyniku zastosowania algorytmu nie
ma potrzeby przeprowadzania postępowania odwrotnego.
operacje elementarne na wierszach
[A|B] - - - - -- - [In|B]
Opis metody
Na początku należy podzielić stronami pierwsze równanie układu podstawowego przez a(0).
11
Dzięki temu otrzymujemy równanie:
x1 + a(1)x2 + a(1)x3 + . . . + a(1)xn = b(1), (16)
12 13 1n 1
gdzie
a(0)
b(0)
1j 1
a(1) = ; b(1) = , j = 1, 2, ..., n.
1j 1
a(0) a(0)
11 11
Korzystając z równania (16) wyeliminujemy zmienną x1 z wszystkich równań poza pierw-
szym. W tym celu odejmujemy odpowiednią wielokrotność równania (16) od pozostałych n - 1
równań. Otrzymujemy układ postaci:
x1 + a(1)x2 + a(1)x3 + . . . + a(1)xn = b(1)
12 13 1n 1
a(1)x2 + a(1)x3 + . . . + a(1)xn = b(1)
22 23 2n 2
. .
. .
. . (17)
a(1)x2 + a(1)x3 + . . . + a(1)xn = b(1),
n2 n3 nn n
gdzie
a(1) = 0, i > j;
ij
a(1) = a(0) - a(0)a(1), i = 2, 3, ..., n; j = 1, 2, ..., n;
ij ij i1 1j
b(1) = b(0) - b(1)a(0), i = 2, 3, ..., n.
i i 1 i1
Następnie drugie równanie układu (17) dzielimy stronami przez a(1). Uzyskujemy równanie
22
postaci:
x2 + a(2)x3 + a(2)x4 + . . . + a(2)xn = b(2), (18)
23 24 2n 2
gdzie
a(1)
b(1)
2j 2
a(2) = ; b(2) = , j = 2, 3, ..., n.
2j 2
a(1) a(1)
22 22
7
Korzystając z równania (18) usuwamy zmienną x2 z wszystkich równań poza drugim. Dzięki
temu dostajemy układ:
x1 + +a(2)x3 + . . . + a(2)xn = b(2)
13 1n 1
x2 + a(2)x3 + . . . + a(2)xn = b(2)
23 2n 2
. .
. .
. . (19)
a(2)x3 + . . . + a(2)xn = b(2),
n3 nn n
przy czym
a(2) = 0, i > j;
ij
a(2) = a(1) - a(1)a(2), i = 1, 3, ..., n; j = 2, 3, ..., n;
ij ij i2 2j
b(2) = b(1) - b(2)a(1), i = 1, 3, ..., n.
i i 2 i2
Kontynuując te obliczenia wyeliminujemy zmienną xk ze wszystkich równań poza k-tym. W
tym celu k-te równanie dzielimy obustronnie przez a(k-1).
kk
Uzyskujemy równanie:
xk + a(k) xk+1 + . . . + a(k)xn = b(k), (20)
kk+1 kn k
w którym
a(k-1)
b(k-1)
kj
k
a(k) = ; b(k) = , j = k, ..., n.
kj k
a(k-1) a(k-1)
kk kk
Za pomocą równania (20) wyeliminujemy zmienną xk. Dzięki przeprowadzonym redukcjom
dostajemy układ postaci:
x1 + +a(k) xk+1 + . . . + a(k) xn-1 + a(k)xn = b(k)
1,k+1 1n-1 1n 1
x2 + +a(k) xk+1 + . . . + a(k) xn-1 + a(k)xn = b(k)
2,k+1 2n-1 2n 2
x3 + +a(k) xk+1 + . . . + a(k) xn-1 + a(k)xn = b(k)
3,k+1 3n-1 3n 3
. .
. .
. .
xk + a(k) xk+1 + . . . + a(k) xn-1 + a(k)xn = b(k) (21)
k,k+1 kn-1 kn k
. .
. .
. .
a(k) xk+1 + . . . + a(k) xn-1 + a(k)xn = b(k),
n,k+1 nn-1 nn n
przy czym
a(k) = 0, i > j;
ij
a(k) = a(k-1) - a(k-1)a(k), i = 1, ..., k - 1, k + 1, ..., n; j = k, ..., n;
ij ij ik kj
b(k) = b(k-1) - b(k)a(k-1), i = 1, ..., k - 1, k + 1, ..., n.
i i k ik
8
Po wykonaniu n - 1 eliminacji otrzymujemy ostatecznie układ równań:
x1 = b(n)
1
x2 = b(n)
2
x3 = b(n)
3
.
.
.
xk = b(n)
k
.
.
.
xn = b(n), (22)
n
z którego odczytujemy rozwiązania.
Zamiast prowadzić działania na równaniach możemy postąpić analogicznie jak w podstawo-
wej eliminacji Gaussa, przeprowadzając operacje na wierszach macierzy uzupełnionej.
Przykład 2 Metodą eliminacji Gaussa-Jordana rozwiązać układ równań liniowych (14) nad
ciałem R.
RozwiÄ…zanie:
Przypomnijmy, że macierze A i Au układu (14) są postaci
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
6 -2 2 4 6 -2 2 4 0
ïÅ‚ śł ïÅ‚ śł
12 -8 4 10 12 -8 4 10 -10
ïÅ‚ śł ïÅ‚ śł
A = ïÅ‚ śł ; Au = ïÅ‚ śł .
ðÅ‚ -13 3 3 3
ûÅ‚ ðÅ‚ -13 3 3 -39
ûÅ‚
3
-6 4 2 -18 -6 4 2 -18 -16
1. Na mocy twierdzenia Kroneckera-Capellego układ (14) ma dokładnie jedno rozwiązanie,
ponieważ
rz(A) = rz(Au) = 4.
2. Za pomocÄ… operacji elementarnych sprowadzimy macierz rozszerzonÄ… Au do macierzy
jednostkowej. Zatem pierwszy wiersz macierzy Au dzielimy stronami przez a(0) = 6. Dzięki
11
temu otrzymujemy macierz postaci:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
6 -2 2 4 0 1 -1 1 2 0
3 3 3
1
ïÅ‚ śł ïÅ‚ śł
w1
12 -8 4 10 -10 12 -8 4 10 -10
6
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł a" ïÅ‚ śł . (23)
ðÅ‚ -13 3 3 -39 3
ûÅ‚ ðÅ‚ -13 3 3 -39
ûÅ‚
3
-6 4 2 -18 -16 -6 4 2 -18 -16
Następnie za pomocą pierwszego wiersza macierzy (23) eliminujemy zmienną x1 ze wszyst-
kich równań poza pierwszym. Uzyskujemy:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 -1 1 2 0 1 -1 1 2 0
3 3 3 3 3 3
w2-12w1;w3-3w1;
ïÅ‚ śł ïÅ‚ śł
w4+6w1
12 -8 4 10 -10 0 -4 0 2 -10
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł a" ïÅ‚ śł . (24)
ðÅ‚ -13 3 3 -39 0
ûÅ‚ ðÅ‚ -12 2 1 -39
ûÅ‚
3
-6 4 2 -18 -16 0 2 4 -14 -16
3. W kolejnym kroku drugi wiersz macierzy (24) dzielimy stronami przez a(1) = -4. Dosta-
22
jemy:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 -1 1 2 0 1 -1 1 2 0
3 3 3 3 3 3
1
ïÅ‚ śł ïÅ‚
- w2
0 -4 0 2 -10 0 1 0 -1 5 śł
4
ïÅ‚ śł ïÅ‚ śł
2 2
ïÅ‚ śł a" ïÅ‚ śł . (25)
ðÅ‚ -12 2 1 -39 0
ûÅ‚ ðÅ‚ -12 2 1 -39
ûÅ‚
0
0 2 4 -14 -16 0 2 4 -14 -16
9
Za pomocą drugiego wiersza macierzy (25) eliminujemy zmienną x2 ze wszystkich równań
poza drugim.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 1 5
1 -1 1 2 0 1 0
1
3 3 3 3 2 6
w1+ w2;w3+12w2;
3
ïÅ‚ ïÅ‚
w4-2w2
0 1 0 -1 5 śł 0 1 0 -1 5 śł
ïÅ‚ śł ïÅ‚ śł
2 2 2 2
ïÅ‚ śł a" ïÅ‚ śł . (26)
ðÅ‚ -12 2 1 -39 0 0 2 -5 -9
ûÅ‚ ðÅ‚ ûÅ‚
0
0 2 4 -14 -16 0 0 4 -13 -21
4. Postępując analogicznie, wiersz trzeci macierzy (26) dzielimy stronami przez a(2) = 2.
33
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 1 5
1 0 1 0 2 3 5
3 2 6
1
ïÅ‚
0 1 0 -1 5 śł w3 ïÅ‚ 0 1 0 -1 5 śł
2
ïÅ‚ śł ïÅ‚ śł
2 2 2 2
ïÅ‚ śł a" ïÅ‚ śł . (27)
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
0 0 2 -5 -9 0 0 1 -5 -9
2 2
0 0 4 -13 -21 0 0 4 -13 -21
Za pomocą trzeciego wiersza macierzy (27) usuwamy zmienną x3 ze wszystkich równań
poza trzecim. Otrzymujemy:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 1 5 4 7
1 0 1 0 0
3 2 6 3 3
1
ïÅ‚ ïÅ‚
w3;w4-4w3
0 1 0 -1 5 śł w1- 3
0 1 0 -1 5 śł
ïÅ‚ śł ïÅ‚ śł
2 2 2 2
ïÅ‚ śł a" ïÅ‚ śł . (28)
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
0 0 1 -5 -9 0 0 1 -5 -9
2 2 2 2
0 0 4 -13 -21 0 0 0 -3 -3
5. W następnej kolejności czwarty wiersz macierzy (28) dzielimy stronami przez a(3) = -3.
44
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
4 7 4 7
1 0 0 1 0 0
3 3 3 3
1
ïÅ‚ ïÅ‚
w4
0 1 0 -1 5 śł - 3
0 1 0 -1 5 śł
ïÅ‚ śł ïÅ‚ śł
2 2 2 2
ïÅ‚ śł a" ïÅ‚ śł (29)
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
0 0 1 -5 -9 0 0 1 -5 -9
2 2 2 2
0 0 0 -3 -3 0 0 0 1 1
Póz
niej wykorzystujÄ…c wiersz czwarty macierzy (29) eliminujemy zmiennÄ… x4 ze wszyst-
kich równań poza czwartym. Dostajemy macierz:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
4 7
1 0 0 4 1 1 0 0 0 1
w1- w4;w2+ w4;
3 3
3 2
ïÅ‚ 5 ïÅ‚ śł
w3+ w4
0 1 0 -1 5 śł 0 1 0 0 3
2
ïÅ‚ śł ïÅ‚ śł
2 2
ïÅ‚ śł a" ïÅ‚ śł . (30)
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
0 0 1 -5 -9 0 0 1 0 -2
2 2
0 0 0 1 1 0 0 0 1 1
6. Z macierzy (30) odczytujemy poszczególne wartości zmiennych
x4 = 1 x3 = -2 x2 = 3 x1 = 1.
10
Wybór elementu głównego
Algorytm Gaussa wymaga, aby w trakcie przekształcania układu równań do układu z macie-
rzą trójkątną górną wszystkie współczynniki a(k-1) dla k = 1, 2, ..., n były niezerowe. Również
kk
przypadek, gdy moduł współczynnika a(k-1) ma bardzo małą wartość, może prowadzić do po-
kk
wstania znacznych błędów zaokrągleń spowodowanych operacją dzielenia przez bardzo małą
liczbę. Aby tego uniknąć, stosuje się różne strategie wyboru elementów głównych, zwanych też
elementami podstawowymi. Wiersz zawierający element główny nazywamy wierszem głównym.
Uwaga 1 Przy wyborze elementów głównych pomijamy kolumnę wyrazów wolnych, niezależnie
od tego, czy jest to wybór częściowy, czy pełny.
Wybór częściowy
A) Wybór w kolumnie
1. Poprzez częściowy wybór elementu głównego w kolumnie, w k-tym kroku rozumiemy zna-
lezienie elementu a(k-1) takiego, że
rk
|a(k-1)| = max {|a(k-1)|},
rk ik
i=k,...,n

gdzie A(0) = a(0) := A.
ij
i,j=1,...,n
2. Następnie w macierzy A(k-1) zamieniamy wiersz r-ty z wierszem k-tym.
3. Kontynuując eliminujemy niewiadomą xk z równań o numerze k + 1, ..., n zgodnie z algo-
rytmem eliminacji Gaussa.
Przykład 3 Stosując metodę eliminacji Gaussa z wyborem elementu głównego w kolumnie
rozwiązać układ równań nad ciałem R
-2x2 + x3 = 5
2x1 + x2 + 3x3 = 8 (31)
-x1 - 3x2 = -2.
RozwiÄ…zanie:
Dla układu (31) macierz A i Au są postaci
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
0 -2 1 0 -2 1 5
ïÅ‚ śł ïÅ‚ śł
A = 2 1 3 ; Au = 2 1 3 8 .
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
-1 -3 0 -1 -3 0 -2
1. Na początku sprawdzamy ilość możliwych rozwiązań układu (31)
rz(A) = rz(Au) = 3.
Na mocy twierdzenia Kroneckera-Capellego układ ma dokładnie jedno rozwiązanie.
2. W pierwszym kroku, w pierwszej kolumnie macierzy Au szukamy największego co do
modułu elementu a(0). Maksymalnym elementem jest |a(0)| = 2, w związku z tym, wiersz
i1 21
11
drugi jest wierszem głównym. Następnie wiersz pierwszy zamieniamy z wierszem drugim,
otrzymujÄ…c tym samym macierz:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
0 -2 1 5 2 1 3 8
w1"!w2
ïÅ‚ śł ïÅ‚ śł
ðÅ‚ 2 1 3 8 a" 0 -2 1 5 .
ûÅ‚ ðÅ‚ ûÅ‚
-1 -3 0 -2 -1 -3 0 -2
Zgodnie z krokami podstawowej eliminacji Gaussa eliminujemy zmiennÄ… x1 z drugiego i
trzeciego równania. Uzyskujemy:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 1 3 8 2 1 3 8
1
w3+ w1
2
ïÅ‚ śł ïÅ‚ śł
0 ûÅ‚ ðÅ‚ ûÅ‚
ðÅ‚ -2 1 5 a" 0 -2 1 5 . (32)
-1 -3 0 -2 0 -5 3 2
2 2
3. KontynuujÄ…c, w drugiej kolumnie macierzy (32) szukamy elementu maksymalnego. Ele-
5
mentem największym co do modułu jest |a(1)| = , a następnie wiersz trzeci zamieniamy
32
2
z wierszem drugim, otrzymujÄ…c:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 1 3 8 2 1 3 8
w2"!w3
ïÅ‚ śł ïÅ‚ śł
0 ûÅ‚ ðÅ‚ ûÅ‚
ðÅ‚ -2 1 5 a" 0 -5 3 2 .
2 2
0 -5 3 2 0 -2 1 5
2 2
Następnie eliminujemy zmienną x2 z trzeciego równania za pomocą operacji elementar-
nych
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 1 3 8 2 1 3 8 2 1 3 8
4
w3- w2
-5w3
5
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
0
ðÅ‚ -5 3 2 a" 0 -5 3 2 a" 0 -5 3 2 . (33)
ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
2 2 2 2 2 2
0 -2 1 5 0 0 -1 17 0 0 1 -17
5 5
Z ostatniej macierzy (33) możemy odczytać, że

2 3 1
x3 = -17, x2 = - - x3 + 2 = -11, x1 = (-x2 - 3x3 + 8) = 35.
5 2 2
Wybór w wierszu
1. Poprzez częściowy wybór elementu głównego w wierszu, w k-tym kroku rozumiemy znale-
zienie elementu a(k-1) takiego, że
ks
|a(k-1)| = max {|a(k-1)|},
ks kj
j=k,...n

gdzie A(0) = a(0) := A.
ij
i,j=1,...,n
2. Następnie w macierzy A(k-1) zamieniamy miejscami s-tą kolumnę z kolumną k-tą.
3. Postępujemy analogicznie jak w przypadku wyboru elementu głównego w kolumnie.
W przypadku wyboru w wierszu należy zapamiętać wszystkie kolejne zmiany kolumn,
ponieważ powodują one zmianę kolejności niewiadomych.
Przykład 4 Stosując metodę eliminacji Gaussa z wyborem elementu głównego w wierszu roz-
wiązać układ (31) nad ciałem R.
W przypadku wyboru elementu głównego w wierszu, postępujemy analogicznie jak w przy-
padku wyboru w kolumnie, z tą różnicą, że elementów głównych szukamy w wierszach.
RozwiÄ…zanie:
12
1. Elementem maksymalnym co do modułu, w pierwszym wierszu macierzy Au jest |a(0)| = 2.
12
Następnie kolumnę drugą macierzy Au zamieniamy z kolumną pierwszą. Tym samym
zamieniamy zmiennÄ… x2 ze zmiennÄ… x1. Otrzymujemy:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x2 x1 x3
x1 x2 x3
0 -2 5 -2 5
1 0 1
ïÅ‚ śł ïÅ‚ śł
k2"!k1
ïÅ‚ śł ïÅ‚ śł
a" .
2 1 3 8 1 2 3 8
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
-1 -3 0 -2 -3 -1 0 -2
Za pomocą operacji elementarnych eliminujemy zmienną x2 z drugiego i trzeciego równa-
nia.
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x2 x1 x3 x2 x1 x3
1 3 -2
-2 5 5
0 1 0 1
w2+ w1;w3- w1
ïÅ‚ śł ïÅ‚ śł
2 2
ïÅ‚ śł ïÅ‚ 7 21 śł
a" . (34)
1 2 3 8 0 2
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
2 2
-3 -1 0 -2 0 -1 -3 -19
2 2
2. Następnie w wierszu drugim macierzy (34) szukamy elementu największego co do modułu.
7
Jest nim |a(1)| = . Zatem trzeciÄ… kolumnÄ™ zamieniamy z kolumnÄ… drugÄ…, tym samym
23
2
zamieniamy zmiennÄ… x3 z x1. Uzyskujemy:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x2 x1 x3 x2 x3 x1
-2 5 -2 5
0 1 1 0
ïÅ‚ śł ïÅ‚ śł
k3"!k2
ïÅ‚ 7 21 śł ïÅ‚ 7 21 śł
a" .
0 2 0 2
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
2 2 2 2
0 -1 -3 -19 0 -3 -1 -19
2 2 2 2
Eliminujemy zmiennÄ… x3 z wiersza trzeciego, za pomocÄ… wiersza drugiego
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x2 x3 x1 x2 x3 x1 x2 x3 x1
3 -2
-2 5 5 -2 5
1 0 1 0 1 0
w3+ w2
ïÅ‚ śł ïÅ‚ śł -7w3
ïÅ‚ śł
7
ïÅ‚ 7 21 śł ïÅ‚ 7 21 śł ïÅ‚ 7 21 śł
a" a" . (35)
0 2 0 2 0 2
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
2 2 2 2 2 2
0 -3 -1 -19 0 0 -1 -10 0 0 1 35
2 2 7 2
Z macierzy (35) odczytujemy
x1 = 35

2 21
x3 = -2x1 + = -17
7 2
1
x2 = - (-x3 + 5) = -11.
2
Wybór częściowy jest istotny ze względu na rozwiązywanie układów z macierzami rzadkimi.
Aby móc zastosować eliminację Gaussa dla macierzy rzadkich, w których większa część elemen-
tów jest zerowa, należy użyć częściowego wyboru elementów głównych.
Wybór pełny
W tym przypadku w pełni wykorzystujemy możliwość wyboru elementów głównych.
1. Poprzez wybór pełny elementu głównego w k-tym kroku rozumiemy znalezienie elementu
a(k-1) spełniającego warunek
rs
|a(k-1)| = max {|a(k-1)|},
rs ij
i,j=k,...,n
gdzie A(0) := A.
13
2. Następnie w macierzy A(k-1) zamieniamy r-ty wiersz z wierszem k-tym, a kolumnę s-tą
z kolumnÄ… k-tÄ….
3. Dalej postępujemy analogicznie jak w przypadku wyboru częściowego.
Przykład 5 Stosując metodę eliminacji Gaussa z wyborem pełnym elementu głównego, roz-
wiązać układ równań (31) nad ciałem R.
W przypadku wyboru pełnego, elementu głównego szukamy zarówno wśród wierszy, jak i ko-
lumn macierzy rozszerzonej.
RozwiÄ…zanie:
1. W pierwszym kroku mamy do wyboru dwa elementy główne |a(0)| = 3 lub |a(0)| = 3.
32 23
Pozwala to na dowolność w wyborze elementu podstawowego. Wybieramy element |a(0)|.
32
Następnie wiersz trzeci macierzy Au zamieniamy z wierszem pierwszym, a kolumnę drugą
z kolumnÄ… pierwszÄ…. Tym samym zamieniamy zmiennÄ… x2 z x1.
Uzyskujemy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x2 x1 x3
x1 x2 x3
0 -2 5 -3 -1 -2
1 0
ïÅ‚ śł ïÅ‚ śł
w1"!w3;k1"!k2
ïÅ‚ śł ïÅ‚ śł
a" .
2 1 3 8 1 2 3 8
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
-1 -3 0 -2 -2 0 1 5
Za pomocą wiersza głównego eliminujemy zmienną x2 z drugiego i trzeciego wiersza.
Mamy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x2 x1 x3 x2 x1 x3
1 2 -3 -1 -2
-3 -1 -2
0 0
w2+ w1;w3- w1
ïÅ‚ śł ïÅ‚ śł
3 3
ïÅ‚ śł ïÅ‚ 5 22 śł
a" . (36)
1 2 3 8 0 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
3 3
2 19
-2 0 1 5 0 1
3 3
2. W macierzy (36) elementem głównym jest |a(1)| = 3. W związku z tym, że element
23
podstawowy znajduje siÄ™ w drugim wierszu, to miejscami zamieniamy jedynie kolumny.
KolumnÄ™ trzeciÄ… zamieniamy z kolumnÄ… drugÄ… i tym samym zamieniamy zmiennÄ… x3 z x1.
Otrzymujemy
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x2 x1 x3 x2 x3 x1
-3 -1 -2 -3 -1 -2
0 0
ïÅ‚ śł ïÅ‚ śł
k3"!k2
ïÅ‚ 5 22 śł ïÅ‚ 5 22 śł
a" .
0 3 0 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
3 3 3 3
2 19 2 19
0 1 0 1
3 3 3 3
Następnie za pomocą wiersza głównego eliminujemy zmienną x3 z trzeciego wiersza:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x2 x3 x1 x2 x3 x1
1 -3 -1 -2
-3 -1 -2
0 0
w3- w2
ïÅ‚ śł ïÅ‚ śł
3
ïÅ‚ 5 22 śł ïÅ‚ 5 22 śł
a" . (37)
0 3 0 3
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
3 3 3 3
2 19 1 35
0 1 0 0
3 3 9 9
Z macierzy (37) odczytujemy

1 5 22 1
x1 = 35, x3 = - x1 + , x2 = - (x1 - 2).
3 3 3 3
Ostatecznie
x1 = 35, x2 = -11, x3 = -17.
14