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