Układy równań liniowych  metoda eliminacji Gaussa
Nale\
y rozwiązać układ równań liniowych:
Ax = b , (1)
gdzie
A" Rn×n , b " Rn×1 ,
x " Rn×1 - wektor niewiadomych.
Metoda eliminacji Gaussa słu\
y do przeksztaÅ‚cenia macierzy kwadratowej A " Rn×n do
postaci górnie trójkątnej.
a11 a12 L a1n a11 a12 L a1n
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚a a22 L a2n śł ïÅ‚ (1 (
0 a22) L a21) śł
21 n
ïÅ‚ śł ïÅ‚ śł
A = Ò! A(n-1) = (2)
ïÅ‚ śł ïÅ‚ śł
L L L L M O O
ïÅ‚a an2 L ann śł ïÅ‚
(n
0 L 0 ann-1) śł
ðÅ‚ n1 ûÅ‚ ðÅ‚ ûÅ‚
Przeksztaceń dokonuje się na macierzy rozszerzonej o wektor wyrazów wolnych:
[A | b]Ò! [A(n-1) | b(n-1)]
. (3)
1 krok
Je\
eli a11 `" 0, wtedy zerujemy elementy pierwszej kolumny le\
ące pod główną
przekątną czyli te w wierszu 2, 3, & , n. Obliczamy współczynniki:
a21 a31 an1
p2 = , p3 = , & , pn = , (4)
a11 a11 a11
a następnie dokonujemy przekształceń:
w3 := w3 - p3 Å" w1 wn := wn - pn Å" w1
w2 := w2 - p2 Å" w1 ,
, & , , (5)
gdzie
wi - oznacza i - ty wiersz macierzy A rozszerzonej o wektor b .
Po 1 kroku otrzymujemy macierz postaci:
a11 a12 L a1n
îÅ‚ Å‚Å‚
ïÅ‚ (1 (
0 a22) L a21) śł
n
ïÅ‚ śł
A(1) = , (6)
ïÅ‚ śł
L L L L
ïÅ‚
( (1
0 an1) L ann) śł
ðÅ‚ 2 ûÅ‚
oraz wektor wyrazów wolnych postaci:
îÅ‚ Å‚Å‚
b1
ïÅ‚b(1) śł
2
ïÅ‚ śł
b(1) = . (7)
ïÅ‚ śł
L
ïÅ‚ śł
(1)
ïÅ‚ śł
ðÅ‚bn ûÅ‚
k-ty krok (dla k = 2, 3, ..., n-1)
(k
Je\
eli akk -1) `" 0 , wtedy zerujemy elementy k-tej kolumny le\
ące pod główną
przekątną czyli te w wierszu k+1, k+2, & , n. Obliczmy współczynniki:
( (
(k
akk -1) akk -1)
ank -1)
+1,k +2,k
pk +1 = , pk +2 = , & , pn = , (8)
(k (k (k
akk -1) akk -1) akk -1)
a następnie dokonujemy przekształceń:
wk +1 := wk +1 - pk +1 Å" wk ,
wk +2 := wk +2 - pk +2 Å" wk , (9)
&
wn := wn - pn Å" wk ,
gdzie
wi - oznacza i - ty wiersz macierzy A(k -1) rozszerzonej o wektor b(k -1) .
Po k-tym kroku otrzymujemy macierz postaci:
a11 L a1k L a1n
îÅ‚ Å‚Å‚
ïÅ‚ śł
0 O M M
ïÅ‚ śł
(k ( 1) (k
ïÅ‚ śł
M O akk -1) akkk-+1 L akn-1)
,
A(k ) = , (10)
ïÅ‚
( (
0 L 0 akk ) +1 L akk ) śł
+1,k +1,n
ïÅ‚ śł
ïÅ‚K śł
L L L L
ïÅ‚ śł
( (k
0 L 0 ankk)+1 L ann) śł
ïÅ‚
,
ðÅ‚ ûÅ‚
oraz wektor wyrazów wolnych postaci:
îÅ‚ Å‚Å‚
b1
ïÅ‚ śł
(
b21)
ïÅ‚ śł
ïÅ‚ śł
L
b(k ) = (11)
ïÅ‚ śł
(k -1)
ïÅ‚bk śł
ïÅ‚ śł
L
ïÅ‚ śł
(k -1)
ïÅ‚ śł
ðÅ‚bn ûÅ‚
Po (n-1) krokach eliminacji Gaussa (wykonanych czyli w ka\
dym kroku był spełniony
(k (n
warunek akk -1) `" 0 ), je\
eli ann-1) `" 0 nale\
y wykonać postępowanie odwrotne:
(
bnn-1)
xn = , (12)
(n
ann-1)
n
( (k
bkk ) - (x Å" akj ))
" j
j=k +1
xk = dla k = n-1, n-2, & , 1. (13)
(k
akk )
(k
Je\
eli zdarzyło się, \
e w którymś kroku element na głównej przekątnej akk -1) = 0 ,
wtedy postępowanie Gaussa nie mo\
e zostać wykonane. Oznacza to, \
e macierz A jest
osobliwa i nie istnieje dokładnie jedno rozwiązanie układu (1).
Ćwiczenie 1
Metodą eliminacji Gaussa z pełnym wyborem elementu maksymalnego rozwiązać
układ równań:
x2 + 2x3 + 3x4 = 8
Å„Å‚
ôÅ‚x + x3 + 2x4 = 4
ôÅ‚
1
òÅ‚x + 2x2 + 3x3 + 4x4 = 10
1
ôÅ‚
ôÅ‚x2 + 3x3 + 2x4 = 7
ół
Ćwiczenie 2
Metodą eliminacji Gaussa z wyborem elementu maksymalnego w kolumnie rozwiązać
układ równań:
2x1 + 3x2 - 4x3 = 9
Å„Å‚
ôÅ‚x + 2x2 - 2x3 = 7
òÅ‚
1
ôÅ‚4x - 2x2 + 5x3 = -5
ół 1
Ćwiczenie 3
Napisać program realizujący rozwiązywanie układu równań liniowych metodami
eliminacji Gaussa:
1) podstawowÄ… (bez wyboru elementu maksymalnego);
2) z pełnym wyborem elementu maksymalnego (element maksymalny wybieramy z );
3) z wyborem elementu maksymalnego w wierszu (w k-tym kroku element maksymalny
wybieramy z k-tego wiersza macierzy A(k -1) a dokładnie z elementów
(k ( 1) (k
akk -1) , akkk-+1, ..., akn -1) , bo wcześniejsze, tj. le\
Ä…ce na lewo w tym wierszu, sÄ… zerami);
,
4) z wyborem elementu maksymalnego w kolumnie (w k-tym kroku element
maksymalny wybieramy z elementów le\
Ä…cych nie wy\
ej ni\
przekÄ…tna w k-tej
(k ( (k
kolumnie macierzy A(k-1) , tj. z elementów akk -1) , akk -1) , ..., ank -1) ).
+1,k
Program przetestować (m.in.!) dla układów równań:
x1 + x2 + x4 - 3x5 = 1
Å„Å‚
ôÅ‚2x - x3 - 2x5 = 1
1
ôÅ‚
ôÅ‚x
a) - x2 - 2x3 + x4 - 2x5 = 1
òÅ‚
1
ôÅ‚2x + x3 + x5 = -1
1
ôÅ‚
ôÅ‚- 3x1 - x2 + x3 + 2x4 + 2x5 = 1
ół
2x1 + 4x2 - 6x4 = 1
Å„Å‚
ôÅ‚x - 5x2 + 3x3 - x4 = -3
ôÅ‚
1
b)
òÅ‚3x + 2x2 - x3 + 2x4 = 9 .
1
ôÅ‚
ôÅ‚6x1 + x2 + 2x3 - 5x4 = 22
ół