Rozwiązywanie układów równań
liniowych
Układ równań liniowych Ax=b, gdzie A jest
daną macierzą o m wierszach i n kolumnach, b –
wektorem kolumnowym m danych liczb, x
wektorem kolumnowym n niewiadomych, może
posiadać nieskończenie wiele rozwiązań,
dokładnie jedno rozwiązanie lub nie posiadać
wcale rozwiązań (układ sprzeczny).
O ile warunki istnienia rozwiązania są
teoretycznie proste, to numeryczne
wyznaczanie rozwiązania może być zadaniem
bardzo trudnym.
Istnieje wiele metod rozwiązywania układów
równań liniowych i decyzja którą z nich wybrać,
powinna zależeć nie tylko od postaci macierzy
A, ale także od specyfiki zagadnienia, które
reprezentuje dany układ równań.
Jeśli na przykład istnieje potrzeba wielokrotnego
rozwiązywania układu równań przy różnych
wartościach wektora b, to należy zastosować
metodę, która przekształci układ do prostszej
postaci, ułatwiającej wyznaczanie dalszych
rozwiązań.
Należy pamiętać, ze istnieją trzy przyczyny
występowania błędów w numerycznie
wyznaczonym rozwiązaniu:
-błąd spowodowany niedokładnymi wartościami
współczynników układu równań (błąd wejściowy),
-błąd powstający na skutek popełniania błędów
podczas numerycznego wykonywania działań
arytmetycznych (błąd zaokrągleń)
-błąd wyznaczania rozwiązania spowodowany
sposobem działania metody (błąd metody)
Metody dokładne
Jeżeli rozwiązanie układu równań Ax=b polega
na takim przekształceniu danych A i b, że przy
założeniu dokładnie wykonywanych działań
arytmetycznych po skończonej liczbie działań
otrzymujemy rozwiązanie, to taką metodę
rozwiązania nazywamy metodą dokładną.
Do metod dokładnych należy zaliczyć wyznaczanie
rozwiązań na podstawie gotowych wzorów
(wzorów Cramera)
Dla układu 2 równań liniowych
mamy następujące gotowe wzory
2
2
22
1
21
1
2
12
1
11
b
x
a
x
a
b
x
a
x
a
(1)
12
21
22
11
2
21
2
11
2
12
21
22
11
2
12
1
22
1
,
a
a
a
a
b
a
b
a
x
a
a
a
a
b
a
b
a
x
(2)
Wzory powyższe wynikają ze wzorów Cramera
Wartości wyznaczników obliczamy ze wzorów
Wyznacznik W
1
powstaje przez wstawienie kolumny
wyrazów wolnych do pierwszej kolumny
wyznacznika W
Wyznacznik W
2
powstaje przez wstawienie
kolumny wyrazów wolnych do drugiej kolumny
wyznacznika W
Wyznacznik główny W powstaje z elementów
macierzy A
W
W
x
W
W
x
2
2
1
1
,
(3)
12
21
22
11
22
21
12
11
a
a
a
a
a
a
a
a
W
(4)
2
12
1
22
2
12
22
1
22
2
12
1
1
b
a
b
a
b
a
a
b
a
b
a
b
W
(5)
1
21
2
11
2
21
1
11
2
b
a
b
a
b
a
b
a
W
(6)
Układ 3 równań liniowych
Wzory Cramera
Wyznaczniki
3
3
33
2
32
1
31
2
3
23
2
22
1
21
1
3
13
2
12
1
11
b
x
a
x
a
x
a
b
x
a
x
a
x
a
b
x
a
x
a
x
a
(7)
W
W
x
W
W
x
W
W
x
3
3
2
2
1
1
,
,
(8)
33
32
31
23
22
21
13
12
11
a
a
a
a
a
a
a
a
a
W
(9)
3
32
31
2
22
21
1
12
11
3
33
3
31
23
2
21
13
1
11
2
33
32
3
23
22
2
13
12
1
1
,
,
b
a
a
b
a
a
b
a
a
W
a
b
a
a
b
a
a
b
a
W
a
a
b
a
a
b
a
a
b
W
(10
)
Schemat Sarrusa
wyznaczania wartości wyznacznika 3 stopnia
32
31
22
21
12
11
33
32
31
23
22
21
13
12
11
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
dopisujemy
i tworzymy iloczyny
+ + +
- - -
33
21
12
32
23
11
31
22
13
32
21
13
31
23
12
33
22
11
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
(11)
Stosując metodę Cramera należy obliczyć (n+1)
wyznaczników, które wymagają co najmniej
(n+1)! mnożeń. Jest to więc metoda bardzo
pracochłonna i dlatego jej się nie stosuje dla
n>4.
Układ n równań liniowych z n niewiadomymi
W zapisie macierzowym ma on postać
Macierz współczynników A jest macierzą
nieosobliwą, tzn. det A 0 (wyznacznik
macierzy A jest różny od zera).
Istnieje więc macierz odwrotna A
-1
. W celu
rozwiązania układu mnożymy obie strony
równania (13) lewostronnie przez macierz A
-1
i
otrzymujemy
n
n
nn
n
n
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
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
(12)
Ax = b
(13)
x= A
-1
b
(14)
Macierz odwrotną A
-1
obliczamy ze wzoru
A
A
A
D
det
1
(15)
gdzie A
D
jest transponowana macierzą dopełnień
algebraicznych, czyli tzw. macierzą dołączoną o
postaci
nn
n
n
nk
k
k
n
n
D
A
A
A
A
A
A
A
A
A
A
A
A
A
2
1
2
1
2
22
12
1
21
11
(16)
gdzie elementy A
ij
są dopełnieniami
algebraicznymi elementów , tzn. wartościami
wyznaczników stopnia n –1 powstałych z
wyznacznika det A przez skreślenie i-tego wiersza i
j-tej kolumny pomnożonymi przez (-1)
i+j
.
Otrzymujemy więc
ij
a
b
A
A
x
D
det
1
(17)
Zauważmy, że w iloczynie
n
nn
n
n
n
nk
k
k
n
n
n
n
D
b
A
b
A
b
A
b
A
b
A
b
A
b
A
b
A
b
A
b
A
b
A
b
A
b
A
2
2
1
1
2
2
1
1
2
2
22
1
12
1
2
21
1
11
(18
)
dowolny k-ty wiersz jest równy wartości
wyznacznika D
k
powstałego z wyznacznika det A
przez zastąpienie w nim k-tej kolumny kolumną
wyrazów wolnych
nn
k
n
n
k
n
n
in
k
i
i
k
i
i
n
k
k
n
k
k
k
n
j
jk
k
a
a
b
a
a
a
a
b
a
a
a
a
b
a
a
a
a
b
a
a
b
A
D
1
,
1
,
1
1
,
1
,
1
2
1
,
2
2
1
,
2
21
1
1
,
1
1
1
,
1
11
1
det
(19)
Ostatecznie równość (14) przyjmie postać
Wzory Cramera
Z tego równania bezpośrednio wynikają wzory
Cramera
n
k
n
k
D
D
D
D
A
x
x
x
x
2
1
2
1
det
1
(20)
n
k
A
D
x
k
k
,
,
2
,
1
,
det
(21)
Układy równań z macierzą trójkątną
górną
Jeżeli macierz A układu n równań z n
niewiadomymi Ax = b
jest macierzą trójkątną górną i wszystkie elementy
na przekątnej głównej są różne od zera,
rozwiązanie x takiego układu można otrzymać
rekurencyjnie.
Z ostatniego równania możemy obliczyć
niewiadomą x
n
Podstawiając x
n
do pozostałych równań możemy
obliczyć niewiadomą x
n-1
, a następnie postępując
podobnie pozostałe niewiadome według wzoru:
n
n
nn
n
n
n
n
b
x
a
b
x
a
x
a
b
x
a
x
a
x
a
2
2
2
22
1
1
2
12
1
11
(22)
nn
n
n
a
b
x
(23)
1
,
,
2
,
1
,
1
1
n
n
i
a
x
a
x
a
b
x
ii
i
ii
in
in
i
i
(24)
Układy równań z macierzą trójkątną
dolną
Niech macierz A układu n równań z n
niewiadomymi Ax = b jest macierzą trójkątną
dolną z 1 na głównej przekątnej. Mamy zatem
układ równań postaci
którego niewiadome obliczamy ze wzoru
rekurencyjnego
n
x
x
x
,
,
,
2
1
Łatwo obliczyć, że dla wyznaczenia wektora x
należy wykonać n dzieleń i
mnożeń oraz odejmowań
n
n
M
2
1
2
2
1
n
n
D
2
1
2
2
1
n
n
n
n
i
i
i
ii
i
i
b
x
x
a
x
a
b
x
x
a
x
a
x
a
b
x
x
a
x
a
b
x
x
a
b
x
2
2
1
1
1
1
2
2
1
1
3
3
2
32
1
31
2
2
1
21
1
1
(25)
n
i
x
a
x
a
b
x
b
x
i
ii
i
i
i
,
,
3
,
2
,
1
1
1
1
1
1
(26)
Łatwo obliczyć, że dla wyznaczenia wektora x
należy wykonać
mnożeń i
odejmowań
n
n
M
2
1
2
2
1
n
n
O
2
1
2
2
1
Metoda eliminacji
Gaussa
Najczęściej stosowaną metodą do numerycznego
rozwiązywania układu równań liniowych jest
metoda eliminacji Gaussa.
Jeśli rozwiązujemy układ równań Ax = b z pełną
macierzą kwadratową A, to można rozwiązać go w
dwóch etapach: sprowadzając układ do postaci
trójkątnej górnej (22), który umiemy już rozwiązywać
stosując wzory (23) i (24)
Dany jest układ równań liniowych Ax = b
postaci
n
n
nn
n
n
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
2
2
1
1
2
2
2
22
1
21
1
1
2
12
1
11
(27)
)
1
(
)
1
(
2
)
1
(
2
1
)
1
(
1
)
1
(
2
)
1
(
2
2
)
1
(
22
1
)
1
(
21
)
1
(
1
)
1
(
1
2
)
1
(
12
1
)
1
(
11
n
nn
n
n
n
n
b
a
x
a
x
a
b
a
x
a
x
a
b
a
x
a
x
a
(28)
Zakładamy dalej, że macierz A
(1)
= (a
ij
) jest
nieosobliwa. Wtedy układ A
(1)
x = b
(1)
ma
jednoznaczne rozwiązanie.
Załóżmy teraz, że a
11
0, Wtedy z ostatnich n-
1 równań możemy wyeliminować x
1
odejmując od
i-tego równania tego układu, i = 2,3,...,n,
pierwsze równanie pomnożone przez
Etap pierwszy ( zwany etapem eliminacji
zmiennych).
Proces eliminacji przebiega w n -1
krokach.Oznaczmy Wtedy układ równań (16)
w nowych oznaczeniach A
(1)
x = b
(1)
przyjmie
postać
b
b
A
A
)
1
(
)
1
(
,
n
i
a
a
m
i
i
,...,
3
,
2
,
)
1
(
11
)
1
(
1
1
(29)
Otrzymujemy wtedy przekształcony układ postaci
Przekształcone równania A
(2)
x = b
(2)
przybierają postać
)
2
(
)
2
(
2
)
2
(
2
)
2
(
2
)
2
(
2
2
)
2
(
22
)
1
(
1
)
1
(
1
2
)
1
(
12
1
)
1
(
11
n
nn
n
n
n
b
a
x
a
b
a
x
a
b
a
x
a
x
a
(30)
)
2
(
(
2
(
2
)
2
(
2
)
2
(
2
(
2
(
2
2
)
2
(
22
n
n
nn
n
n
n
b
x
a
x
a
b
x
a
x
a
(31)
gdzie nowe współczynniki są dane wzorami
n
i
b
m
b
b
n
j
a
m
a
a
i
i
i
j
i
ij
ij
,
,
3
,
2
,
,
,
3
,
2
,
)
1
(
1
1
)
1
(
)
2
(
)
1
(
1
1
)
1
(
)
2
(
(32)
Nowy układ składa się z n–1 równań i zawiera n-1
niewiadomych
n
x
x
x
,
,
3
2
Wyeliminowaliśmy w ten sposób pierwszą
niewiadomą x
1
z
równań leżących w wierszach
o numerach i = 2,3, ...n
.
Podobnie eliminujemy x
2
z równań leżących w
wierszach 3,4,...,n
odejmując od i-tego wiersza tego
układu, i = 3,4,...,n, wiersz drugi pomnożony przez
mnożnik
Otrzymamy wtedy układ n-2 równań A
(3)
x = b
(3)
o n-2
niewiadomych którego współczynniki będą
dane wzorami
n
x
x
,
3
n
i
a
a
m
i
i
,
,
4
,
3
,
)
2
(
22
)
2
(
2
2
(33)
n
i
b
m
b
b
n
j
a
m
a
a
i
i
i
j
i
ij
ij
,
,
3
,
,
,
3
,
)
2
(
2
2
)
2
(
)
3
(
)
2
(
2
2
)
2
(
)
3
(
(34)
Postępując w ten sposób otrzymamy kolejne,
przekształcone układy równań A
(3)
x = b
(3)
,A
(4)
x
= b
(4)
,..., i po (n-1) eliminacjach uzyskamy układ
równań A
(n)
x = b
(n)
o jednej niewiadomej postaci
Zbierzmy teraz pierwsze równania z każdego
kroku:
Elementy występujące w eliminacji
nazywa się elementami głównymi
)
(
)
3
(
33
)
2
(
22
)
1
(
11
,
,
,
,
n
nn
a
a
a
a
Tak więc zredukowaliśmy układ (27) do układu
trójkątnego górnego, który umiemy już
rozwiązać,
)
(
)
(
n
n
n
n
nn
b
x
a
(35)
)
(
)
(
)
2
(
2
)
2
(
2
2
)
2
(
22
)
1
(
1
)
1
(
1
2
)
2
(
12
1
)
1
(
11
n
n
n
n
nn
n
n
n
n
b
x
a
b
x
a
x
a
b
x
a
x
a
x
a
(36)
Etap drugi (jest nazywany postępowaniem odwrotnym
lub podstawieniem wstecz). Otrzymany po
przekształceniu układ rozwiązujemy zgodnie ze
wzorami (23) i (24)
Opisany powyżej sposób nazywamy metodą
eliminacji Gaussa
Można obliczyć, że w celu otrzymania tą metodą
rozwiązania x należy wykonać łącznie
mnożeń i dzieleń oraz
odejmowań
n
n
n
M
3
1
2
3
3
1
n
n
n
D
6
5
2
2
1
3
3
1
Zauważmy, że prawą stronę b przekształca się tak
samo jak kolumny macierzy A. Dlatego opis
eliminacji uprości się, jeśli uznamy b za ostatnią
kolumnę macierzy A i przyjmiemy, że
Wtedy wzory można streścić w następujący
sposób. Eliminację wykonuje się w n -1 krokach
o numerach k = 1,2,...,n-1. W k-tym
kroku elementy dla j, j>k przekształca się
według wzorów
)
(k
ij
a
n
i
k
b
a
k
i
k
k
i
1
,
)
(
)
(
1
,
(37)
)
1
,
,
2
,
1
;
,
,
2
,
1
(
,
)
(
)
(
)
1
(
)
(
)
(
n
k
k
j
n
k
k
i
a
m
a
a
a
a
m
k
kj
ik
k
ij
k
ij
k
kk
k
ik
ik
(38)
Mamy zatem dwie równości L
(1)
A
(1)
= A
(2)
,
L
(1)
b
(1)
= b
(2)
Analogicznie otrzymujemy dwie następne równości:
L
(2)
A
(2)
= A
(3)
, L
(2)
b
(2)
= b
(3)
, gdzie
n
i
a
a
l
l
l
L
i
i
n
,
,
4
,
3
,
,
1
0
1
0
0
1
0
1
)
2
(
22
)
2
(
2
2
2
32
)
2
(
Postępując dalej w ten sposób otrzymujemy
ostatecznie
L
(n-1)
L
(n-2)•••
L
(1)
A
(1) =
A
(n)
, L
(n-1)
L
(n-2)•••
L
(1)
b
(1) =
b
(n)
Macierze L
(i)
, i = 1,2,...,n, są nieosobliwe, możemy
zatem napisać
)
(
1
)
1
(
1
)
2
(
1
)
1
(
)
1
(
n
n
A
L
L
L
A
(40)
A
L
U
Zauważmy teraz , że jeśli mamy wiele układów
równań o wspólnej macierzy A:
Ax
1
= b
1
,
Ax
2
= b
2
... Ax
p
= b
p
to można przekształcać je łącznie, traktując b
j
jako
(n+j )-tą kolumnę macierzy A. Jedyną różnicą w
porównaniu z algorytmem (27) będzie obecnie to, ze
wskaźnik j powinien przebiegać wartości
k+1,k+2,...,n+p. Po eliminacji otrzymamy p
układów trójkątnych do rozwiązania.
W trakcie eliminacji może się zdarzyć, że w k-tym
kroku lub też jest bliski zeru.
0
)
(
k
kk
a
Wtedy trzeba zwykle wybierać element główny w
k-tym kroku zgodnie z jedną z następujących
strategii:
Wybór częściowy elementu głównego
Wybiera się r jako najmniejszą liczbę
całkowitą, dla której
)
(
max
)
(
k
ik
n
i
k
k
rk
a
a
i przestawia się wiersze k i r.
Wybór pełny elementu głównego
Wybiera się r i s jako najmniejsze liczby
całkowite dla których
)
(
max
,
)
(
k
ij
n
i
i
k
k
rs
a
a
i przestawia się wiersze k i r oraz kolumny k
i s
Rozkład macierzy A na iloczyn macierzy
trójkątnych L·U
W wielu zagadnieniach numerycznych dotyczących
macierzy kwadratowych A, poszukujemy takich
macierzy trójkątnych L i U, by A = L · U.
Metoda eliminacji Gaussa umożliwia wyznaczenie
takiego rozkładu.
Zauważmy, że przekształcenie układu A
(1)
x = b
(1)
do postaci A
(2)
x = b
(2)
jest równoważne pomnożeniu
obu stron układu ( 17) przez macierz
n
i
a
a
l
l
l
l
L
i
i
n
,
,
3
,
2
,
,
1
0
0
1
0
0
1
1
)
1
(
11
)
1
(
1
1
1
31
21
)
1
(
itd
l
l
L
l
l
l
L
n
n
,
1
0
0
1
0
0
1
0
1
,
1
0
0
1
0
0
1
1
2
32
1
)
2
(
1
31
21
1
)
1
(
Zauważmy, że
a
ponadto
1
1
0
1
1
3
2
1
32
31
21
1
)
1
(
1
)
2
(
1
)
1
(
n
n
n
n
l
l
l
l
l
l
L
L
L
Jeśli powyższą macierz oznaczymy symbolem L,
a macierz A
(n)
symbolem U, to rozkład (40)
macierzy A
(1)
na iloczyn możemy zapisać
następująco
A
(1)
= LU
(41)
gdzie L jest macierzą trójkątną dolną, a U –
macierzą trójkątną górną
Z przeprowadzonych rozważań wynika, że jeżeli
etap eliminacji zmiennych metodą Gaussa można
wykonać do końca, to układ równań Ax = b można
zapisać jako LUx = b.
Etap ten jest zatem równoważny przekształceniu
wejściowego układu do postaci Ux = L
-1
b = b
(n)
, a
wyznaczanie rozwiązania x polega na rozwiązaniu
dwu układów z macierzami trójkątnymi
Ly = b, Ux = y
Document Outline